[Graph] Computing reachable vertices on a graph
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<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@fr.thalesgroup.com
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!
You probably shouldn't rely on vertex indices as the canonical id of the vertex. The method of identifying vertices (and edges) in an adjacency list varies with the vertex set and edge set type selectors (indices or identifeirs for vecS aren't the same as listS). There are a couple of different approaches. The easiest would be to simply maintain a mapping of id to vertex descriptor. For example: map<int, graph_traits<Graph>::vertex_descriptor> verts; verts[5] = add_vertex(g); verts[58] = add_vertex(g); // and so on. You can couple that bundled vertex properties to get a kind of bimap. struct vertex_props { int id; } typedef adj_list<vecS, vecS, directedS, vertex_props> Graph; template <typename Graph, typename Map> void add_vertex(Graph& g, Map& verts, int id) { vertex_descriptor v = add_vertex(g); verts[id] = v; g[v].id = id; } add_vertex(g, verts, 5); add_vertex(g, verts, 58); ... cout << g[*vertices(g).begin]->id << "\n"; Hope that helps, Andrew Sutton andrew.n.sutton@gmail.com
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 <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::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
participants (3)
-
Andrew Sutton
-
Florian.PONROY@fr.thalesgroup.com
-
Steven Watanabe