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