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

From: David M. Jones (djones_at_[hidden])
Date: 2004-11-15 10:46:56

Thank you, Jurko and Doug, for your replies.

David

"Doug Gregor" <dgregor_at_[hidden]> wrote in message
news:5763CAC2-3712-11D9-A5E7-000D932B7224_at_cs.indiana.edu...
>
> 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
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost
>