Boost.Graph 最短経路の長さ(weight)を計算する

C++

TDDBC for C++に参加して書いてたコードの完成版。
当日終わらなかったので、帰ってから仕上げました。


最短経路を計算するのには、ダイクストラ法(boost::dijkstra_shortest_paths)を使用。
頂点のリストを一つずらしでzipした辺のリストを作ったまではよかったけど、頂点のペアとしての辺からどうやってweightを取得するのかがわからず時間がかかってしまいましたが、

boost::tuple<Vertex, Vertex> x;
weight += boost::get(
                boost::edge_weight,
                g,
                boost::edge(boost::get<0>(x), boost::get<1>(x), g).first);

で取得することができました。

それと、最短経路を計算したあと、経路がなかったことをどう判定すればいいのかわからなかったのですが、
Twitterで教えてもらいました。


こうなりました。

if (parents[to] == to)
    return 0;


以下、完全なコードです。

#include <iostream>
#include <vector> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/assign/list_of.hpp>
#include <boost/range/combine.hpp>
#include <boost/range/adaptor/sliced.hpp>
#include <boost/foreach.hpp>

#include <boost/detail/lightweight_test.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
    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;
typedef boost::graph_traits<Graph>::edge_descriptor     EdgeDesc;

struct Station {
    enum enum_t {
        Omiya,
        Yokohama,
        Oshima,
        Tokyo,
        NishiKokubunji,
        N
    };
};

const int vertex_count = Station::N;

Graph create_graph()
{
    const std::vector<Edge> edges = boost::assign::list_of<Edge>
        (Station::Omiya, Station::Tokyo)
        (Station::Tokyo, Station::Yokohama)
        (Station::NishiKokubunji, Station::Yokohama)
        (Station::NishiKokubunji, Station::Omiya)
    ;

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

    const Graph g(edges.begin(), edges.end(), weights.begin(), vertex_count);
    return g;
}

int calc_path_weight(const Graph& g, Station::enum_t from, Station::enum_t to)
{
    std::vector<Vertex> parents(num_vertices(g));
    boost::dijkstra_shortest_paths(g, from,
                boost::predecessor_map(&parents[0]));

    // 経路なし
    if (parents[to] == to)
        return 0;

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

    // 経路の長さを計算
    int weight = 0;

    using boost::adaptors::sliced;
    typedef boost::tuple<Vertex, Vertex> value_type;
    BOOST_FOREACH (value_type x, boost::combine(route | sliced(0, route.size() - 1),
                                                route | sliced(1, route.size()))) {
        weight += boost::get(
                        boost::edge_weight,
                        g,
                        boost::edge(boost::get<0>(x), boost::get<1>(x), g).first);
    }

    return weight;
}

void reachable_path_test()
{
    const Graph g = create_graph();

    BOOST_TEST(calc_path_weight(g, Station::Omiya, Station::Yokohama) == 5);
    BOOST_TEST(calc_path_weight(g, Station::Yokohama, Station::Tokyo) == 2);
    BOOST_TEST(calc_path_weight(g, Station::Tokyo, Station::Omiya) == 3);

    BOOST_TEST(calc_path_weight(g, Station::Yokohama, Station::NishiKokubunji) == 6);
    BOOST_TEST(calc_path_weight(g, Station::Omiya, Station::NishiKokubunji) == 1);
    BOOST_TEST(calc_path_weight(g, Station::Tokyo, Station::NishiKokubunji) == 4);
}

void reverse_reachable_path_test()
{
    const Graph g = create_graph();

    BOOST_TEST(calc_path_weight(g, Station::Yokohama, Station::Omiya) == 5);
    BOOST_TEST(calc_path_weight(g, Station::Tokyo, Station::Yokohama) == 2);
    BOOST_TEST(calc_path_weight(g, Station::Omiya, Station::Tokyo) == 3);

    BOOST_TEST(calc_path_weight(g, Station::NishiKokubunji, Station::Yokohama) == 6);
    BOOST_TEST(calc_path_weight(g, Station::NishiKokubunji, Station::Omiya) == 1);
    BOOST_TEST(calc_path_weight(g, Station::NishiKokubunji, Station::Tokyo) == 4);

}

void unreachable_path_test()
{
    const Graph g = create_graph();

    BOOST_TEST(calc_path_weight(g, Station::Yokohama, Station::Oshima) == 0);
    BOOST_TEST(calc_path_weight(g, Station::Oshima, Station::Omiya) == 0);
}

int main()
{
    reachable_path_test();
    reverse_reachable_path_test();
    unreachable_path_test();

    return boost::report_errors();
}