Subject: Re: [boost] [graph] interest in resumable dijkstra?
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-08-07 17:13:46
On 04/08/2012 20:30, Jeremiah Willcock wrote:
> 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
> Does dijkstra_shortest_paths_no_init cover that use case, or do you
> need something other than that?
Almost. I had to create a function called
dijkstra_shortest_path_no_init_at_all, which does not initialize the
queue and also does not push the source vertex to the queue.
>> 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.
It is part of the implementation of a traffic assignment algorithm
> 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?
I am using the distance, color and predecessor maps from earlier
computations in later ones. I should also use the queue from earlier
computations, but as it stands I am recreating that one from the color map.
>> 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
> 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.
That would be easier indeed, if I did not already have the
dijkstra_class for the second use case.
>> 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.
Interleaving multiple searches was my critical problem in the second
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk