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-13 11:36:10

On 10/08/2012 21:12, Jeremiah Willcock wrote:
>
> OK.  I think either your model for suspension or the algorithm object 
> model (what I had proposed) will work for that case.

It seems that we have established now that the proposed dijkstra_class 
is actually useful. It makes something possible that was not possible 
before: interweaving dijkstra shortest path searches. And it is making 
some other things easier than they were before: using dijkstra shortest 
path with multiple sources, re-using property maps by re-initializing 
properties for changed vertices only. One other improvement is that the 
priority queue and color map can now be set in the named parameters, 
making it easier to customize the algorithm.

However, the algorithm object model has been long on the wish-list of 
the BGL and my model for suspension is not as flexible, generic, and - 
from your point of view - simple. The algorithm object model may be 
better attuned to the direction that you wish to take BGL. Perhaps you 
already have some working proto-type? I find it hard to imagine an 
efficient implementation of the algorithm object model, because there 
are so many potential break points in the algorithm and each time the 
algorithm is resumed it would have to work out where it was left.

My implementation on the other hand tries to stay close to the current 
BGL. It uses the BGL named parameters. There is only one potential break 
point, which is the - from my point of view - natural outer while() loop 
that processes all vertices in the queue, all other events are handled 
using the visitors that are already supported by the BGL.

How would you like to take this forward?

Kind regards, Alex

p.s. I put a latest version online, that uses the null_property_map and 
also support graphs of unknown size. 
http://people.pwf.cam.ac.uk/ahh34/dijkstra.zip