あめだまふぁくとりー

Boost.Graphとかできますん

boost::adjacency_listのVertexListテンプレート引数とvertex_indexの関係

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が用意されているのでこちらを用いるとよい.

*1:公式にはこのような呼び方はない

*2:この理由についてはいつか述べるかもしれない