Re: [boost] [BGL] Determining whether a path exists from vertex U to vertex V

From: Doug Gregor (dgregor_at_[hidden])
Date: 2004-11-15 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