To find a path between two vertices in a tree.
Hi, I am looking for a implementation in boost that is efficient in finding a path between two vertices in a given tree. I am right now using the unidrected adjancency list to store the tree. Given a node u and node v I would like to find the path between these two nodes in the tree. Any suggestions is greatly appreciated ! Thanks, Nishchal Devanur
On Wed, May 18, 2011 at 12:34 PM, Nishchal Devnur <nishchal.devnur@gmail.com
wrote:
Hi,
I am looking for a implementation in boost that is efficient in finding a path between two vertices in a given tree. I am right now using the unidrected adjancency list to store the tree. Given a node u and node v I would like to find the path between these two nodes in the tree. Any suggestions is greatly appreciated !
If your edges are weighted, then you should look into Dijkstra's Algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm If your edges all have the same weight, then a standard breadth-first search is sufficient: http://en.wikipedia.org/wiki/Breadth-first_search Wikipedia's article on BFS is a bit misleading in your case since you might think it says you have to start at the root of your tree. In fact you should just start from your "u" node and progress outwards -- the u node is the "root" of a notional tree that is superimposed on your normal graph. -Chris
Thanks a lot Chris, I am currently using BFS for it and I am using the boost library to do it. But I am finding that the code is running very slowly as I am working with very large graphs that are dynamic and I need to apply BFS repeatedly. Also is there a way to exit from the BFS function of the boost library once I find the target node during the search. I have a hunch that I should use BFS Visitor concept for this, but I am not able to figure that out properly. Regards, Nishchal. On Wed, May 18, 2011 at 3:50 PM, Chris Weisiger <cweisiger@msg.ucsf.edu>wrote:
On Wed, May 18, 2011 at 12:34 PM, Nishchal Devnur < nishchal.devnur@gmail.com> wrote:
Hi,
I am looking for a implementation in boost that is efficient in finding a path between two vertices in a given tree. I am right now using the unidrected adjancency list to store the tree. Given a node u and node v I would like to find the path between these two nodes in the tree. Any suggestions is greatly appreciated !
If your edges are weighted, then you should look into Dijkstra's Algorithm: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
If your edges all have the same weight, then a standard breadth-first search is sufficient: http://en.wikipedia.org/wiki/Breadth-first_search
Wikipedia's article on BFS is a bit misleading in your case since you might think it says you have to start at the root of your tree. In fact you should just start from your "u" node and progress outwards -- the u node is the "root" of a notional tree that is superimposed on your normal graph.
-Chris
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Nishchal Devanur
On 05/18/2011 02:58 PM, Nishchal Devnur wrote:
I am working with very large graphs that are dynamic and I need to apply BFS repeatedly. Also is there a way to exit from the BFS function of the boost library once I find the target node during the search. I have a hunch that I should use BFS Visitor concept for this, but I am not able to figure that out properly.
One trick I've used is to define a custom color map that always returns 'black' for every node that you don't want the BFS algorithm visiting. The current BFS implementation still visits the first node though, but that wasn't a problem. After you find your node, you could flip a switch in your custom color map so that it then always returns black. You could also empty the Buffer Q explicitly. Some combination of those should exit the algorithm fairly quickly. It also means you don't have to allocate map storage for every node in the graph, just for the ones actually visited. You'd use breadth_first_visit since your color map can perform its own initialization. I'm a BGL newb though, so perhaps someone else has a better way. - Marsh
participants (3)
-
Chris Weisiger -
Marsh Ray -
Nishchal Devnur