Boost logo

Boost Users :

Subject: [Boost-users] [Graph] Computing reachable vertices on a graph
From: Florian.PONROY_at_[hidden]
Date: 2009-03-20 04:44:53

Hi all,

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. To understand its behavior, I simplified the example source code to this :

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

  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<int> distances;

  std::fill_n(&distances[0], 6, 0);

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

                              boost::visitor(boost::make_bfs_visitor(boost::record_distances(&distances[0], boost::on_tree_edge()))));


  for (int i = 0; i < 6; i++)
          std::cout << "Node " << i << " : ";
          if (distances[i] != 0)
                  std::cout << "reachable, distance " << distances[i] << std::endl;
                  std::cout << "not reachable" << std::endl;

However, I encounter the following issue : in this example, vertices are numbered from 0 to 5. However, in my project, this is not the case, vertices could be numbered 5, 38, 42, 384... Using a vector in that case might not work as expected, a map<vertex, distance> would probably be better. I'm not quite familiar with BGL so far, maybe should I deal with a specific property map? Or using a visitor to record a vertex distance upon graph discovery? I'm a little bit lost, any help will be greatly appreciated!

Thank you very much,

Florian PONROY
Thales Land & Joint France
Tel. : +33(0)1 41 304 363
Fax : +33(0)1 41 303 560
Email : florian.ponroy_at_[hidden]

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