Re: [Boost-users] [BGL] premature termination in dijkstra using visitor

On Fri, 2 Oct 2009, Michael Fawcett wrote:

On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz wrote:

...

Hi,

I have some very large undirected graphs (half a million vertices). Edges have weight 0 or 1. For each vertex I need to find all vertices

       * that are in sum 2 edges away        * whose distance is 0

Both tasks can be done with breadth-first searches but I don't know in advance how many edges in depth I have to traverse. That's why I thought of Dijkstra's algorithm. But in my case this is overkill as I am not interested in the exact distance of a vertex from a given vertex but only in if it is not farther than 0 or 2 away. Is it possible to use a visitor to alter the colormap to mark vertices as final that are too far even thought they are not final yet?

I don't have a suggestion, but I did want to lend weight to your question since I have exactly the same requirements. I currently use Dijkstra and accept the overkill, but as my graphs get bigger it's becoming less acceptable.

The normal technique for this is to write a visitor that throws an exception when the distance becomes too large. The task of finding distance-0 vertices can also be done by BFS with a filtered_graph that only keeps weight-0 edges; that will automatically stop when all of the needed vertices are found. -- Jeremiah Willcock