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

From: Alexandre Carsac (acarsac_at_[hidden])
Date: 2003-03-04 08:03:20

Why not, just erasing temporary the vertice (c,d) and applying DFS directly ?
 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
---------------------------------
Do You Yahoo!? -- Une adresse @yahoo.fr gratuite et en français !
Testez le nouveau Yahoo! Mail
[Non-text portions of this message have been removed]