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

Boost.Graph is_reachable

C++

ある頂点からある頂点に到達可能かどうかをチェックする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 到達可能かどうかをチェックする

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