LEMON Graph LibraryをMacで使う(成功とおもいきや)

前回,LEMON Graph Libraryのインストールに成功した.
と思ったが,そのライブラリを使うプログラムをコンパイルしてみたところ,うまく行かなかったのでメモ.
※この記事はLEMON Graph Libraryが悪いのではなく,brewで普通に入れたBoostと一緒に使おうとしたのが原因です
症状は,リンク時にリンカエラーで,boost::regex系の何かがないと言われる次のようなもの.

 "boost::re_detail::perl_matcher<__gnu_cxx::__normal_iterator<char const*, std
::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::all
ocator<boost::sub_match<__gnu_cxx::__normal_iterator<char const*, std::basic_st
ring<char, std::char_traits<char>, std::allocator<char> > > > >, boost::regex_t
raits<char, boost::cpp_regex_traits<char> > >::construct_init(boost::basic_rege
x<char, boost::regex_traits<char, boost::cpp_regex_traits<char> > > const&, boo
st::regex_constants::_match_flags)", referenced from:
      boost::re_detail::perl_matcher<__gnu_cxx::__normal_iterator<char const*,
std::basic_string<char, std::char_traits<char>, std::allocator<char> > >, std::
allocator<boost::sub_match<__gnu_cxx::__normal_iterator<char const*, std::basic
…

これの原因はおそらく,入れてるBoostがclangでコンパイルされているのに対して,lemonがgcc49でコンパイルされていることだと思う.
これを回避するには,Boostのbrewするときに –interactive で gcc49 を使ってインストールすれば良いと思うが,他のBoostを使っているプログラムにも影響が出そうなのでまだ試していない.

Boost.Graphでdotファイルを読み書き

昨日に引き続き、Boost.Graphの話題。
昨日はBoost.Graphを使うということで、Graphの頂点や辺に複数のプロパティを持たせることについて書いた。
今日はBoost.Graphのプロパティをファイルから読み込む方法。ここで、グラフを保持するファイルはGraphvizのdot形式とする。
dot形式は例えば

digraph G{
1 [label="A"];
2 [label="B"];
1->2 [weight=10];
}

のような形とする。
このファイルをBoost.Graphの形式で読み込むには、 #include を利用して、

//グラフの宣言
Graph g;
//グラフのプロパティ設定
boost::dynamic_properties dp(boost::ignore_other_properties);
dp.property("id",boost::get(boost::vertex_id,g)); // 自前で定義したvertex_idの型
dp.property("label",boost::get(boost::vertex_name,g));
dp.property("weight",boost::get(boost::edge_weight,g));
//グラフを読み込み
boost::read_graphviz(file, g, dp, "id");

これにより、グラフ中の1,2といった頂点の識別子をidとして、dotファイル中のlabelをlabelとして、weightをweightとして読み込むことができる。

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;

上のコードは、頂点に名前、辺に重みを持つ有向グラフを表す。テンプレート引数の最後の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;

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