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

On Fri, 2 Oct 2009, Michael Fawcett wrote:

On Fri, Oct 2, 2009 at 11:50 AM, Jeremiah Willcock 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?

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.

Wouldn't throwing an exception when the weight gets too large mean the search stops at the first vertex when distance > N? The OP wants all vertices where distance == 2.

Yes, so stop when the distance is at least 3; vertices are processed in order of distance. -- Jeremiah Willcock