Boost.Graphを使う

C++でグラフ構造を、しかもグラフ理論的なアルゴリズム（ワーシャル-フロイド法(Warshall-Floyd, WF法)とか）を使う必要があって、Boost.Graphを使うことになった。
Boost.Graphライブラリは、Boostの数あるライブラリの中でも、やばいライブラリのうちの一つ。Boost沼の一つ。やばい原因はその汎用性の高さにある。
汎用性がめちゃくちゃ高いため、普通に「よーし使うぞー」と思った時には、まず次のような呪文を唱えなくてはならない。

typedef boost::adjacency_list&lt;
    boost::listS, boost::vecS, boost::directedS,
    boost::property&lt;boost::vertex_name_t, std::string&gt;
    boost::property&lt;boost::edge_weight_t, float&gt;&gt; Graph;

上のコードは、頂点に名前、辺に重みを持つ有向グラフを表す。テンプレート引数の最後の２が、頂点に対するプロパティと辺に対するプロパティ。この例だと、頂点に対し、プロパティとして頂点名をstd::string型で指定、辺に対し、プロパティとして重みをfloat型で指定している。ここの指定の仕方を変えることで、様々なグラフを表現することができる。
細かい使い方は他のブログ等を参照してもらうとして、今回ここで書くのは、各頂点に対して複数のプロパティを持たせる方法。
例えば、頂点に名前（ラベル）と何かの確率の値を持たせたいとする。この場合、Boost::Graphへの独自のproperty追加とdynamic_propertiesを使ったdotファイル読み込みを参考に、

namespace boost{
  enum vertex_probability_t{vertex_probability};
  BOOST_INSTALL_PROPERTY(vertex,probability);
}

という風に型を定義しておく。問題は、どうやって複数のプロパティを頂点に割り当てるか。
ここで、再帰的なテンプレートが使われる。実は、boost::property<>はlispのリストみたいに作られていて、

boost::property&lt;boost::vertex_name_t,std::string,boost::property&lt;boost::hogehoge_t, int, boost::property&lt;boost::foobar_t, float&gt;&gt;&gt;

のように利用できる。これを使って

typedef boost::adjacency_list&lt;
    boost::listS, boost::vecS, boost::directedS,
    boost::property&lt;boost::vertex_name_t, std::string, boost::property&lt;boost::vertex_probability_t, float&gt;&gt;,
    boost::property&lt;boost::edge_weight_t, float&gt;&gt; Graph;

とすることで、名前と確率を頂点に持たせたグラフを作ることができる。

コメントする コメントをキャンセル

コメントするコメントをキャンセル