Re: [Boost-users] [BGL]Standard Breadth First Visitor

Subject: Re: [Boost-users] [BGL]Standard Breadth First Visitor
From: Moritz Beber (moritz.beber_at_[hidden])
Date: 2009-01-06 09:26:53

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_at_[hidden]
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> 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