Boost.Graph 最短経路を計算する過程を取得

Boost.GraphにはEvent Visitorという機能があって、最短経路を計算するアルゴリズム内の各ポイントの情報を取得することができます。
ここでは、ダイクストラ法の最短経路計算で、頂点を調べる順番を調べてみます。

#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/assign/list_of.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int>                           Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;

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

struct path_history_visitor {
    typedef boost::on_discover_vertex event_filter;
   
    template<typename Vertex, typename Graph>
    void operator()(Vertex v, const Graph&) const
    {
        std::cout << Names[v] << ' ';
    }
};

Graph make_graph()
{
    const std::vector<Edge> edges = boost::assign::list_of<Edge>
        (S, A)
        (A, B)
        (B, C)
        (B, D)
        (C, E)
        (C, F)
        (D, F)
        (E, D)
        (F, E)
        (E, Z)
        (F, Z)
    ;

    const std::vector<int> weights = boost::assign::list_of
        (3)
        (1)
        (2)
        (3)
        (7)
        (12)
        (2)
        (11)
        (3)
        (2)
        (2)
    ;

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

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

    // ダイクストラ法で最短経路を計算
    boost::dijkstra_shortest_paths(g, from,
            boost::visitor(boost::make_dijkstra_visitor(path_history_visitor())));
}

S A B C D E F Z 

小さいグラフなせいか何もおもしろくない結果ですが、他の最短経路アルゴリズムとか大きめのグラフを使う場合にこれを使うとアルゴリズムの動作を視覚化することが簡単にできそうな気がします。

ここでは、on_discover_vertexという頂点を通過する際に呼ばれるVisitorを使っていますが、他にもいろいろなイベントをとることができます。

参照：
Event Visitor Concept - Boost Graph Library