C++のメモ

Boost.Graphは

• グラフ構造のコンテナ
• グラフに対するアルゴリズム

を提供する．

問題点として，

• ドキュメントが不十分である
• 全てのクラス，関数が名前空間boost::graphではなくboostに置かれている
• First Releaseが1.18と古いため最新のboostの機能，例えばboost.parameters，を利用できていない
• 引数でgraphを受ける位置が関数によって異なる．操作系: 最後，プロパティ系: 2番目

が挙げられる．

http://www.boost.org/doc/libs/1_55_0/libs/graph/do...

bidirectionalを双方向と訳すと矢印が両端についているイメージで，undirectedと区別がつかない．

directed: vertexは出て行くエッジ(out_edge)のみを保存する
bidirected: 入ってくるエッジ(in_edge)も保存する

可読性を考えるとbundle propertyを用いる方がよい．

struct vertex_property_t
{
  std::string node_name;
  int node_data;
};

struct edge_property_t
{
  std::string edge_name;
  int edge_data;
};

void graph_use_bundled_property()
{
  typedef boost::adjacency_list<boost::listS, boost::vecS, vertex_property_t, edge_property_t> graph_t;
  graph_t g;
  graph_t::vertex_descriptor node1 = boost::add_vertex(g);
  g[node1].node_name = "first node";
  g[node1].node_data = 4;

  graph_t::vertex_descriptor node2 = boost::add_vertex(g);
  g[node1].node_name = "second node";
  g[node1].node_data = 9;
  
  graph_t::edge_descriptor edge_1_2 = boost::add_edge(node1, node2, g);
  g[edge_1_2].edge_name = "first edge";
  g[edge_1_2].edge_data = 52;

  std::cout << g[node1].node_name << std::endl;
  std::cout << g[node1].node_data << std::endl;
  std::cout << g[edge_1_2].edge_name << std::endl;
  std::cout << g[edge_1_2].edge_data << std::endl;
  return 0;
}

vertex_descriptorはvertex_list_typeがvecSの場合はvectorの要素番号である．
listSを選んだ場合は，vertex_descriptor = void* である．

vertex_listがvecSの場合，std::vector<T>::eraseが実行されるため，依存のvertex_descriptorは無効化される．
厳密には，詰められるため，削除以降の番号がずれる．
例えばname->vertex_descriptorの逆引き辞書を保存している場合は，再構成する必要がある．
listSの場合，removeによって逆引き辞書は無効化されない．

それぞれのルールで指定したノードから順に探索する．
visitorを与えて，各イベント時に処理を行うことができる．
生じるイベントはsearchアルゴリズムによって異なる．

vertes_list = listSの場合，color_mapを指定する必要がある．

struct vertex_property_t
{
  boost::default_color_type color;
};

struct on_tree_edge : public boost::default_bfs_visitor
{
  template <class Edge, class Graph>
  void tree_edge(Edge e, Graph const& g)
  {
    // write your code here
  }
};

void func()
{
  typedef boost::adjacency_list<boost::listS, boost::listS, vertex_property_t> graph_t;
  graph_t g;

  // build graph

  on_tree_edge vis;
  boost::breadth_first_search(g, first_node, boost::color_map(boost::get(&vertex_property_t, g)).visitor(vis));
}