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