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: Marsh Ray (marsh_at_[hidden])
Date: 2011-05-19 12:24:17

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