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

From: Louis Lavery (Louis_at_[hidden])
Date: 2003-03-04 15:44:37

----- Original Message ----- 
From: Tarjei Knapstad <tarjeik_at_[hidden]>
To: Boost-users <Boost-Users_at_[hidden]>
Sent: Monday, 03 March, 2003 5:51 PM
Subject: [Boost-Users] [BGL] Preconditioned color maps?

> 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.
> 

Doesn't it invoke dfs_visitor::initialize_vertex(u,g) on every vertex 
before the start of the search?

> 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;
>    }
> }

If so, you could do something similar in there?

Although I can't find in the documentation that it's invoked after the 
colours have been set (but it is if you look in depth_first_search.hpp).

Failing that, dfs_visitor::start_vertex(s,g) is invoked on the source 
vertex once before the start of the search, so you could look for 'd'
in there.

Hmm, it doesn't say that dfs_visitor::start_vertex(s,g) is called after
the colours have been set (at least I can't find it in the docs), but 
it doesn't seem sensible to do it the other way round.

Louis.