ある頂点からある頂点に到達可能かどうかをチェックするboost::is_reachable()がすでに用意されていました。
namespace boost { // xからyに到達可能? template <typename IncidenceGraph, typename VertexColorMap> bool is_reachable( typename graph_traits<IncidenceGraph>::vertex_descriptor x, typename graph_traits<IncidenceGraph>::vertex_descriptor y, const IncidenceGraph& g, VertexColorMap color // 各頂点が白で開始しなければならない ); }
サンプル:
#include <iostream> #include <vector> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/graph_utility.hpp> #include <boost/assign/list_of.hpp> #include <boost/detail/lightweight_test.hpp> typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS> Graph; typedef std::pair<int, int> Edge; enum { A, B, C, D, E, N }; const int vertex_count = N; int main() { const std::vector<Edge> edges = boost::assign::list_of<Edge> (A, B)(B, E) (A, C)(C, E) ; const Graph g(edges.begin(), edges.end(), vertex_count); // 全部白のカラーマップを作って渡す std::vector<boost::default_color_type> color(vertex_count, boost::white_color); BOOST_TEST( boost::is_reachable(A, E, g, color.data())); BOOST_TEST(!boost::is_reachable(A, D, g, color.data())); return boost::report_errors(); }
他の実装:
ex_is_reachable.cpp
Boost.Graph 最短経路の長さ(weight)を計算する