Boost.Graphを使う

C++でグラフ構造を、しかもグラフ理論的なアルゴリズム(ワーシャル-フロイド法(Warshall-Floyd, WF法)とか)を使う必要があって、Boost.Graphを使うことになった。

Boost.Graphライブラリは、Boostの数あるライブラリの中でも、やばいライブラリのうちの一つ。Boost沼の一つ。やばい原因はその汎用性の高さにある。

汎用性がめちゃくちゃ高いため、普通に「よーし使うぞー」と思った時には、まず次のような呪文を唱えなくてはならない。

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::directedS,
    boost::property<boost::vertex_name_t, std::string>
    boost::property<boost::edge_weight_t, float>> Graph;

上のコードは、頂点に名前、辺に重みを持つ有向グラフを表す。テンプレート引数の最後の2が、頂点に対するプロパティと辺に対するプロパティ。この例だと、頂点に対し、プロパティとして頂点名を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;

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