読者です 読者をやめる 読者になる 読者になる

Folioscope

プログラミング/Unix系/デザイン/CG などのメモがもりもり

boostのグラフ別,動作の違い

boostにあるグラフライブラリのグラフの種類と動作の違いをまとめてみた.
boostのグラフには辺の向きのタイプが3種類用意されている.

directedS
有向グラフ.
undirectedS
無効グラフ.
bidirectionalS
有向グラフだが,双方向に走査できる.

またboostには,ある頂点に隣接する辺や頂点を取得する関数がいくつかある.

adjacent_vertex()
ある頂点に隣接する全ての頂点を取得する
in_edge()
ある頂点の全ての入辺を取得する
out_edge()
ある頂点の全ての出辺を取得する

これらのグラフの種類と各メソッドの動作の違いを調べてみる.

まず次のようにグラフを作成

graph_type g;
typename graph_type::vertex_descriptor v1, v2, v3;
v1 = boost::add_vertex(g);
v2 = boost::add_vertex(g);
v3 = boost::add_vertex(g);
boost::add_edge(v1, v2, g);
boost::add_edge(v2, v3, g);

有向グラフで表すと次のようなグラフである.
f:id:ibenza:20121031094333p:plain
ここで各関数にv2を放り込んで,帰ってきた結果が次の表のようになった.

directedS undirectedS bidirectionalS
adjacent_vertex() v3 v1, v3 v3
in_edge() - (v1,v2), (v2,v3) (v1,v2)
out_edge() (v2,v3) (v1,v2), (v2,v3) (v2,v3)

ここでdirectedSのin_edge()のデータが無いのはコンパイルができなかったからである.
うーむ,boostよくできている.