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

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 
(http://www.sciencedirect.com/science/article/pii/S0191261509000769).

> 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: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.
>
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.