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