Boost.Graph make_function_property_mapの例

先日の「動的な辺の重みで最短経路探索する」で使用したboost::function_property_mapですが、ヘルパ関数があったので使ってみました。
以下は、重みを全て1として扱う、最短単純路(通った辺の数が最も少ない経路)を求めるプログラムです。
(先日は固定で3を返していたのを、1にしただけです。先日のも全て同じ重みなので、最短単純路です。)

#define BOOST_RESULT_OF_USE_DECLTYPE
#include <iostream>
#include <vector>
#include <deque>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/function_property_map.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS> Graph;
typedef std::pair<int, int>                         Edge;
typedef boost::graph_traits<Graph>::edge_descriptor EdgeDesc;
typedef int Vertex;

enum { S, A, B, C, D, E, F, G, Z, N };
const std::string Names = "SABCDEFGZ";

// グラフを作る
Graph make_graph()
{
    const std::vector<Edge> edges = {
        {S, A},
        {A, B},
        {B, C},
        {B, D},
        {C, E},
        {D, G},
        {E, D},
        {G, E},
        {E, F},
        {F, Z},
        {G, Z},
    };

    return Graph(edges.begin(), edges.end(), N);
}

int main()
{
    const Graph g = make_graph();
    const Vertex from = S; // 開始地点
    const Vertex to = Z; // 目的地

    // 最短経路を計算
    std::vector<Vertex> parents(boost::num_vertices(g));
    boost::dijkstra_shortest_paths(g, from,
        boost::predecessor_map(&parents[0]).weight_map(
            boost::make_function_property_map<EdgeDesc>([](EdgeDesc){ return 1; })
        ));

    // 経路なし
    if (parents[to] == to) {
        std::cout << "no path" << std::endl;
        return 1;
    }

    // 最短経路の頂点リストを作成
    std::deque<Vertex> route;
    for (Vertex v = to; v != from; v = parents[v]) {
        route.push_front(v);
    }
    route.push_front(from);

    // 最短経路を出力
    for (const Vertex v : route) {
        std::cout << Names[v] << std::endl;
    }
}

S
A
B
D
G
Z

make_function_property_mapは、テンプレート引数でedge descriptorの型を明示的に指定する必要があります。

また、ラムダ式を使用する場合、BOOST_RESULT_OF_USE_DECLTYPEをdefineしておく必要があります。関数オブジェクトの戻り値である重みの型を内部で取得するために、内部でboost::result_ofを使用しているからです。ラムダ式が生成する関数オブジェクトはresult_type型を持っていないので、boost::result_ofがdecltype実装になっていないのと、戻り値の型を取得できないのです。