Boost logo

Boost :

Subject: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-09-22 21:27:55

[apologies for double posting, send it to wrong list before]

A few months ago I posted here to gauge interest for an interruptable
and resumable version of the dijkstra_shortest_path algorithm. The
initial response was positive, but Jeremiah considered the proposed
solution lacking compared to an algorithm object model that inverts the
control over the algorithm,

Additional to my original solution, I now have two implementations of
the algorithm object model.

1. Visitor based interruption. This is my original approach. It
separates the algorithm into an init and main function. The main
function asks the visitor if it should be halted afer each iteration.
After halting, the main function can be used to resume the calculation.

auto dijkstra = make_dijkstra_object(graph, named_parameters);
dijkstra.expand( interruptor);
dijkstra.expand( other_interruptor);

auto distance_map = dijkstra.get<vertex_distance_t>();
auto color_map = dijkstra.get<vertex_color_t>();

2. Algorithm object implementation. This was suggested by Jeremiah. The
algorithm object iterates from control point to control point in the
algorithm. Giving at each stop access to the intermediate results of the
algorithm. The two implementations are:
a) Using the [Coroutine] library that is currently under review to step
in and out of the function.
b) Fragmenting the function into many subfunctions that are chained
together and the other works by fragmenting the original algorithm into
a number of small interlinked functions starting at one control point
and returning at the next.

The interface of a and b is exactly the same and it works like this:

auto dijkstra = make_dijkstra_object(graph, sources, named_parameters);
while( )
   control_point cp = dijkstra.get_control_point();
   vertex u = dijkstra.get_u();
   auto distance_map = dijkstra.get<vertex_distance_t>();
   if(cp == cp_finish_vertex && get(distance_map, u) > 42)
     cout << "far enough" << endl;
auto distance_map = dijkstra.get<vertex_distance_t>();

The algorithm object offers most flexibility for interweaving multiple
searches. The visitor based solution on the other hand is more
efficient. The latter has no loss in performance compared to the
existing dijkstra functions. The coroutine algorithm object was
extremely easy to implement but it is not very efficient. Does anybody
have a suggestion how that can improve?

Besides these interruptable and resumable shortest path searches, there
are a few more advantages to the implementation.

a. All dijkstra parameters are bundled in a light-weight dijkstra_state
object that is returned by algorithms, giving direct access to all
results of the algorithm, for instance:

auto dijkstra_state = dijkstra_shortest_paths(graph, sources,
no_named_parameters() );
auto distance_map = dijkstra_state.get<vertex_distance_t>();

b. Named parameters (old style) are also used for the priority queue and
the color map
c. Boost.Heap mutable queues can be used with Boost.Graph via the named
parameter interface. It doesn't help performance now, but may be a good
base for experimentation.
d. Separation of the dijkstra shortest path algorithm in init and main
function makes it easier to provide custom initialization. For instance:
multiple sources or only re-initializing changed vertices

Can anybody use this? The latest version is here:

Kind regards, Alex

p.s. below are timings for a large graph:


2090 ms. Boost Graph Library
2121 ms. With interruption visitor
5601 ms. With Coroutine(*)
2621 ms. With fragmented functions (*)
2840 ms. With Boost.Heap
(*) halting at all control points of the dijkstra visitor

Boost list run by bdawes at, gregod at, cpdaniel at, john at