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

Subject: Re: [Boost-users] [BGL] premature termination in dijkstra using visitor
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2009-10-02 11:50:55

On Fri, 2 Oct 2009, Michael Fawcett wrote:

> On Fri, Oct 2, 2009 at 9:42 AM, Ralf Goertz
> <R_Goertz_at_[hidden]> 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