Boost logo

Boost :

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
>> paths.
> 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
> <URL:>)
> 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
use case.

Boost list run by bdawes at, gregod at, cpdaniel at, john at