Re: [Boost-users] [Graph] Computing reachable vertices on a graph

20 Mar 2009

      AMDG

Florian.PONROY@fr.thalesgroup.com wrote:
...
I need to get the list of all reachable vertices from a given vertex in a graph. I'm currently using the BFS algorithm to achieve that, which seems to fit well to my need.
How does this work:

#include 
#include 
#include 
#include <vector>
#include <iterator>

typedef boost::adjacency_list< boost::vecS,
                                 boost::vecS,
                                 boost::directedS > Graph;

int main() {

  Graph G(1);
  boost::add_edge(0, 1, G);
  boost::add_edge(1, 2, G);
  boost::add_edge(2, 5, G);
  boost::add_edge(3, 2, G);
  boost::add_edge(4, 3, G);
  boost::add_edge(5, 3, G);

  typedef Graph::vertex_descriptor Vertex;
  std::vector<Vertex> reachable;

  // The source vertex
  Vertex s = *(boost::vertices(G).first);

  boost::breadth_first_search(G, s,
    boost::visitor(
      boost::make_bfs_visitor(
        boost::write_property(
          boost::identity_property_map(),
          std::back_inserter(reachable),
          boost::on_discover_vertex()))));
}

In Christ,
Steven Watanabe