Boost1.55でMultiple Source Dijkstra
この記事はC++ (fork) Advent Calendar 2013の22日目の記事になります．
今回も軽めの記事です．ご了承ください．
Boost1.55ではBoost.Graphの関数boost::dijkstra_shortes_pathsがマルチソースに対応しましたので，本記事ではこれを紹介します．
dijkstra_shortest_paths
関数dijkstra_shortest_pathsはその名前からも分かる通り，ダイクストラ法を用いた最短経路木を探索するためのアルゴリズムです．通常，ダイクストラ法ではスタート地点となる節点を一つ選択し，この節点から他の節点までの最短経路を求めます．
マルチソースの場合はスタート地点(ルート)となる節点が複数になります．実際に図で見てみるとこのようになります(見た目上枝の長さは違いますが，論理的にはすべて同じにしてます)．
二重線で囲まれている節点(ラベルが0, 20, 40, 60, 80の節点)がルートになります．
マルチソースダイクストラでは，ルート以外の節点vと，各ルート間のすべての最短経路が計算されるのではなく，経路距離が最小となるルートとの経路のみが計算されます．そのため図中ではルート以外の節点は経路距離が最小となるようなルートと同じ色で塗り分けしています．
この図はグラフのボロノイ分割と呼ばれ，勢力図等を作成するのに役立ちます．例えば，ルートを消防署と考えれば，ある節点で火事が起きた際にどこの消防署から消防車を出せばよいかの指標になります．
マルチソース版の実装で，シングルソース版との違いは探索開始時に優先度付きキューの中身に複数のルートがあるという点だけですので，容易に実装できます(私も昔作りました)．
上記のような図をboost::dijkstra_shortes_pathsを用いて作成するコードは以下になります．
A example of multiple source dijkstra.
ルート節点の指定
注目すべき箇所は関数multisource_dijkstra内のboost::dijkstra_shortest_pathsの呼び出しです．
第一引数はシングルソースの場合と同じで探索対象のグラフですが，第二，第三引数がルートとなる節点の集合を示すイテレータペアになっています(Rangeで渡したいですね!!)．シングルソースの場合は，第二引数にルートとなる節点一つを指定していた場合とは異なります．それ以外の引数はシングルソースの場合と同じです．
各節点から最短のルートの記録
ここではparent_recorderという名前のEventVisitorを新たに作成しています(root_recorderという名前にすればよかった)．これは新たに探索された節点がどのルートから探索されたかを記憶します．親(predecessorであってparentではない)のルートを自節点のルートに設定するだけです．あらかじめルートとなる節点のルートをその節点に設定しておく必要はありますが，そこは我慢します．
void operator()(Edge const e, Graph const& g) const { auto value = get(parent_map_, source(e, g)); put(parent_map_, target(e, g), value); }
getとputを合わせて一行にせずにわざわざgetで取得した値をコピーしているのは，put時にparent_map_の内部で保持するvectorのresize()が呼ばれてgetで取得した値が破棄されるのを防ぐためです(というか一行で書いて嵌りました)．
引数の数
上記のdijkstra_shortes_pathsの呼び出しでは12個の引数を指定していますが，これらを省略することはできません．
通常Boost.Graphの関数はdjikstra_shortest_pathsも含め，Named Parameter Idiomを用いた名前付き引数によってデフォルト引数を持つパラメータに対して引数を指定する必要はありません．しかしながら，マルチソースの場合名前付き引数を持つオーバロードが一つもないので，すべての引数を指定する必要があります(さらにVertexColorMapを指定するオーバロードならありました．これで引数の数は13個!!)．
使い勝手はかなり悪いので，名前付き引数版をオーバロード可能かどうか調査して追加するか独自にラッパを作成する必要がありそうです．
グラフの視覚化
出力されたファイルはgraphvizを使えばいい感じにレイアウトしてくれます.
fdp -Nstyle=filled -Nshape=circle -Nperipheries=peripheries -Tpng -O graph.dot
