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,
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
<boost/graph/dijkstra_shortest_paths_no_color_map.hpp>, with documentation
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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk