Re: [boost] [graph] interest in resumable dijkstra?

Subject: Re: [boost] [graph] interest in resumable dijkstra?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-08-04 15:30:48

For now, I'm only going to comment on your use cases.  I'm glad that you 
sent them; they give a better sense of what you had in mind for the class, 
rather than my version which is just directly inverting the control flow 
from visitors to an algorithm object that suspends itself at event points.

On Fri, 4 Aug 2012, Alex Hagen-Zanker wrote:

> For your information, I have the following cases at hand:
>
> 1. Calculating multiple paths on the same graph, where the graph have many 
> vertices but the paths not. It then saves to only reset the queue and the 
> property maps for the discovered vertices that are recorded by a visitor, 
> instead of initializing property maps for all paths.

Does dijkstra_shortest_paths_no_init cover that use case, or do you need 
something other than that?

> 2. Interweavedly do many shortest paths on the same network for different 
> sources. Iteratively do the following for each source: deserialize, update 
> stopping criterion, expand the shortest path tree to criterion is met, 
> serialize.

I'm not sure I understand what you're trying to do for this case.  Are you 
doing many independent shortest path computations with different sources 
and stopping criteria, but starting from scratch each time, or are you 
using the distance, color, and/or predecessor maps from earlier 
computations in later ones?

> 3. Find the nearest source, if within a given distance e.g. finding the 
> 3-minute walking catchments for all bus-stops in a state.

There's an easier solution for that use case: use 
dijkstra_shortest_paths_no_color_map_no_init (from 
<boost/graph/dijkstra_shortest_paths_no_color_map.hpp>, with documentation 
at 
<URL:http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html>) 
and a combine function that does a normal saturating addition but then 
converts any results that are >= 3 minutes to infinity.  That version of 
Dijkstra's algorithm stops when all vertices in the queue have infinite 
distances, and you should be able to just re-run it with different 
sources, with an empty queue each time but not changing the distance or 
predecessor maps between runs.  The predecessor map should then give you a 
tree for each catchment area.

> Originally I used exception throwing visitors, which I believe is common 
> practice. So, I was happy to keep using visitors.

That is the common practice; the inversion of control would allow you to 
just use "return" and "break" instead, as well as interleave multiple 
searches at the same time.

-- Jeremiah Willcock