From: David M. Jones (djones_at_[hidden])
Date: 2004-11-15 10:46:56
Thank you, Jurko and Doug, for your replies.
"Doug Gregor" <dgregor_at_[hidden]> wrote in message
> On Nov 12, 2004, at 1:37 PM, David M. Jones wrote:
> > I have looked at the BGL User Guide/Reference manual book but I can't
> > seem
> > to find the answer to this seemingly basic question.
> > I have a directed BGL graph. Given two vertices U and V, I want to know
> > whether there is a path from U to V. I don't care what path it is; I
> > just
> > want to know whether one exists or not. It looks like I might be able
> > to use
> > the BFS or DFS to do this, but that seems like attacking a mosquito
> > with a
> > tank.
> Either BFS or DFS is fine here. You could write your own visitor that
> throws an exception when it finds V, if you're worried about searching
> too much of the graph,
> > A slightly more complicated problem that I want to solve is: given
> > vertices
> > U and V, I want to know whether there is a path from U to V such that
> > all
> > edges along the path have a certain property. Again, I don't care to
> > know
> > what the path is or its length; only whether or not such a path exists.
> Again, you can use BFS or DFS (doesn't matter which), but there's one
> more step: you'll want to create a filtered_graph that filters out all
> of the edges that do not have the "certain property" you mentioned, so
> that the BFS/DFS only sees the good edges and will be able to determine
> if a path exists. The filtered_graph documentation is here:
> Unsubscribe & other changes:
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk