On Fri, 13 Jul 2012, Alex Hagen-Zanker wrote:
Dear boost-list,
I placed the BGL algorithm of the dijkstra_shortest_path in a class, with the creation and initialization part separate from the main algorithm. This allows interrupting, resetting and resuming the algorithm. Would this be of interest to anybody?
Yes, definitely.
The following function call:
dijkstra_shortest_path(graph, orig, parameter_pack);
is separated into:
auto dijkstra = make_dijkstra(graph, parameter_pack); dijkstra.init_from_origin(orig /*, optional_visitor*/); dijkstra.expand(/*optional_visitor*/);
The make_dijkstra() function reads all parameters from the parameter_pack including color_map and priority_queue Visitors interrupt the calculation using a do_intterrupt() callback instead of throwing an exception. The function expand() can be called repeatedly, each time with another visitor. The implementation requires C++11, because of auto and lambda's, it also relies on the following patch: https://svn.boost.org/trac/boost/ticket/7130.
It would be nicer to have it be C++03, since nothing else in BGL requires C++11 yet.
To see for yourself: http://people.pwf.cam.ac.uk/ahh34/dijkstra_test.zip
I am interested to hear your opinion.
I haven't had a chance to look at it yet, but I'm definitely interested in putting it in when it's ready. -- Jeremiah Willcock