sloan_ordering

  (1)
  template <class Graph, class OutputIterator,
                  class ColorMap, class DegreeMap, 
                  class PriorityMap, class Weight>
  OutputIterator
  sloan_ordering(Graph& g,
                 typename graph_traits<Graph>::vertex_descriptor s,
                 typename graph_traits<Graph>::vertex_descriptor e,
                 OutputIterator permutation, 
                 ColorMap color, 
                 DegreeMap degree, 
                 PriorityMap priority, 
                 Weight W1, 
                 Weight W2 )

  (2)
   template <class Graph, class OutputIterator,
                  class ColorMap, class DegreeMap, 
                  class PriorityMap, class Weight>
  OutputIterator
  sloan_ordering(Graph& g,
                 OutputIterator permutation, 
                 ColorMap color, 
                 DegreeMap degree, 
                 PriorityMap priority, 
                 Weight W1, 
                 Weight W2 )


(3)
 template <class Graph, class OutputIterator,
                  class ColorMap, class DegreeMap, 
                  class PriorityMap>
  OutputIterator
  sloan_ordering(Graph& g,
                 typename graph_traits<Graph>::vertex_descriptor s,
                 typename graph_traits<Graph>::vertex_descriptor e,
                 OutputIterator permutation, 
                 ColorMap color, 
                 DegreeMap degree, 
                 PriorityMap priority )


(4)
 template <class Graph, class OutputIterator,
                  class ColorMap, class DegreeMap, 
                  class PriorityMap>
  OutputIterator
  sloan_ordering(Graph& g,
                 OutputIterator permutation, 
                 ColorMap color, 
                 DegreeMap degree, 
                 PriorityMap priority )

Sloan ordering algorithm （スローンの順序アルゴリズム）[1, 2] の目的は、各頂点に割り当てられたインデックスを並び替えることによって、波面のグラフ、即ち縦断面を減少させることである。スローンのアルゴリズムでは、起点と終点が必要である。起点と終点は任意に指定できるが、効率よく減少させるための起点と終点が探査可能な sloan_starting_nodes （スローンの起点探査）アルゴリズムが存在するので、そちらを使うとよい。各頂点には優先度というプロパティが割り当てられている。この優先度は終点（大域的基準）までのベクトルに対する距離の合計を重みとしたものであり、頂点のカレント次数と呼ばれる。このカレント次数は、ある頂点（局所的基準）の隣接頂点から数えあげる優先度を基本的に反映する。それゆえにスローンの順序アルゴリズムは（McKee とは対照的に）、局所的基準と大域的基準を再整列に関して同等に考慮する。重みの関係は調整することができるが、スローンによって提案された (weight1/weight2= 1/2) というデフォルトの関係は、ほとんどのケースで最良に近いものとなるであろう。

バージョン１のアルゴリズムではユーザが始点と終点を選択することができるのに対して、バージョン２のアルゴリズムでは前述の sloan_starting_node （スローンの起点探査）アルゴリズムにより良好な始点を見つける。始点と終点の選択は順序生成の品質に多大な影響をおよぼすであろう。バージョン３とバージョン４は、標準の重み W1=1 と W2= 2 が使用されるという点を除いて、それぞれバージョン１とバージョン２に対応する。

このアルゴリズムの出力は新たに順序付けされた頂点インデックスである。どのような種類の出力イテレータを利用してもかまわないし、スローンの順序として取り出すことも、その逆順で取り出すことも可能である。例えば、std::vector （ベクタ）へ出力を保持しておき、std::vector<vertex_descriptor>::reverse_iterator （ベクタの逆行イテレータ）を使用すれば、スローンの順序と逆の順序を得ることができる。

  std::vector<vertex_descriptor> inv_perm(num_vertices(G));
  sloan_ordering(G, inv_perm.rbegin());

一方で、ベクタへ出力を保持しておけば、新しいインデックスから古いインデックスへの変換を得ることができる。

  inv_perm[new_index[u]] == u

ときには、古いインデックスから新しいインデックスへの逆変換が必要となることもあろうが、これは、以下のように簡単に計算することができる。

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

通常、Cuthill-McKee のアルゴリズムでは、逆方向の順序が必要され、スローンのアルゴリズムでは順方向の順序が必要とされる。

パラメータ

• Graph& g   （入力）
  無向グラフ。グラフ・タイプは IncidenceGraph というモデルでなければならない。 
• vertex_descriptor s  （入力）
  始点
• vertex_descriptor e （入力）
  終点
  
• OutputIterator permutation  （出力）
  新たな頂点の順序。頂点は新たな順序で output iterator （出力イテレータ）に書き出される。
• ColorMap color_map  （作業用）
  このアルゴリズム過程の探査を維持する目的で内部的に使用される（同一頂点を２度訪れるのを防ぐため）。
• PriorityMap priority_map  （入力）
  各頂点を並び替えるにあたって優先度を保持するために内部的に使用される。
• DegreeMap degree_map  （入力）
  これは各頂点の各次数に対するマップでなければならない。
• Weight W1 & W2  （入力）
  スローンのアルゴリズムのための heuristical  （発見的）重み。

バージョン（２）版：

• Graph& g   （入力）
  無向グラフ。グラフ・タイプは IncidenceGraph というモデルでなければならない。
  
• OutputIterator permutation  （出力） 
  新たな頂点の順序。頂点は新たな順序で output iterator （出力イテレータ）に書き出される。 
• ColorMap color_map  （作業用）
  このアルゴリズム過程の探査を維持する目的で内部的に使用される（同一頂点を２度訪れるのを防ぐため）。
• PriorityMap priority_map  （入力）
  各頂点を並び替えるにあたって優先度を保持するために内部的に使用される。
• DegreeMap degree_map   （入力）
  これは各頂点の各次数に対するマップでなければならない。
• Weight W1 & W2   （入力）
  スローンのアルゴリズムのための heuristical  （発見的）重み。

バージョン（３）版：

• Graph& g  （入力）
  無向グラフ。グラフ・タイプは IncidenceGraph というモデルでなければならない。
• vertex_descriptor s  （入力） 
  始点
• vertex_descriptor e （入力）
  終点
  
• OutputIterator permutation   （出力）
  新たな頂点の順序。頂点は新たな順序で output iterator （出力イテレータ）に書き出される。
• ColorMap color_map   （作業用）
  このアルゴリズム過程の探査を維持する目的で内部的に使用される（同一頂点を２度訪れるのを防ぐため）。
• PriorityMap priority_map  （入力）
  各頂点を並び替えるにあたって優先度を保持するために内部的に使用される。
• DegreeMap degree_map   （入力）
  これは各頂点の各次数に対するマップでなければならない。

バージョン（４）版：

• Graph& g   （入力）
  無向グラフ。グラフ・タイプは IncidenceGraph というモデルでなければならない。
  
• OutputIterator permutation  （出力） 
  新たな頂点の順序。頂点は新たな順序で output iterator （出力イテレータ）に書き出される。 
• ColorMap color_map   （作業用）
  このアルゴリズム過程の探査を維持する目的で内部的に使用される（同一頂点を２度訪れるのを防ぐため）。
• PriorityMap priority_map  （入力）
  各頂点を並び替えるにあたって優先度を保持するために内部的に使用される。
• DegreeMap degree_map   （入力）
  これは各頂点の各次数に対するマップでなければならない。

例

関連項目

sloan_start_end_vertices ， bandwidth ， profile ， wavefront ， boost/graph/properties.hpp 中の degree_property_map

[1] S. W. Sloan, An algorithm for profile and wavefront reduction of sparse matrices, Int. j. numer. methods eng., 23, 239 - 251 (1986)

[2] S. W. Sloan, A fortran program for profile and wavefront reduction, Int. j. numer. methods eng., 28, 2651 - 2679 (1989)

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