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,
Florian
-----Message d'origine-----
De : boost-users-bounces@lists.boost.org
[mailto:boost-users-bounces@lists.boost.org]De la part de Steven
Watanabe
Envoyé : vendredi 20 mars 2009 18:36
À : boost-users@lists.boost.org
Objet : Re: [Boost-users] [Graph] Computing reachable vertices on a
graph
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
_______________________________________________
Boost-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
