Boost logo

Boost Users :

Subject: Re: [Boost-users] [Graph] Computing reachable vertices on a graph
From: Florian.PONROY_at_[hidden]
Date: 2009-03-23 04:50:01

Hi Steven,

I just tried your solution, which works perfectly well. The vector is
actually sized to the number of reachable nodes. I just added a
reachable.reserve(max_number_of_nodes) to avoid multiple reallocations.

Thank you very much for your help,


-----Message d'origine-----
De : boost-users-bounces_at_[hidden]
[mailto:boost-users-bounces_at_[hidden]]De la part de Steven
Envoyé : vendredi 20 mars 2009 18:36
À : boost-users_at_[hidden]
Objet : Re: [Boost-users] [Graph] Computing reachable vertices on a


Florian.PONROY_at_[hidden] 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 <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/visitors.hpp>
#include <vector>
#include <iterator>

typedef boost::adjacency_list< 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,

In Christ,
Steven Watanabe

Boost-users mailing list

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at