boostのグラフを使って経路探索するサンプル

dijk_dist.cpp

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

struct ver_prop_t {
    std::string     name;
};

struct edge_prop_t {
    std::string     name;
    int             distance;
};

typedef boost::adjacency_list<
    boost::listS,
    boost::vecS,
    boost::bidirectionalS,
    ver_prop_t,
    edge_prop_t
> graph_t;
typedef std::pair<int, int> edge_t;
typedef boost::graph_traits<graph_t>::vertex_descriptor vertex_t;


namespace {
    vertex_t add_ver(graph_t& graph, std::string name)
    {
        typedef boost::graph_traits<graph_t>::vertex_iterator vertex_it_t;

        //登録済みかどうか確認
        vertex_t vret;
        bool ret = false;
        std::pair<vertex_it_t, vertex_it_t> ver_it = boost::vertices(graph);
        for (vertex_it_t it = ver_it.first, et = ver_it.second; it != et; it++) {
            if (graph[*it].name == name) {
                ret = true;
                vret = *it;
                break;
            }
        }
        if (!ret) {
            vret = boost::add_vertex(graph);
            graph[vret].name = name;
        }
        return vret;
    }

    void add_edge(graph_t& graph, vertex_t v1, vertex_t v2, int distance12, int distance21)
    {
        bool inserted;
        graph_t::edge_descriptor e1, e2;

        boost::tie(e1, inserted) = boost::add_edge(v1, v2, graph);
        graph[e1].distance = distance21;
        boost::tie(e2, inserted) = boost::add_edge(v2, v1, graph);
        graph[e2].distance = distance12;
    }
}

int main()
{
    graph_t graph;

    vertex_t va = add_ver(graph, "Asia");
    vertex_t vb = add_ver(graph, "Beer");
    vertex_t vc = add_ver(graph, "Cool");
    vertex_t vd = add_ver(graph, "Devel");
    vertex_t ve = add_ver(graph, "Estimate");
    vertex_t vf = add_ver(graph, "Foobar");
    vertex_t vs = add_ver(graph, "START");
    vertex_t vz = add_ver(graph, "GOAL");

    add_edge(graph, vs, va, 3, 3);
    add_edge(graph, va, vb, 1, 1);
    add_edge(graph, vb, vc, 2, 2);
    add_edge(graph, vb, vd, 3, 3);
    add_edge(graph, vc, ve, 7, 7);
    add_edge(graph, vc, vf, 12, 12);
    add_edge(graph, vd, vf, 2, 2);
    add_edge(graph, ve, vd, 11, 11);
    add_edge(graph, vf, ve, 3, 3);
    add_edge(graph, ve, vz, 2, 2);
    add_edge(graph, vf, vz, 2, 2);


    // 最短経路を計算
    std::vector<vertex_t> parents(boost::num_vertices(graph));
    std::vector<int> distance(boost::num_vertices(graph));
    boost::dijkstra_shortest_paths(graph, vs,
                boost::weight_map(boost::get(&edge_prop_t::distance, graph)).
                    predecessor_map(&parents[0]).
                    distance_map(&distance[0]));

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

    // 距離
    std::cout << "distance: " << distance[vz] << std::endl;

    // 経路の並べ直し
    std::deque<vertex_t> route;
    for (vertex_t v = vz; v != vs; v = parents[v]) {
        route.push_front(v);
    }
    route.push_front(vs);

    std::deque<vertex_t>::iterator it = route.begin();
    while (true) {
        std::cout << graph[*it].name;
        it++;
        if (it != route.end()) {
            std::cout << " --> ";
        } else {
            std::cout << std::endl;
            break;
        }
    }

    // graphviz用
    //      $ dot -T png dijkstra-graph.dot -o graph.png
    std::ofstream dot_file("dijkstra-graph.dot");
    dot_file << "digraph D {\n"
             << "  rankdir=LR\n"
             << "  ratio=\"fill\"\n"
             << "  edge[style=\"bold\"]\n" << "  node[shape=\"circle\"]\n";

    boost::graph_traits < graph_t >::edge_iterator ei, ei_end;
    for (boost::tie(ei, ei_end) = edges(graph); ei != ei_end; ++ei) {
        boost::graph_traits < graph_t >::edge_descriptor e = *ei;
        vertex_t u = source(e, graph), v = target(e, graph);
        dot_file << graph[u].name << " -> " << graph[v].name << "[label=\"" << graph[e].distance << "\"";
        if (parents[v] == u) {
            dot_file << ", color=\"black\"";
        } else {
            dot_file << ", color=\"grey\"";
        }
        dot_file << "]";
    }
    dot_file << "}";

}