# `minimum_degree_ordering`

      template <class AdjacencyGraph, class OutDegreeMap,
               class InversePermutationMap,
               class PermutationMap, class SuperNodeSizeMap, class VertexIndexMap>
      void minimum_degree_ordering
        (AdjacencyGraph& G,
         OutDegreeMap outdegree,
         InversePermutationMap inverse_perm,
         PermutationMap perm,
         SuperNodeSizeMap supernode_size, int delta, VertexIndexMap id)

最小次数順序付け [21, 35] は記入 (fill-in) を減少する 行列並べ替え のアルゴリズムである。Cholesky の因数分解 (対称行列のためのガウスの消去法の 亜種である) を使って A x = b のような方程式の体系を解く場合、 多くの機会に 0 であった行列中の要素が消去過程のために 0 でなくなる。 これが“記入 (fill-in)”と呼ばれる事で、記入は行列をより疎でなくし、それゆえ 後の消去段階と因数分解の結果を使う計算中でより多くの時間と領域を消費するので まずい。 行列の行の並び替えは生じる記入 (fill-in) の量に劇的に影響を及ぼすことが できることが現在明らかである。それで A x = b を解く代わりに、 並べ替えられた (しかし等価な) 体系 (P A PT)(P x) = P b を解く。最善の順序付けは NP完全問題 (すなわち、適度な量の時間で 解くことはできない) なので代わりに発見的手法を用いて“十分に良い”順序付けを 見つけるだけにする。最小次数順序付けアルゴリズムは一つのそのようなアプローチ である。

対称行列 `A` は通常は無向グラフで表される。しかしながらこの関数の ためには入力は有向グラフであることを必要とする。各々の 0 でない行列の記入 は`G` 中の二つの有向辺 (`e(i,j)` と`e(j,i)`) で 表されなければならない。

アルゴリズムの出力は新しい順序付け中の頂点である。

      inverse_perm[new_index[u]] == old_index[u]

古い添え字を新しい添え字に置換する。

      perm[old_index[u]] == new_index[u]

次の等式は常に保たれる。

      for (size_type i = 0; i != inverse_perm.size(); ++i)
        perm[inverse_perm[i]] == i;

### Parameters

- `AdjacencyGraph& G` (IN)
  有向グラフ。グラフの型は Adjacency Graph、Vertex List Graph、Incidence Graph、そして Mutable Graph のモデルでなければならない。 それに加え、関数 `num_vertices()` と `out_degree()` を 必要とする。
- `OutDegreeMap outdegree` (WORK)
  これは内部的に頂点の出次数を格納するのに使われる。これはキー型がグラフの 頂点記述子型と同じで、値型が汎整数型である LvaluePropertyMap でなければならない。
- `InversePermutationMap inverse_perm` (OUT)
  新しい頂点の順序付け。新しい添え字から古い添え字 (逆置換) へのマップとして 得られる。これは値型とキー型が符号付き整数の LvaluePropertyMap でなければならない。
- `PermutationMap perm` (OUT)
  新しい頂点の順序付け。古い添え字から新しい添え字 (置換) へのマップとして 得られる。これは値型とキー型が符号付き整数の LvaluePropertyMap でなければならない。
- `SuperNodeSizeMap supernode_size` (WORK/OUT)
  これは内部的に上位ノードの大きさを記録するために、また役立つ情報を保持する ために使われる。これは符号無し整数の値型と頂点記述子のキー型を持つ LvaluePropertyMap である。
- `int delta` (IN)
  多重消去を制御する変数。もしこれが 0 以上であれば、多重消去が許可されて いる。`delta` の値は最小次数と消去されるべき頂点の次数の間を述べる。
- `VertexIndexMap id` (IN)
  内部的に頂点をその添え字にマップするために使われる。これはキー型がグラフの 頂点記述子と同じで整数型の値型を持つ Readable Property Map でなければならない。

### Example

`example/minimum_degree_ordering.cpp` を見なさい。

### Implementation Notes

工事中

それはガウスの消去法の過程をシミュレートする各段階でグラフ中の最小次数 を持つ頂点を選ぶ。

この実装は全体消去、不完全な次数の更新、多重消去、そして外部の次数を 含む多くの拡張を提供する。最小次数のアルゴリズム史概論のために [35] を見なさい。

グラフの消去 Gv はグラフ G から頂点 v とその全ての接続辺を除去し、それからv へ隣接している全ての頂点を クリークにするために付け加える事 (すなわち、辺が既に存在していないならば 各隣接頂点のペア間に辺を付け加える) によって得られる。 グラフ G は行列 A の 0 でない構成を表現しているグラフであると 仮定してみよう。すると行列 A の行 i におけるガウスの消去法の 段階を実行する事は ... に等しい。

Copyright © 2001 | Lie-Quan Lee, Indiana University (llee@cs.indiana.edu) Jeremy Siek, Indiana University (jsiek@osl.iu.edu)

Japanese Translation Copyright © 2003 Takashi Itou
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。

このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント (英語)