2011-12-21
これは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
2011-10-03
VirtualBoxのウィンドウなし起動と自動サスペンドスクリプト
最近MacBook Air 11'(Mid 2011)を買いました！
いまだ環境構築中ですがとりあえず
仮想化については、Winの頃使っていたVirtualBoxを使うことにしました。
macのvirtualboxでは、winでは割と上手く動かなかったウィンドウ無し起動などが
ちゃんと動くようなのでちょっと試してみました。
ウィンドウ無し起動
/Applications/VirtualBox.app/Contents/MacOS/VBoxManage
があり、
これを使うとGUIからではできない動作ができます。
ウィンドウ無しでの起動は
VBoxManage startvm [vm名] --type=headless
のように、--type=headlessをつければよいようです。
普段ssh越しでしかVMにアクセスしない場合は割と便利なんじゃないかと思います。
自動サスペンド
MBA11'は割と電池持ちに問題があるので、
開発用のVMにパワーを持っていかれると辛いので
ssh接続からVMサスペンドからの復帰、sshを切るとVMを自動でサスペンド
してくれるようなスクリプトを作ってみました。
#! /bin/sh VBoxManage controlvm $1 resume ssh $1 remain=`ps -e -o args | grep -c "^ssh.*$1"` if [ $remain -eq 0 ];then VBoxManage controlvm $1 pause echo vm paused. fi echo bye
#使い方 sshv.sh [vm名] VBoxManage controlvm [vm名] pauseでサスペンド VBoxManage controlvm [vm名] resumeでサスペンドからの復帰
該当VMに対するssh接続の有無を確認、他に接続しているコネクションがなければ
割と自分用にぱっぱと作ったのでいろいろあれですが（sshの残コネクションの判断など）
何かの参考になればと思います。
今回紹介した以外にも、VBoxManageではいろいろなことができるようなので
探してみると便利なんじゃないかと思います。
Permalink | コメント(0) | トラックバック(0) | 08:26
2010-10-14
gitまとめ
思い出し次第どんどん追記
基本的な設定
git config --global user.name Name git config --global user.email mail@addr git config --global core.editor emacs git config --global color.ui true
Permalink | コメント(0) | トラックバック(0) | 11:27
2010-10-09
Unixからシリアルポートに接続
個人的なメモとして
aptitude install cu
物理COMポートを使う場合は
dmesg | grep tty
などでどこに割り当てられたか確認
cu -l /dev/ttyS0 -s 115200
で接続
permission deniedとか出てきたら
/dev/ttyS0にchmodとかで適切な権限を
cuから抜けるには接続中に
~.
でOK
Permalink | コメント(0) | トラックバック(0) | 04:55
2010-08-30
sinatraのerrorハンドリング
最近sinatraでwebアプリケーションを作ってたりするんですが
ちょっとうまくいってないのでメモ。
ルートハンドラの中で例外をraiseした場合に
チュートリアルによると、errorハンドラで受け取れるよとあったのでやってみてもうまく動かない
具体的には
require 'rubygems' require 'rubygems/gem_runner' require 'sinatra' require 'erb' error do 'Sorry there was a nasty error - ' + env['sinatra.error'].name end get '/' do raise 'test' end
こんな感じにすると、errorに飛ばずに普通にランタイムエラーで落ちる。
ちなみに、ステータスコードに対応するerrorハンドラを以下のように追加した場合
error 403 do erb "403 dayo" end get '/403' do 403 end
これだときちんと動作する（403 dayo)と表示される
なにか使い方が大きく間違ってるような気がするので誰かわかる人いたら教えてください。
Permalink | コメント(0) | トラックバック(0) | 05:29
