[BGL] Determining whether a path exists from vertex U to vertex V
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. 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. Thanks in advance, David Jones
Hi David.
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.
Hmmm... I do not think you can do better than BFS unless your particular graph has some special knowledge in it that we are not aware of. Also... with BFS you do get the shortest path available and I believe you can force it to solve your 'more complicated' problem as well... HTH, Jurko Gospodnetiæ
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
Thank you, Jurko and Doug, for your replies. David "Doug Gregor" <dgregor@cs.indiana.edu> wrote in message news:5763CAC2-3712-11D9-A5E7-000D932B7224@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:
participants (3)
-
David M. Jones -
Doug Gregor -
Jurko Gospodneti�