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

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

On Wed, 2003-03-05 at 08:50, Louis Lavery wrote:
> 
> 
> [snip]
> 
> > A possibility (as have recently been discussed IIRC) is to break off the
> > DFS by throwing an exception the second time start_vertex is invoked in
> > the visitor. I'm not too fond of that solution though, allthough I must
> > admit that my visitor implementation above is not exactly "a beaut"...
> 
> A less drastic alternative is to, on the second call, just set all vertex
> colours to black.
> 
Less drastic yes, but (possibly severly) inefficient in large graphs. In
undirected_dfs, after the starting vertex has been DFS visited, the
algorithm checks all vertices to see if there are any white left in the
graph, so the "colour all black" approach involves first setting say
100,000 vertex colors to black, and then checking the same 100,000
vertex colors to see if any are white.

> But I agree with you that a one_shot_depth_first_search that starts from
> a given vertex and then gets out is called for.
> 
Yes, like I said to Vladimir today, my "constrained_undirected_dfs" is
really nothing more than "undirected_dfs_visit". If I could have used
depth_first_visit I would be in the clear as it only discovers the
vertices which belong to the same connected component as the starting
vertex. Pre-colouring a vertex black effectively divides a fully
connected graph into two connected components (with the exception that
both components actually share the black vertex, but that becomes
unimportant).

> In fact I find it difficult to understand why anyone would want to start
> at a given vertex, do a dfs from there and then go on to start another
> dfs from any unvisited vertices. Perhaps I lack imagination - anyone
> got an example of its use?
> 
I'm not too heavily into graph theory and all it's applications either,
but there's probably scenarios where you've got several connected
components and need to start off with one of them based on some
criterion/-a.

Regards,
--
Tarjei