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

Subject: Re: [Boost-users] [BGL] premature termination in dijkstra using visitor
From: Michael Fawcett (michael.fawcett_at_[hidden])
Date: 2009-10-02 11:56:27

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.

--Michael Fawcett