hiro99ma blog: [c++]Boostのdijkstra_shortest_paths()

第3回。前回はこちら。

前回は、グラフの有向や無向の設定だけを見た。
それ以外にグラフの設定で使いそうなのが、プロパティだろう。
経路探索する場合は、vertexとvertexのつながりだけでなく、経路の取捨選択に用いる情報を付加することが多いからだ。
よくあるのは、距離とか、そこを通るのにかかる費用とか。

距離のような単純な情報であればboostが用意していて、edgeのプロパティとして

boost::property<boost::edge_weight_t, int>

などと書いてあげればよい(これはint型の重み)。

ただ、重みの情報は1つだけど、そのルートを通るようになった場合に参照したくなる情報もある。
さっきの例でいえば、重みとしては距離を使うけれども、経路が分かった後には通行料を知りたい、などという場合だ。
そういうときは、自分でプロパティを設定できるようである。

https://boostjp.github.io/tips/graph.html#bundle-property
ここでは、structを作ってプロパティにしている。
何でもいいのかな？
まあ、C++のtemplateはマクロみたいなものだったと思うので、ちょっと種類が異なるグラフ型を作ると、それに関連する関数も新たに作ることになってしまうのだと思うが。

試して分かったが、このプロパティにする型だが、関数内に書いてはダメだった。
グローバルスコープじゃないと展開できないのだろう(私はC++にあまり詳しくないので、推測だ)。

あとは真似をしておけばdijkstraで経路探索したり、距離を表示させたりすることはできた。
しかし、サンプルではせっかくedgeにもプロパティを付けてTokyoやNagoyaを設定しているのに、表示するときには固定文字列を使っている。
かといって、map[v1].nameなどと指定するだけでは芸が無い気もする。

それに、これは2点間だからよいが、複数のvertexがあって経路探索した場合は、どの経路を通ったかをもらって、そこからプロパティを取得していきたいではないか。

https://boostjp.github.io/tips/graph.html#dijkstra-shortest-paths
経路探索して、その経路を出力するサンプルがこちらだ。
プロパティはedgeだけで、int型になっている。
そして経路出力しているところを見ると、parentという変数を使っている。
使われ方は・・・ああ、プロパティサンプルのdistanceと同じ立ち位置なのか。

ただ、プロパティのサンプルではboost::weight_map()を使っているが、ここではboost::predecessor_map()を使っている。
dijkstra_shortest_paths - boostjp
weight_map()はINで、predecessor_map()はOUTだ。
INなのに、なぜ・・・。

あ、dijkstra_shortest_paths()が長いので気がつかなかったが、引数は3つしかないんだ。
そして、第3引数はxxx_map()がドットでつながっている。

Boost Graph Library: Dijkstra's Shortest Paths - 1.65.0

引数が3つのタイプは、これだ。

// named parameter version
template <
         typename Graph,
         typename P,
         typename T,
         typename R>
void dijkstra_shortest_paths(
         Graph& g,
         typename graph_traits<Graph>::vertex_descriptor s,
         const bgl_named_params<P, T, R>& params
);

最後のparamsが、xxx_map()が連鎖しているところになる。
引数が多いタイプも合って、そっちはnon-named parameter versionと呼ばれている。
あまり読んでないが、ここに書いてあるxxx_map()をどんどんつないでいって、指定したいものだけ指定すれば応じた結果が得られるということだろう。

プロパティのサンプルは、こう。

weight_map().distance_map()

経路を求めるサンプルは、こう。

predecessor_map().distance_map()

プロパティのサンプルは重みを別のところから取ってくるからweight_map()を使っているのだろうか。
しかし、それならプロパティにHighwayを指定しなくてもなんとかなるんじゃ無かろうか、と思ったが、それはコンパイルエラーになった。
ではweight_map()だけ外したらどうなるかと思ったら、それはdistance_map()がわからんと言われた。
distance_map()は「UTIL/OUT」になっているから、オプション扱いで、何かの後ろに付けるということか。

weightは任意のプロパティから指定したい、経路の情報は欲しい、ということであれば、こんな感じにするとよいのか。

    std::vector::vertex_descriptor> pred(num_vertices(map));
    std::vector distance(boost::num_vertices(map));
    boost::dijkstra_shortest_paths(map, v1,
            boost::weight_map(boost::get(&Highway::distance, map)).
            predecessor_map(&pred[0]).
            distance_map(&distance[0]));

検証は、次回だ。

hiro99ma blog

2017/09/01

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

0 件のコメント:

コメントを投稿