Why not, just erasing temporary the vertice (c,d) and applying DFS directly ?
Tarjei Knapstad 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]
