[prev in list] [next in list] [prev in thread] [next in thread] 

List:       boost-users
Subject:    [Boost-users] [graph][heap][coroutine] interruptable dijkstra shortest path function
From:       Alex Hagen-Zanker <ahh34 () cam ! ac ! uk>
Date:       2012-09-23 0:57:56
Message-ID: 505E5E94.1020002 () cam ! ac ! uk
[Download RAW message or body]

Hi,

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.init_from_sources(sources);
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(dijkstra.next() )
{
   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;
     break;
   }
}
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: 
http://people.pwf.cam.ac.uk/ahh34/dijkstra.zip

Kind regards, Alex

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

bimba_6M.obj...

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-users mailing list
Boost-users@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
[prev in list] [next in list] [prev in thread] [next in thread]