Dear Jeremiah and Boost list,
I'd like to suggest for inclusion in Boost Graph Library an algorithm object
version of dijkstra shortest path algorithm.
The following is an example how it can be used, assuming some graph, source
node(s) and threshold distance:
auto dijkstra make_dijkstra_object(graph, source_range);
while(dijkstra()) {
auto v = dijkstra.get_vertex();
auto distance_map = dijkstra.get();
if(get(distance_map, v) > threshold) break;
}
It is very close to what Jeremiah suggested 2 years ago:
http://lists.boost.org/Archives/boost/2012/07/195300.php
The main advantage for me is the possibility to interweave several shortest
path searches.
The algorithm object makes use of the stackless coroutine in Boost ASIO,
which means it is relatively lightweight. However, on a large graph the
algorithm object still takes about 20% more time than the normal
dijkstra_shortest_path.
The operator() progresses the algorithm to the next control point. Control
points can correspond to all places where breadth_first_search invokes its
visitor, but it is specified in compile time at which potential control
points the algorithm actually yields. The default is to halt at the
finish_vertex control point only.
The make_dijkstra_object function can take all parameters through
bgl_named_parameters, including the priority queue and the color map, which
the existing dijkstra_shortest_path does not support.
The code is part of the following project:
http://code.google.com/p/resumable-dijkstra
The algorithm object is defined here:
http://code.google.com/p/resumable-dijkstra/source/browse/trunk/resumable-di
jkstra/blink/graph/dijkstra_object.hpp
I look forward to hear if there are any takers this time.
Best wishes, Alex
