
Boost : 
From: Vladimir Prus (ghost_at_[hidden])
Date: 20030305 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 BoostUsers 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk