Re: [boost] (from: [Boost-Users]) [BGL] Preconditioned color maps?

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-03-05 01:53:11

Tarjei Knapstad wrote:

> The second problem however is a property of the DFS algorithm where a
> starting vertex is given that I had overlooked. After the DFS has
> discovered all the vertices reachable from the starting vertex, it will
> continue using any yet undiscovered (white) vertices and use those as
> starting vertices for another search. That means that if I block 'd' in
> my example graph, undirected_dfs will first do the job I intend it to
> starting from 'c', but will then select either 'e' or 'f' as a next
> starting vertice and do a DFS from there until all vertices have been
> discovered. And that was exactly what I was trying to avoid :)

I think that besides depth_first_search, there's depth_first_visit, 
which traversed the graph starting from *one* vertex. depth_first_search
merely calls depth_first_visit for all white vertices. Maybe, 
depth_first_visit is what you're after?

>> > In an algorithm I'm working on I need to do an undirected_dfs using a
>> > visitor for analysis. I know my starting vertex, and I also want the
>> > DFS to skip one of the starting vertex's adjacent vertices (i.e. don't
>> > proceed in the "direction" from the starting vertex). Example:

>     template <class Vertex, class Graph>
>     void start_vertex(Vertex u, const Graph& g)
>     { 
>         if (apVertex)
>         { 
>            (*apColorMap)[*apVertex] = Color::black();
>         }
>     }

Ehhm... how will this work? 'start_vertex' is called immediately
before calling next depth_first_visit. That function, right in
the start, colors the starting vertex in gray...

If I were to implement the same, I'd try using 'examine_edge' event: when
edge leads to a blocked vertex, you color that vertex in black.

Another possibility is to eliminate blocked vertices from the graph, using
'subgraph' adapter, but I really don't know how good/efficient this idea is.

- Volodya