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

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2003-03-04 10:30:23

On Tue, 2003-03-04 at 14:03, Alexandre Carsac wrote:
> 
> Why not, just erasing temporary the vertice (c,d) and applying DFS directly ?

Hi Alexandre,

There are two reasons why I'd like to avoid this:

1 (minor): My graph has a lot of internal properties, so that would mean
that some state saving had to be done. My graph class inherits an
undirected adjacency list, so I could allways implement some
"HideEdge/RestoreEdge" functionality that would temporarily remove a
edge from the graph.

2 (major): This is a read-only operation, and the same graph _might_
also be accesed read-only in another thread. The remove edge solution
would mean that I'd have to put a lock on it in this algorithm and lose
performance. I could make a copy of the graph, but as it is potentially
quite large this could possibly take longer than just doing a full DFS,
and eliminate the unwanted results afterwards.

I'll consider going with the remove-edge alternative, but I'll have to
look a bit more into if I risk losing parallell efficiency.

>  Tarjei Knapstad <tarjeik_at_[hidden]> wrote: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:
> 
>       d-e-f
>      /
> a-b-c
>      \
>       g-h-i
> 
> Starting vertex is 'c' and I want to eliminate the "d-e-f" branch, so
> the DFS finds "c-b-a" and "c-g-h-i".
> 
> My first idea was to set up a vertex color map, and set the color to
> black for vertex 'd' in the example above, but that doesn't do much good
> as the undirected_dfs sets all colors to white initially.
> 
> My second thought was to feed the vertex I want to eliminate and the
> vertex color map to my dfs_visitor implementation, something like:
> 
> discover_vertex(u, g)
> {
>    if (u == blocked)
>    {
>       vertex_colormap[u] = black;
>    }
> }
> 
> Will the latter approach work satisfactory? If not, is there some other
> way which I can use to precondition the color maps used in the BGL
> algorithms?
> 

Thanks,
--
Tarjei