
Boost : 
Subject: Re: [boost] [graph] interest in resumable dijkstra?
From: Alex HagenZanker (ahh34_at_[hidden])
Date: 20120807 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 HagenZanker 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 3minute walking catchments for all busstops 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 rerun 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 acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk