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

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2003-03-05 05:05:04

On Wed, 2003-03-05 at 07:53, Vladimir Prus wrote:
> 
> 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?
> 
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. 

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.

> 
> >> > 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:

       d-e-f
      /
 a-b-c
      \
       g-h-i

If my starting vertex is 'c' here, and I want to block 'd', then 'd'
will be coloured black in start_vertex. 'c' will then be coloured gray,
and the DFS then proceeds to discover new vertices. When it discovers
'd' it sees that it is allready black and believes it's allready been
there. (the edge (c,d) could of course be coloured instead).

> 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.

> 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.

Regards,
--
Tarjei