Re: [Boost-users] [Graph] Switching from depth_first_search to depth_first_visit

Subject: Re: [Boost-users] [Graph] Switching from depth_first_search to depth_first_visit
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2011-03-16 11:39:49

On Wed, 16 Mar 2011, Marcus Riemer wrote:

> Hello there!
>
> I just stumbled over a little bug that is simply due to the wrong visiting 
> pattern used. From what I understand it should simply print a graph with 
> children being indented.
>
> The visitor defined for the task itself is just fine. Problem is that 
> currently a depth first *search* is used, which prints each vertex only once.
>
> So from my understanding the only thing I need to do is to replace that 
> search with a visit. Sadly replacing the call to depth_first_visit with a 
> call to depth_first_visit is not as easy as I thought ...
>
> For the record: The search call itself looks like this:
> boost::depth_first_search(mGraph, 
> boost::visitor(printer).root_vertex(start));
>
> Looking at the documentation [0] it seems that there is no version with named 
> parameters for the depth first visit. So I need to pass the graph itself, the 
> starting vertex, the visitor and a color map.
>
> And its the color map that troubles me ... I have tried around a little to 
> construct such a thing, but so far without success. My try can be found at 
> [1]. This results in a massive compilation error [2].
>
> I am not really experienced with the extent templates are used in the BGL and 
> have no idea what the compiler tries to tell me.
>
> Could anyone give me a hint what I am doing wrong?
>
> If more sourcecode is required thats not a problem at all. Simply tell me if 
> anything is missing. Access to the source is also not a problem, compilation 
> is quite easy using cmake.
>
> Thanks in advance
>  Marcus Riemer

A raw std::vector is not enough to use as a color map.  If your graph has 
a vertex index map (which is probably true), you can make a color map as:

two_bit_color_map<property_map<Graph, vertex_index_t>::const_type>
   color_map(num_vertices(graph), get(vertex_index, graph));

I believe that is automatically cleared; otherwise, see the code in 
depth_first_search() that clears the color map (depth_first_visit() will 
not do that for you).

-- Jeremiah Willcock