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

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-03-05 05:41:42

Tarjei Knapstad wrote:

> Yes, depth_first_visit goes through all the vertices in the connected
> component which the starting vertex belong to, but depth_first_visit is
> for directed graphs so I can't use it - it confuses tree and back edges
> when used on undirected graphs. This is why undirected_dfs was made
> which correctly handles tree and back edges by using an additional edge
> color map.

Oops. I've paid not enough heed to 'undirected' word. BTW, I also don't know
why undirected_dfs is completely separate algorithm... there's a lot in 
common.

> On second thought undirected_dfs_visit is exactly what I've implemented
> in my constrained_undirected_dfs, as colouring one vertex black
> basically "fools" the DFS into believing that the graph consists of two
> connected components.

Just to clarify: are you talking about "undirected_depth_first_visit" 
function as found in <boost/graph/undirected_dfs.hpp>? 

>> >> > 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...
>> 
> Yes, the starting vertex is colored gray. 'apVertex' above however is a
> pointer to the vertex which is to be blocked, and this vertex is
> adjacent to the starting vertex, so this works (maybe I should've called
> it 'apBlockedVertex' or the like). Taking my example graph:

Agh.. you color specific vertex in black when starting next dfs_visit.

>> 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.
>> 
> Yes, but this is a lot more work than the above. In my case the vertex I
> want to block is allways adjacent to the starting vertex, so the
> start_vertex approach works fine, but if you want something more general
> where the vertex/vertices to be blocked are not adjacent to your
> starting point then this would be a more proper solution of course.

OK. And interesting questions is whether blocking some vertices should be
supported in BGL. 

>> 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.
>> 
> Richard Howells suggested this in Boost-Users as well, but the problem
> is that to create a subgraph you need to specify all the vertices from
> the original graph, and the adapator then recreates the edges as they
> are found in the original graph. Those vertices are exactly what I'm
> trying to discover through my "blocked DFS" though, so the adapter
> solution leaves me at square one.

I don't think so. You can write a predicate which will say that
specific vertex is not present in the filtered_graph (BTW, this is the
right name, not 'subgraph' as I said before). Or you can exclude the
edge from starting vertex to the blocked one. Changing color looks
faster, in any case.

- Volodya