| グラフ: | 無向グラフ |
|---|---|
| プロパティ: | 色、次数 |
| 計算量: | 時間: m = max { degree(v) | v in V } の場合 O(log(m)|E|) |
(1)
template <class IncidenceGraph, class OutputIterator,
class ColorMap, class DegreeMap>
void
cuthill_mckee_ordering(IncidenceGraph& g,
typename graph_traits<Graph>::vertex_descriptor s,
OutputIterator inverse_permutation,
ColorMap color, DegreeMap degree)
(2)
template <class VertexListGraph, class OutputIterator,
class ColorMap, class DegreeMap>
void
cuthill_mckee_ordering(VertexListGraph& G, OutputIterator inverse_permutation,
ColorMap color, DegreeMap degree)
Cuthill-Mckee (と逆 Cuthill-Mckee) 順序付けアルゴリズム [14, 43, 44, 45] の目的は各頂点に割り当てられ
ている添え字を再順序付けすることによってグラフの帯域幅を減らすことである。
Cuthill-Mckee の順序付けアルゴリズムは i 番目の帯域幅の局所最小化によって
動作する。頂点は基本的に幅優先探索順に割り当てられる。但し各段階において、
隣接頂点がキュー中に次数の昇順で並べられることを除く。
アルゴリズムのバージョン (1) はユーザに“始点”を選ばせるのに対し、 バージョン (2) は疑似周辺ペアの発見的手法を用いて良好な始点を見つける。 “始点”の選択は順序付けの品質上重要な影響を持つ傾向がある。
アルゴリズムの出力は新しい順序付けになっている頂点である。 使用した出力イテレータの種類に依存して、Cuthill-Mckee の順序付けまたは 逆 Cuthill-Mckee の順序付けのどちらか一方を得られる。例えば、出力を vector のリバース・イテレータを用いて vector に格納すれば、逆 Cuthill-Mckee 順序付けを得る。
std::vector<vertex_descriptor> inv_perm(num_vertices(G)); cuthill_mckee_ordering(G, inv_perm.rbegin());
どちらの方法でも、出力を vector に格納することは新しい順序付けから 古い順序付けへの順列を与える。
inv_perm[new_index[u]] == u
多くの場合、欲しい順列は逆の順列、つまり古い添え字から新しい添え字への順列 である。これは次の方法で簡単に計算され得る。
for (size_type i = 0; i != inv_perm.size(); ++i)
perm[old_index[inv_perm[i]]] = i;
| Copyright © 2000-2001 | Jeremy Siek, Indiana University (jsiek@osl.iu.edu) |
Japanese Translation Copyright © 2003 Takashi Itou
オリジナルの、及びこの著作権表示が全ての複製の中に現れる限り、この文書の複製、利用、変更、販売そして配布を認める。このドキュメントは「あるがまま」に提供されており、いかなる明示的、暗黙的保証も行わない。また、いかなる目的に対しても、その利用が適していることを関知しない。
このドキュメントの対象: Boost Version 1.30.0
最新版ドキュメント (英語)