Boost logo

Boost :

From: Tarjei Knapstad (tarjeik_at_[hidden])
Date: 2003-03-05 07:17:56


On Wed, 2003-03-05 at 11:23, vladimir josef sykora wrote:
>
> "Tarjei Knapstad" <tarjeik_at_[hidden]> wrote in message
> news:1046817775.2517.58.camel_at_cc-intern01...
> > On Tue, 2003-03-04 at 21:44, Louis Lavery wrote:
>
> [snip]
>
> > > > 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".
>
> AFAICS, 'd' is not an adjacent vertex of 'c'.
>
Why? There's and edge (c,d), so certainly 'd' is adjacent to 'c' (this
is to my knowledge the definition of "adjacent vertex").

> > > >
> > > > 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.
> > > >
>
> There's the _visit_ version of the algorithm, where this task is left to the
> user. So you could color your graph as you like, and then call that version.
>

>From Vladimir Prus:
> Just to clarify: are you talking about "undirected_depth_first_visit"
> function as found in <boost/graph/undirected_dfs.hpp>?

This is of course exactly what I'm after, but I hand't seen it until now
because it's not mentioned in the docs and it's stashed at the bottom of
that header where I obviously hadn't looked

Thanks both of you,

--
Tarjei

Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk