Boost::Graphへの独自のproperty追加とdynamic_propertiesを使ったdotファイル読み込み

これはC++ Advent Calendar 2012の5日目の記事です。

はじめに

気づくと最新のエントリが去年のAdvent calenderとなっていて一年ぶりの記事になってますね．
やはりtwitterを始めるとblog書かなくなるというのは本当ですね．（そして迫る修士論文
今回は，去年と同じようにBoost::Graphに関する日本語情報の少ない機能について補完してきたいと思います．
本当であれば実装を追いたかったのですが，少し時間がないため使い方程度の記事としたいと思います．
本エントリでは，

グラフに任意のプロパティを追加
追加したプロパティをdynamic_propertiesを使ってdot(graphviz)形式で入出力

といった話をしようと思います．

グラフに任意のプロパティを追加

Boost::Graphでは，グラフの頂点やエッジに付加情報をつけるために，Boost::propertyを使っています．
デフォルトでは以下のpropertyが定義されています．

  struct vertex_index_t { };
  struct vertex_index1_t { };
  struct vertex_index2_t { };
  struct edge_index_t { };
  struct graph_name_t { };
  struct vertex_name_t { };
  struct edge_name_t { };
  struct edge_weight_t { };
  struct edge_weight2_t { };
  struct edge_capacity_t { };
  struct edge_residual_capacity_t { };
  struct edge_reverse_t { };
  struct vertex_distance_t { };
  struct vertex_root_t { };
  struct vertex_all_t { };
  struct edge_all_t { };
  struct graph_all_t { };
  struct vertex_color_t { };
  struct vertex_rank_t { };
  struct vertex_predecessor_t { };
  struct vertex_isomorphism_t { };
  struct vertex_invariant_t { };
  struct vertex_invariant1_t { };
  struct vertex_invariant2_t { };
  struct vertex_degree_t { };
  struct vertex_out_degree_t { };
  struct vertex_in_degree_t { };
  struct vertex_discover_time_t { };
  struct vertex_finish_time_t { };

いろいろとありますが，いくつかはRead onlyなmapなので(indexなど），
頂点に重みがあるようなグラフ（頂点が都市を表していてその人口など）では，
vertex_weight_tなどわかりやすいpropertyを自分で追加したくなるのではと思います．
例えばvertex_weight_tをグラフに追加するためには以下のようにboost名前空間に自分でタグを追加します．

namespace boost{
  enum vertex_weight_t{vertex_weight};
  BOOST_INSTALL_PROPERTY(vertex,weight);
}

こうして追加したpropertyは，デフォルトで定義されているpropertyと同じように，グラフの定義で追加し，
boost::get/putで操作することができます．

typedef boost::adjacency_list<
  boost::listS, boost::vecS, boost::undirectedS,
  boost::property<boost::vertex_weight_t, int>,
  boost::no_property > MyGraph;//グラフに独自に定義したpropertyを追加

  MyGraph g;
  int num = 0;
  boost::get(boost::vertex_weight,g,0);
  boost::put(boost::vertex_weight,g,0,num);

追加したプロパティをdynamic_propertiesを使ってdot(graphviz)形式で入出力

このように，独自のpropertyをグラフに追加することができましたが，
次はこれを入出力することを考えてみたいと思います．
今回，グラフの表現フォーマットとして，古くからあるdot(graphviz)形式での入出力を考えます．

graph G {//入力したいdotファイル
0[label=A][vweight=1];//各頂点に重み属性が付与されている(vweight)
1[label=B][vweight=2];
2[label=C][vweight=3];
3[label=D][vweight=4];
4[label=E][vweight=5];
5[label=F][vweight=6];
0--1 ;
1--2 ;
3--4 ;
4--5 ;
0--3 ;
1--4 ;
2--5 ;
}

read_graphvizを使ったdotファイルの入力

Boost::graphには，dot形式での入出力用のAPIが用意されています．

namespace boost {

  template <typename MutableGraph>
  bool read_graphviz(std::istream& in, MutableGraph& graph,
                     dynamic_properties& dp,
                     const std::string& node_id = "node_id");

  template <typename MutableGraph>
  bool read_graphviz(std::string& str, MutableGraph& graph,
                     dynamic_properties& dp,
                     const std::string& node_id = "node_id");

  template <typename InputIterator, typename MutableGraph>
  bool read_graphviz(InputIterator begin, InputIterator end,
                     MutableGraph& graph, dynamic_properties& dp,
                     const std::string& node_id = "node_id");

}

上のAPIを見ると，boost::dynamic_propertiesというのが登場していることがわかります．
詳細についてはリファレンスを参照してほしいのですが，簡単なイメージで説明すると，
これは，ファイルからのデータ入力などコンパイル時に入力データの型を静的に決定できないものを
boost::propertyを使って扱うために用意されているシステムです．
boost::propertyをvalue,stringをkeyとしたproperty mapのようなインターフェイスとなっており，
dot形式ファイルをランタイムで読み込む際には，dot形式における属性をkey,その属性をputしたい先の
graphに付与されたpropertyをvalueとしたdynamic propertyをread_graphvizに渡すことで
dotファイル中で属性の記述を発見した時に自動的に指定したpropertyにputしてくれるようになります．

また，APIを使ってdotファイルから読み込みを行う際には，独自に定義した属性だけでなく，
dotファイル暗黙的に存在するnodeidを処理する必要があります．
read_graphvizでは，これを属性として捉えてパースするため，
暗黙的なnodeidをなんという属性名にするか(key側），そしてそれをどのpropertyに紐付けるかの設定が必要です．

int main()
{ 
  MyGraph g;
  boost::dynamic_properties dp;

  //以下gに追加されているpropertyとkeyを関連付け（vertex_node_id/vertex_weightは独自定義タグ）
  dp.property("node_id",boost::get(boost::vertex_node_id,g));//暗黙的なnode_idをvertex_node_idに割り当て
  dp.property("label",boost::get(boost::vertex_name,g));//自分で追加した属性
  dp.property("vweight",boost::get(boost::vertex_weight,g));//自分で追加した属性


  std::ifstream infile("test.dot");
  read_graphviz(infile,g,dp,"node_id");//最後の引数で暗黙的なnodeidを"node_id"というkeyとして扱うと宣言
                                                                                                         
  return 0;
}

上のようにすることで，dotファイルの属性をgraphのpropertyに入力することができます．
上ではやっていませんが，read_graphvizでは，渡されたdynamic_propertiesのkeyとして設定されていない，
属性を発見すると例外を吐くので，try-catchをきちんとするか，もしくはunknown itemを発見した場合に
呼ばれるファンクタを適切に設定してやる必要があります．
また，出力に関してもdynamic_propertiesを同様に使う方法と，エッジ及び頂点の書き出し用関数用オブジェクトを指定する方法の２つが用意されています．

最後に

今回は独自propertyの定義とdynamic_propertiesを使ったdotファイルの読み込みについて解説しました．
本当は，細かい実装や，独自のVisitorで探索アルゴリズムの拡張などまで書きたかったのですが，
いま余裕がないのでまた今度文章にしたいと思います．それでは！