Re: [Boost-users] To find a path between two vertices in a tree.

Subject: Re: [Boost-users] To find a path between two vertices in a tree.
From: Nishchal Devnur (nishchal.devnur_at_[hidden])
Date: 2011-05-18 15:58:36

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_at_[hidden]>wrote:

> On Wed, May 18, 2011 at 12:34 PM, Nishchal Devnur <
> nishchal.devnur_at_[hidden]> 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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>

-- 
Nishchal Devanur