
Boost : 
From: Doug Gregor (dgregor_at_[hidden])
Date: 20041115 09:26:29
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:
http://www.boost.org/libs/graph/doc/filtered_graph.html
Doug
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk