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,
>> 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
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
>> 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
-- Jeremiah Willcock
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk