ばるの日記

これはBoost Advent Calendar 2011の21日目の記事です。

はじめに

今回は自分が本格的にBoost.Graphを使う必要ができたときにぐぐっても意外と情報の少なかった

頂点や辺を動的に追加したり削除する方法や注意点について書きたいと思います．

まず，WebでBoost.graphの日本語情報を探すと，以下のようなものが多いと思います．

//ちょうどよかったのでid:futadaさんのコードを引用させて頂きます．

たとえば、3個のvertexからなり、vertex 0 -> 1、0 -> 2、1 -> 2の3個のエッジを持つ有向グラフのデータをBoost.Graphを使って作るには以下のようなコードになります。

#include <vector>
#include <boost/graph/adjacency_list.hpp>

int main()
{
  std::vector<std::pair<int, int> > edge_list = {{0, 1}, {0, 2}, {1, 2}};
    
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property,
				boost::no_property,
				boost::no_property> Graph;

  Graph graph(edge_list.begin(), edge_list.end(), 3); // コンストラクタの引数は、エッジイテレータの最初, 最後, vertex数の順

  return 0;
}

http://d.hatena.ne.jp/futada/20111220/1324389070

上のコードでは，コンストラクタでグラフを構築しています．

執筆者の意図として，より細かいアルゴリズムの適用などを見せたいというのがあるのであれば

グラフの構造についてコード中にstaticに記述してしまうのは妥当だと思いますが，

実際Boost.Graphを使う場合はこのように構造をコード中に記述することはあまりないと思います．

（実際使い始めるときに一番自分が躓いたのはここでした）

コンストラクタ以外で頂点や辺を追加

普通に実用するとコンストラクタでない場所で頂点や辺を追加したくなるわけですが，

それを行うには以下のようにadd_edgeとadd_vertexを使うことになります．

#include <boost/graph/adjacency_list.hpp>

enum {VA,VB,VC};
int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property, boost::no_property> Graph;
  
  Graph graph;
  
  for(int i = 0;i < 3;++i)
    boost::add_vertex(graph);
  
  boost::add_edge(VA,VB,graph);
  boost::add_edge(VA,VC,graph);
  boost::add_edge(VB,VC,graph);
  
  return 0;
}

一見これでうまく行っているように見えるのですが，実はこのコードには問題があります．

例えばここで，graphの内部の頂点配列のコンテナをlistSに切り替えた以下のコードはコンパイルエラーになります．

#include <boost/graph/adjacency_list.hpp>

enum {VA,VB,VC};
int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::listS, boost::directedS,
				boost::no_property, boost::no_property> Graph;//２つ目の引数をvecSからlistSに変更
  
  Graph graph;
  
  for(int i = 0;i < 3;++i)
    boost::add_vertex(graph);
  
  boost::add_edge(VA,VB,graph);
  boost::add_edge(VA,VC,graph);
  boost::add_edge(VB,VC,graph);
  
  return 0;
}

bash-3.2$ g++ main.cpp
main.cpp: In function ‘int main()’:
main.cpp:37: error: cannot convert ‘<anonymous enum>’ to ‘void*’ for argument ‘1’ to ‘std::pair<typename Config::edge_descriptor, bool> boost::add_edge(typename Config::vertex_descriptor, typename Config::vertex_descriptor, boost::directed_graph_helper<Config>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>::config]’
main.cpp:38: error: cannot convert ‘<anonymous enum>’ to ‘void*’ for argument ‘1’ to ‘std::pair<typename Config::edge_descriptor, bool> boost::add_edge(typename Config::vertex_descriptor, typename Config::vertex_descriptor, boost::directed_graph_helper<Config>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>::config]’
main.cpp:39: error: cannot convert ‘<anonymous enum>’ to ‘void*’ for argument ‘1’ to ‘std::pair<typename Config::edge_descriptor, bool> boost::add_edge(typename Config::vertex_descriptor, typename Config::vertex_descriptor, boost::directed_graph_helper<Config>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>::config]’

上のエラーはadd_edgeに渡す頂点記述子VA,VB（vertex_descriptor)はintではなくvoid*だよというエラーです．

いままで頂点を指定するのになんとなく０から始まる整数値を使っていたと思いますが，この頂点記述子は常にintではありません．

これを仮定する形でenumを使って簡単に頂点に名前をつけているコードなども見かけますが，

本来は以下のコードのようにadd_vertex()から返される頂点記述子をきちんと保存しておき，それを使ってadd_edgeするべきです．

#include <boost/graph/adjacency_list.hpp>
#include <map>

int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::listS, boost::directedS,
				boost::no_property, boost::no_property> Graph;
  
  Graph graph;
  std::map<int,Graph::vertex_descriptor> desc;//Graph::vertex_descriptorで頂点記述子の型を取得
  for(int i = 0;i < 3;++i)
    desc[i] = boost::add_vertex(graph);
  
  boost::add_edge(desc[0],desc[1],graph);
  boost::add_edge(desc[0],desc[2],graph);
  boost::add_edge(desc[1],desc[2],graph);
  
  return 0;
}

きちんとBoost.Graphのコードを読めていないので単なる推測ですが，

この頂点記述子はgraphが内部的に持っている頂点データのデータ構造を一意に特定できればいいはずなので，

vecSの場合はvector<Vertex>のindexになっているのではないかと思います（なのでint)

頂点の削除

次に頂点の削除について考えてみます．

頂点の削除はremove_vertexを用いて行います．

#include <boost/graph/adjacency_list.hpp>
#include <map>

int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::listS, boost::directedS,
				boost::no_property, boost::no_property> Graph;
  
  Graph graph;
  std::map<int,Graph::vertex_descriptor> desc;//Graph::vertex_descriptorで頂点記述子の型を取得
  for(int i = 0;i < 3;++i)
    desc[i] = boost::add_vertex(graph);
  
  boost::add_edge(desc[0],desc[1],graph);
  boost::add_edge(desc[0],desc[2],graph);
  boost::add_edge(desc[1],desc[2],graph);

  boost::clear_vertex(desc[0],grapg);//頂点を含む辺を削除する
  boost::remove_vertex(desc[0],graph);//頂点を削除
  
  boost::add_edge(desc[2],desc[1]);//その後辺を追加
  return 0;
}

上のようにすることで，正常に最初に追加した頂点を削除し，その後二，三回目に追加した頂点のを結ぶ辺を作ることができます．

ここで以下のように頂点のデータ構造をvecSに変更してみます．

#include <boost/graph/adjacency_list.hpp>
#include <map>

int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property, boost::no_property> Graph;
  
  Graph graph;
  std::map<int,Graph::vertex_descriptor> desc;//Graph::vertex_descriptorで頂点記述子の型を取得
  for(int i = 0;i < 3;++i)
    desc[i] = boost::add_vertex(graph);
  
  boost::add_edge(desc[0],desc[1],graph);
  boost::add_edge(desc[0],desc[2],graph);
  boost::add_edge(desc[1],desc[2],graph);

  boost::clear_vertex(desc[0],grapg);//頂点を含む辺を削除する
  boost::remove_vertex(desc[0],graph);//頂点を削除
  
  boost::add_edge(desc[2],desc[1]);//その後辺を追加...とはならない
  return 0;
}

これは意図したどおりの動作をしません．

先ほど説明したとおり，頂点記述子はgraph内部の頂点データ配列を一意に特定できる何かのはずです．

内部のデータ構造にvecS(vector)を指定した場合，記述子が配列のindexそのままとなるのであれば，

頂点を削除した際に内部のvectorが連続性を保証するため前に１つずつ詰められ，

add_vertexの際に保存した頂点記述子と内部のindexがずれることになります，

そのため，vecSを指定した場合，graphに対して削除などのオペレーションを行ったあとの頂点記述子は無効になります．

実はこの辺はgraphのドキュメントにきちんとまとめて書いてあります．

http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/adjacency_list.html

よって，頂点や辺の削除を行う予定のあるグラフを扱う場合は，

自分のユースケースに応じた適切なコンテナを指定するのが非常に重要です．

最後に自分が少し引っかかったことについて

ここまで読んでいただいて，graphにおける頂点配列コンテナの指定には，パフォーマンス以外にも

動作の違いがあることがわかってもらえたと思います．

最後に，このvecSとlistSの切り替えに関して自分が躓いたトピックについて書いておきたいと思います．

listSにするとvertex_index_tがデフォルトで付加されていない

Graphには指定しなくてもデフォルトで付与されるプロパティがあります．

しかし，指定したコンテナによっては付与されるデフォルトプロパティが異なります．

そのため，以下のgraphviz書き出しを行うコードはvecSの場合追加でプロパティを指定しなくても動作しますが，

listSを指定した場合は，write_graphvizが使用するvertex_index_tプロパティを自分で指定し，

きちんとputしてやることが必要になります．

#include <boost/graph/adjacency_list.hpp>
#include <map>
#include <boost/graph/graphviz.hpp>

int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property,boost::no_property> Graph;//vecSの場合はこれでOK
				//boost::property<boost::vertex_index_t,int>, boost::no_property> Graph;//listSの場合は必要
  
  Graph graph;
  std::map<int,Graph::vertex_descriptor> desc;//Graph::vertex_descriptorで頂点記述子の型を取得
    for(int i = 0;i < 3;++i){
    desc[i] = boost::add_vertex(graph);
    //    boost::put(boost::vertex_index, graph, desc[i], i);//listSの場合必要
    }
  
  boost::add_edge(desc[0],desc[1],graph);
  boost::add_edge(desc[0],desc[2],graph);
  boost::add_edge(desc[1],desc[2],graph);

  boost::write_graphviz(std::cout, graph);
  return 0;
}

これは，vecSでは頂点記述子をそのままvertex_index_tをして使っているためだと思います．

このように，割とlistSだと面倒な事が全体的に増えます（個人的な印象）

vecSの際に無効な頂点記述子を指定して辺の追加などを行うと新しい頂点が作成されてしまう

いままでvecSを指定したgraphに対してadd_vertexした後にadd_edgeしていましたが，

実はadd_vertexしなくてもadd_edgeできてしまいます．

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property,boost::no_property> Graph;
  
  Graph graph;
  
  boost::add_edge(0,1,graph);
  boost::add_edge(0,2,graph);
  boost::add_edge(1,2,graph);

  boost::write_graphviz(std::cout, graph);
  return 0;
}

どうやら範囲オーバーしたvertex_descriptorが与えられた場合，

新しく頂点が自動的に作成されるようです．

割とこの動作が見つけにくいバグの原因になることがあるので気をつけておくと良いと思います．

（個人的にはassertion failedになってほしい）

最後に

すごく雑多に書きましたが，基本的に自分がgraphを実用するにあたって当たった壁や理解するまで時間のかかった部分をまとめてあります．

前半webの情報は駄目だみたいなことを書いていますが，サンプルコードと実用コードは違うので，

エッセンスを短くまとめる上で頂点記述子の型をintと仮定したりするのは全く問題ないと思っています．

id:futadaさんの記事で基本的な使い方やproperty_mapについてわかりやすい解説があるので，

この記事も併せて初めてgraphを使う人への助けになればと思います．

Permalink | コメント(3) | トラックバック(0) | 23:34