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 http://www.boost.org/doc/libs/1_38_0/libs/graph/example/bfs.cpp example source code to this :
typedef boost::adjacency_list< boost::vecS,
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;
distances.reserve(6);
std::fill_n(&distances[0], 6, 0);
// The source vertex
Vertex s = *(boost::vertices(G).first);
boost::breadth_first_search(G,
s,
boost::visitor(boost::make_bfs_visitor(boost::record_distances(&distances[0], boost::on_tree_edge()))));
boost::print_graph(G);
for (int i = 0; i < 6; i++)
{
std::cout << "Node " << i << " : ";
if (distances[i] != 0)
std::cout << "reachable, distance " << distances[i] << std::endl;
else
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