Boost.Graph.Stanford_graphを使ってみた

むずひ・・・
bglむずひ
それに輪をかけて、という表現は適切では無いけど、stanford_graphがあちこち分からん。
まぁ、とりあえず動いたんだけれども。
というわけで使用レポート。半分ぐらいstanford_graph関係ないけど。
間違ってたり適当な事言ってたら教えてください。


とりあえず大半は以下を参考にしました。
http://www.mm.media.kyoto-u.ac.jp/members/a_hasimoto/boostgraphlib/HEAD/libs/graph/doc/table_of_contents.html


stanford_graphは、SGBのソースコードをbglに適合出来るようにしたもんです。
C++でSGBを扱うときはこれを使うといいです。
SGBのソースコードはLiterate Programmingというパラダイムによって記述されてます。
リファレンスとソースコードを一緒にしてしまった感じ。
どんなんかっつーと、まぁソース見てもらうと分かるんですけど、(gb_basic.wとか)
texC言語の記述がごっちゃになってますね。
cweaveでtex形式に変換できます。
でこれplatexとかで変換しようと思ったんですけどうまくいかないですね。
なんでじゃいあん


・実行環境構築
Ubuntuだとcwebとsgbがaptで用意されてるんで、それをいれるだけでOK。
cwebはいるのかなぁ。もしかしたらいらないかも。
コンパイルする時は

g++ hoge.cc -l gb

つってライブラリ指定すんの忘れないでね


・使ってみる

インクルード

#include <boost/graph/stanford_graph.hpp>

何故か俺の環境では、他のbglヘッダのインクルードの順番によってはコンパイルエラーになる。
とりあえずこのstanford_graphは最後に持ってくるといいっぽい。
あと、SGBのヘッダは二重インクルード防止をしていないため、
この前後にgb_basic.hとかをインクルードしちゃだめ。


以下から名前空間は省略。


グラフ読み込みと破棄は次の様に行う。
gt-itmで出力したファイルを使ってる。

//hoge.gbからグラフを生成
sgb_graph_ptr g = restore_graph( const_cast<char*>("ts100-0.gb") );
//グラフの破棄
gb_recycle(g);


グラフの型情報はgraph_traitsを用いて得ることが出来る。
他の情報は非メンバ関数で得る形が多い(?)

//グラフg中の頂点数
graph_traits< sgb_graph_ptr >::vertices_size_type vn = num_vertices(g);
//グラフg中の辺数
graph_traits< sgb_graph_ptr >::edge_size_type en = num_edges(g);

頂点や辺を得るときはこんな感じとか

typedef graph_traits< sgb_graph_ptr >::vertex_descriptor vertex_descriptor; //頂点
typedef graph_traits< sgb_graph_ptr >::vertex_iterator vertex_iterator; //頂点イテレータ
typedef pair< vertex_iterator , vertex_iterator > vertex_range; //gの持つ頂点への範囲イテレータ
typedef graph_traits< sgb_graph_ptr >::edge_descriptor edge_descriptor; //辺

vertex_range vr = vertices(g); //グラフgの頂点への範囲イテレータを得る
vertex_descriptor v = *vr.first; //グラフgの先頭の頂点を得る
edge_descriptor ed = *out_edges( v , g ).first; //グラフg中にある頂点vが持つ最初の辺を得る


頂点の名前や辺の長さを得るためには、プロパティを用いる。
この辺がよくわからず泣きそうになった。むじゅい。
プロパティタグは、頂点や辺から取り出すデータの種類を指定する。
edge_length_tであればエッジの長さであったり、
vertex_name_tであれば頂点の名前を指定することが出来る。
注意として、
http://www.mm.media.kyoto-u.ac.jp/members/a_hasimoto/boostgraphlib/HEAD/libs/graph/doc/PropertyTag.html
に定義されてるタグが並んでるけど、
SGBで保持していないデータはタグを指定しても取得する事が出来ない。
例えば、edge_weight_tはSGBのGraphに対しては無効。コンパイルエラーになる。


プロパティマップは、プロパティタグで指定したデータを得る型を生成出来る。

//グラフg中の頂点の名前を取得するプロパティマップを取得
sgb_vertex_name_map name_map = get( vertex_name_t() , g );
//頂点vの名前を標準出力
cout << name_map[v] << endl;
//グラフg中の辺edの長さを標準出力
cout << get( edge_length_t() , g ,ed ) << endl; 

vertex_name_tとかgetで頂点を直接指定出来なかったり、こーいううざいのが時々ある。


値をセットする時はputを用いる

//グラフg中の辺edの長さに12をセットする
put( edge_length_t() , g , ed , 12 );


SGBの頂点は、利用者が自由に使用できる6つのutility field(u,v,w,x,y,z)を持っている。
dijkstraの距離の保存場所などに利用する。
utility fieldはSGBではunionとして定義されており、型は以下に制限される。


・Vertex* (graph_traits< sgb_graph_ptr >::vertex_descriptorはVertex*のtypedef)
・Arc*
・Graph*
・char*
・long


stanford_graphでは、このutility fieldにもプロパティマップとプロパティタグを用いてアクセスする。

//グラフgの頂点vが持っているutility uに保持されているlong型の値を標準出力
put( u_property<long>() , g , v ) << endl;
//グラフgの頂点vが持っているutility wにchar*型の値を代入
put( w_property<char*>() , g , v , const_cast<char*>("hoge") );

ちなみに、SGBの辺も同様のutility fieldを2つ(a,b)を保持している。




俺が使った範囲で基本的な所はこんなもんかなぁ。
一応、sgbのgraphでdijkstra_shortest_pathsを使おうと思ってかなりつまったので紹介。
辺の重みにはグラフの辺の長さを指定し、
距離の保持にはutility fieldを用いた。

 dijkstra_shortest_paths( g, v,
    	 distance_map(get( u_property<long>(), g)).
    	 weight_map(get(edge_length_t(), g))
    	 );

ここで、自分の環境の場合、

/usr/include/boost/graph/dijkstra_shortest_paths.hpp:375: error: no matching function for call to ‘vertices(Graph* const&)’

コンパイルエラーが出た。


verticesはstanford_graph.hppで定義されているので、
インクルードの順番が悪いのかなぁ。

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/stanford_graph.hpp>


しかし、stanford_graph.hppをdijkstra_shortest_path.hppの手前に持ってくると、
もっといっぱいエラーが出てくる。

In file included from /usr/include/boost/graph/dijkstra_shortest_paths.hpp:20,
                 from 3main.cc:14:
/usr/include/boost/graph/named_function_params.hpp:402: error: expected ‘,’ or ‘...’ before ‘.’ token
/usr/include/boost/graph/named_function_params.hpp: In function ‘typename boost::detail::override_const_property_t<typename boost::parameter::value_type<ArgPack, Tag, int>::type, Prop, Graph, boost::detail::parameter_exists::value>::result_type boost::detail::override_const_property(const ArgPack&)’:
/usr/include/boost/graph/named_function_params.hpp:408: error: ‘g’ was not declared in this scope
/usr/include/boost/graph/named_function_params.hpp:408: error: ‘t’ was not declared in this scope
/usr/include/boost/graph/named_function_params.hpp: At global scope:
/usr/include/boost/graph/named_function_params.hpp:430: error: expected ‘,’ or ‘...’ before ‘.’ token
/usr/include/boost/graph/named_function_params.hpp: In function ‘typename boost::detail::override_property_t<typename boost::parameter::value_type<ArgPack, Tag, int>::type, Prop, Graph, boost::detail::parameter_exists::value>::result_type boost::detail::override_property(const ArgPack&)’:
/usr/include/boost/graph/named_function_params.hpp:436: error: ‘g’ was not declared in this scope
/usr/include/boost/graph/named_function_params.hpp:436: error: ‘t’ was not declared in this scope
/usr/include/boost/graph/named_function_params.hpp: At global scope:
/usr/include/boost/graph/named_function_params.hpp:468: error: expected ‘,’ or ‘...’ before ‘.’ token
/usr/include/boost/graph/named_function_params.hpp:495: error: expected ‘,’ or ‘...’ before ‘.’ token
In file included from /usr/include/boost/graph/dijkstra_shortest_paths.hpp:25,
                 from 3main.cc:14:
/usr/include/boost/pending/relaxed_heap.hpp: In member function ‘void boost::relaxed_heap<IndexedType, Compare, ID>::pair_transform(boost::relaxed_heap<IndexedType, Compare, ID>::group*)’:
/usr/include/boost/pending/relaxed_heap.hpp:462: error: expected initializer before ‘.’ token
/usr/include/boost/pending/relaxed_heap.hpp:463: error: ‘u’ was not declared in this scope

よくわからんので、インクルードの順番はいじらずにverticesを再定義する方向で無理やり回避した。

//stanford_graph.hppのverticesと同様のを再定義
std::pair<sgb_vertex_iterator,sgb_vertex_iterator>
    vertices(boost::sgb_const_graph_ptr g)
{
    return std::make_pair(sgb_vertex_iterator(g->vertices),
                           sgb_vertex_iterator(g->vertices + g->n));
}

解決方法があったら教えてくだしぁ


あーそれと、自分のdijkstraの場合、距離だけでなく
それにかかったホップ数も保持したかったので、
dijkstra_visitorを継承してedge_relaxedを上書きした。
以下それ。


typedef boost::u_property<long> hop_property;
typedef boost::v_property<Vertex*> predecessor_property;
typedef boost::w_property<long> distance_property;

//predecessorとhop数を保存する
template <class PredecessorMap >
class record_predecessor_and_hop : public boost::dijkstra_visitor<>
{
public:
    record_predecessor_and_hop( PredecessorMap p )
            :predecessor(p){}

    template< class Edge , class Graph >
    void edge_relaxed( Edge e , Graph g )
    {
        //predecessorの保存
        put( predecessor , target(e,g) , source(e,g) );
        //hopの保存
        put( hop_property() , g , target(e,g) , get( hop_property() , g , source(e,g) ) + 1 ); 
    }
protected:
    PredecessorMap predecessor;
};

//record_predecessor_and_hopを生成する便利関数
template <class PredecessorMap>
record_predecessor_and_hop<PredecessorMap> make_predecessor_and_hop( PredecessorMap p)
{
    return record_predecessor_and_hop<PredecessorMap>(p);
}

hop_propertyとか直で指定せず、
テンプレートとかで置き換えた方がいいのかもしれないけれどもまぁそれはまた今度だ。


で、いざdijkstraに使ってみる。

//ホップ数の保存もしつつdijkstra
dijkstra_shortest_paths( g, v,
    visitor( make_predecessor_and_hop( get( predecessor_property() , g ) ) ).
    distance_map(get( distance_property(), g)).
    weight_map(get(edge_length_t(), g))
    );