graphtest.cpp tests the Boost Graph Library (BGL)

graphtest.cpp

// graphtest.cpp tests the Boost Graph Library (BGL)
// Reference: http://faithandbrave.hateblo.jp/entry/20100413/1271129607
////
#include <iostream>
#include <vector>
#include <string>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/phoenix.hpp>

using namespace boost;

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

enum { A, B, C, D, E, N };
const std::string name = "ABCDE";
const int vertex_count = N;

int main()
{
    // 辺
    std::vector<Edge> edges = {
        {A, B}, {A, C}, {A, D},
        {B, E}, {C, E}, {D, E}
    };

    // 距離
    std::vector<int> weights = {
        3, 1, 4,
        5, 2, 6
    };

    // グラフ作成
    Graph g(edges.begin(), edges.end(), weights.begin(), vertex_count);

    // 最短経路を計算
    std::vector<Vertex> p(num_vertices(g));
    dijkstra_shortest_paths(g, A,
        visitor(make_dijkstra_visitor(record_predecessors(&p[0], on_edge_relaxed()))));

    // 結果を表示
    adjacency_list<> tree(vertex_count);
    boost::phoenix::for_each(vertices(g), [&](const graph_traits<Graph>::vertex_descriptor& v) {
        if (v != p[v])
            add_edge(p[v], v, tree);
    })();
    print_graph(tree, name.c_str());
}
// local variables:
//   compile-command: "g++ -std=c++11 -g -Wall -O3 -o graphtest graphtest.cpp && ./graphtest"
// End: