2017/09/02

[c++]Boostのdijkstra_shortest_paths() - 4

前回は、dijkstra_shortest_paths()に重みを指定しつつ、経路を得るための引数を指定するところまでだった。
なんであんな中途半端で終わらせたかというと、仕事に行く時間だっただけだ。。。

動作結果は、OKだった。
検証したソースを載せたいところだが、そっちは仕事で書いているコードでやってしまったのだ。すまん。


第3引数には他の種類もある。
こちらでは、visitor()というものを使っている。
Boost.Graphに入門 - Faith and Brave - C++で遊ぼう
やっていることは同じような内容なのだが、最短経路以外にも試されている。


BoostのGraphは自由度が高いので、あれこれできてしまい、検索して見たサイトで全部やり方が違っていて「うーん、難しい・・・」と感じてしまう。

ただ、便利だし、Cから使うときもそこだけライブラリにしておけばうまいことやれるんじゃなかろうかと思う。
Makefileで、CとC++を混在させるやり方がよくわからんのだ。。。
.oを.cやら.cppに見立てる方式ではダメだから、最近はソースファイル名を列挙する方式にしているのだけど、extern "C"だけでうまく回避できるんだっけ?


いかんいかん、話が逸れてしまった。
ともかく、BoostのGraphは、大ざっぱに言えば、

  • adjacency_list<>でグラフを構成する型を作る
  • そのインスタンスを作って、vertexやedgeを突っ込んでいく
  • アルゴリズムを実行
  • 結果を得る

という流れのようだ。

そして、vertexやedgeは単純なものであれば元からある型を使えばよいし、プロパティとして複数の情報を持たせたければ構造体などを指定すればよい。
プロパティを自前で用意する場合は、重みをweight_map()で指定する。
距離の結果を得たい場合はdistance_map()を、経路の結果を得たい場合はpredecessor_map()を指定する。

私が使う範囲では、このくらいわかっておけばよさそうだ。

0 件のコメント:

コメントを投稿

コメントありがとうございます。
スパムかもしれない、と私が思ったら、
申し訳ないですが勝手に削除することもあります。