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