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
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