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
_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
