読者です 読者をやめる 読者になる 読者になる

Boost.Graph 到達可能かどうかをチェックする

C++

TDDBC for C++に参加して書いてたコードです。
ある駅からある駅に行けるかどうかをチェックする(経由駅も考慮する)という課題。


幅優先探索(boost::breadth_first_search)でfromから到達可能な頂点のリストを作成して、findでtoが含まれているか調べています。
後日、到達可能か調べるだけならもっといい方法(?)があることがわかったので、それは次回書きます。

#include <iostream>
#include <vector> 
#include <iterator> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/breadth_first_search.hpp> 
#include <boost/graph/visitors.hpp> 
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/range/algorithm/find.hpp>
#include <boost/assign/list_of.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;

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)
    ;

    // 距離はここではいらないので全部1
    const std::vector<int> weights(vertex_count, 1);

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


bool is_reachable(const Graph &g, Station::enum_t from, Station::enum_t to)
{
    // fromから到達可能な頂点のリストを作成
    std::vector<Vertex> reachable; 
    boost::breadth_first_search(g, from, 
        boost::visitor( 
          boost::make_bfs_visitor( 
            boost::write_property( 
              boost::identity_property_map(), 
              std::back_inserter(reachable), 
              boost::on_discover_vertex())))); 
 
    // toがその中にあるか調べる
    return boost::find(reachable, static_cast<Vertex>(to)) != reachable.end();
}

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

    BOOST_TEST(is_reachable(g, Station::Omiya, Station::Yokohama));
    BOOST_TEST(is_reachable(g, Station::Yokohama, Station::Tokyo));
    BOOST_TEST(is_reachable(g, Station::Tokyo, Station::Omiya));

    BOOST_TEST(is_reachable(g, Station::Yokohama, Station::NishiKokubunji));
    BOOST_TEST(is_reachable(g, Station::Omiya, Station::NishiKokubunji));
    BOOST_TEST(is_reachable(g, Station::Tokyo, Station::NishiKokubunji));
}

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

    BOOST_TEST(is_reachable(g, Station::Yokohama, Station::Omiya));
    BOOST_TEST(is_reachable(g, Station::Tokyo, Station::Yokohama));
    BOOST_TEST(is_reachable(g, Station::Omiya, Station::Tokyo));

    BOOST_TEST(is_reachable(g, Station::NishiKokubunji, Station::Yokohama));
    BOOST_TEST(is_reachable(g, Station::NishiKokubunji, Station::Omiya));
    BOOST_TEST(is_reachable(g, Station::NishiKokubunji, Station::Tokyo));

}

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

    BOOST_TEST(!is_reachable(g, Station::Yokohama, Station::Oshima));
    BOOST_TEST(!is_reachable(g, Station::Oshima, Station::Omiya));
}

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

    return boost::report_errors();
}