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

Subject: Re: [Boost-users] [BGL] premature termination in dijkstra using visitor
From: Cosimo Calabrese (cosimo.calabrese_at_[hidden])
Date: 2009-10-03 04:26:09

Ralf Goertz ha scritto:
> 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?
> 
> Ralf

Hi Ralf,

to write a visitor that throw an exception at the "right moment" is the 
official method, I've tried it an it works.

Personally, I don't like very much this way, because I use the 
exceptions only when happens special SO condition, like file that 
doesn't exists.

I prefer another way: to write a visitor that takes a reference to the 
Dijkstra queue. At the right moment, you empty the queue; when you 
return from the visitor event, the empty queue naturally terminates the 
Dijkstra's algorithm. Sincerely, I've never tried this technique, but if 
you want to try it, you can tell us if it works ;)

Best regards,
Cosimo Calabrese.