[BGL]Standard Breadth First Visitor
Hello everyone, I can't seem to wrap my head around implementing a BFS Visitor and color map required by the breadth_first_visitor function. I want to use it to find connected parts of a graph and after the algorithm has run I plan to clear all white nodes. If anyone could provide me with a code example or link to one implementing really only default behaviour I'd appreciate it immensely. Have a happy new year, Moritz
I can't seem to wrap my head around implementing a BFS Visitor and color map required by the breadth_first_visitor function.
I want to use it to find connected parts of a graph and after the algorithm has run I plan to clear all white nodes.
If anyone could provide me with a code example or link to one implementing really only default behaviour I'd appreciate it immensely.
Which part is causing trouble: the implementation of the visitor or the creation of a color map? Creating exterior properties can be a bit tricky, and the method used depends entirely on the type of your graph. Post code usually results in better answers. Andrew Sutton andrew.n.sutton@gmail.com
On Tue, 2009-01-06 at 09:03 -0500, Andrew Sutton wrote:
I can't seem to wrap my head around implementing a BFS Visitor and color map required by the breadth_first_visitor function.
I want to use it to find connected parts of a graph and after the algorithm has run I plan to clear all white nodes.
If anyone could provide me with a code example or link to one implementing really only default behaviour I'd appreciate it immensely.
Which part is causing trouble: the implementation of the visitor or the creation of a color map? Creating exterior properties can be a bit tricky, and the method used depends entirely on the type of your graph.
Post code usually results in better answers.
Andrew Sutton andrew.n.sutton@gmail.com _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
OK, I'll try to explain a little bit better. I have a graph with a known number of roots which I represent by the following adjacency list: boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, boost::no_property, boost::no_property, boost::no_property, boost::listS> The graph is generated in a way that I have a stable number of vertices but sort of random links (it's an evolutionary design of a network). So I want to use the breadth first visitor to identify any vertices of the graph that are not connected to the main graph formed with the known roots. Since I have several roots I thought I could speed up the process by using an external property map for colours which I pass again to breadth_first_visitor without re-initialisation for each root. At the end I would clear any vertex that is white. When I want to use the algorithm: template <class IncidenceGraph, class Buffer, class BFSVisitor, class ColorMap> void breadth_first_visit (const IncidenceGraph& g, typename graph_traits<IncidenceGraph>::vertex_descriptor s, Buffer& Q, BFSVisitor vis, ColorMap color) I need to supply it with an appropriate visitor which does the exploring of adjacent nodes and a property map for the colouring. Setting up those two causes me trouble. I simply fail at making sense of the documentation. Thank you for your help and time, Moritz
I need to supply it with an appropriate visitor which does the exploring of adjacent nodes and a property map for the colouring. Setting up those two causes me trouble. I simply fail at making sense of the documentation.
Creating a visitor is easy. Creating exterior property maps can be a bit of a pain. struct my_visitor : default_bfs_visitor { my_color_map colors; template <typename Graph, typename Vertex> discover_vertex(Graph& g, Vertex v) { /* Your code here */ } }; // calling it queue<graph_traits<Graph>::vertex_descriptor> q; breadth_first_visit(g, root, q, my_visitor(), my_colors); Andrew Sutton andrew.n.sutton@gmail.com
On Tue, 2009-01-06 at 09:03 -0500, Andrew Sutton wrote:
I can't seem to wrap my head around implementing a BFS Visitor and color map required by the breadth_first_visitor function.
I want to use it to find connected parts of a graph and after the algorithm has run I plan to clear all white nodes.
If anyone could provide me with a code example or link to one implementing really only default behaviour I'd appreciate it immensely.
Which part is causing trouble: the implementation of the visitor or the creation of a color map? Creating exterior properties can be a bit tricky, and the method used depends entirely on the type of your graph.
Post code usually results in better answers.
Andrew Sutton andrew.n.sutton@gmail.com _______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
OK, I'll try to explain a little bit better. I have a graph with a known number of roots which I represent by the following adjacency list: boost::adjacency_list<boost::setS, boost::vecS, boost::bidirectionalS, boost::no_property, boost::no_property, boost::no_property, boost::listS> The graph is generated in a way that I have a stable number of vertices but sort of random links (it's an evolutionary design of a network). So I want to use the breadth first visitor to identify any vertices of the graph that are not connected to the main graph formed with the known roots. Since I have several roots I thought I could speed up the process by using an external property map for colours which I pass again to breadth_first_visitor without re-initialisation for each root. At the end I would clear any vertex that is white. When I want to use the algorithm: template <class IncidenceGraph, class Buffer, class BFSVisitor, class ColorMap> void breadth_first_visit (const IncidenceGraph& g, typename graph_traits<IncidenceGraph>::vertex_descriptor s, Buffer& Q, BFSVisitor vis, ColorMap color) I need to supply it with an appropriate visitor which does the exploring of adjacent nodes and a property map for the colouring. Setting up those two causes me trouble. I simply fail at making sense of the documentation. Thank you for your help and time, Moritz
participants (2)
-
Andrew Sutton -
Moritz Beber