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

Subject: Re: [boost] [graph] interest in resumable dijkstra?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-08-09 16:58:34

On Tue, 7 Aug 2012, Alex Hagen-Zanker wrote:

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

OK.  Other people have asked about searching from multiple sources, which 
your new function would help with as well.

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

OK.  It looks like that algorithm is using longest paths (in DAGs) as well 
as shortest paths.  Is that also something that you're doing?

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

Do you just use this to interleave computations, with the maps used to 
restart a shortest path search from where it left off, or are you 
manipulating the maps in some other way?

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

OK.

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

OK.

-- Jeremiah Willcock