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:59:18

On Fri, 2 Oct 2009, Michael Fawcett wrote:

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