id:faith_and_brave:20131003:1380788496に関して少しばかし補足.
まず,知るべきことはboost::adjaceny_listのテンプレート引数を省略した場合である.この場合,以下の引数を指定したものとして扱われる.
boost::adjacency_list< boost::vecS, // OutEdgeList boost::vecS, // VertexList boost::directedS, // Directed boost::no_property, // VertexProperty boost::no_property, // EdgeProperty boost::no_property, // GraphProperty boost::listS // EdgeList >
ここでは各引数の詳細は説明しないが,ここで注目していただきたいのは2番目のVertexListとコメントしたテンプレート引数である.
このVertexListテンプレート引数にはグラフの節点(Vertex)を格納するコンテナを指定する.デフォルトではvecSとなっており,これはstd::vectorに対応している.ここで注意して頂きたいことはVertexListがvecSの場合,adjaceny_listは自動的に各節点にindex番号が割り当てられたIndexedGraph*1になるということである.
このときもう一つ注意すべきことは,このIndexedGraphではindexの値が自動で割り振られ,外部からは変更不可能ということである.このときの節点のindex値は[0, num_vertices(g))中の値に一対一に対応する(gはadjacency_listのオブジェクトである).つまり,indexに任意の値を割り当てることができないことになる.
よって,VertexListがvecSでない場合はデフォルトではIndexedGraphにならない.以下のコードはエラーになる.
#include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/range/algorithm/for_each.hpp> #include <boost/range/counting_range.hpp> int main() { using Graph = boost::adjacency_list< boost::listS, boost::listS, // VertexListはlistS boost::directedS, boost::no_property // VertexPropertyはなし >; Graph g; for (auto i : boost::counting_range(0, 5)) { add_vertex(g); } using Vertex = boost::graph_traits<Graph>::vertex_descriptor; boost::for_each(vertices(g), [&](Vertex const v) { std::cout << get(boost::vertex_index, g, v) << std::endl; // error gはIndexedGraphではない }); }
この場合,以下のように手動でグラフにindexを持たせる必要がある.
#include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/range/algorithm/for_each.hpp> #include <boost/range/counting_range.hpp> int main() { using IndexProp = boost::property<boost::vertex_index_t, std::size_t>; using Graph = boost::adjacency_list< boost::listS, boost::listS, // VertexListはListS boost::directedS, IndexProp // VertexPropertyはvertex_indexを持つproperty >; Graph g; for (auto i : boost::counting_range(0, 5)) { add_vertex(IndexProp(i * 2), g); // ついでなのでindexを2の倍数とする } using Vertex = boost::graph_traits<Graph>::vertex_descriptor; boost::for_each(vertices(g), [&](Vertex const v) { std::cout << get(boost::vertex_index, g, v) << std::endl; }); }
ここではadjacency_listのVertexPropertyにvertex_indexを持つpropertyを指定した.これにより,get(boost::vertex_index, g, v)で節点vからindexを取得することが可能となる.
また,ここでは関数add_vertexの呼び出し時に各節点のindexの値を設定している.
実際はvertex_indexの値は上記のような不連続な値にせず,[0, num_vertices(g))に対応するように割り当てるべきである*2.こういったindex付けをしたい場合は,vertex_indexの代わりにvertex_index1やvertex_index2が用意されているのでこちらを用いるとよい.