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