Boost logo

Boost :

Subject: [boost] [graph] interest in resumable dijkstra?
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-07-13 12:25:09


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?

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.

To see for yourself: http://people.pwf.cam.ac.uk/ahh34/dijkstra_test.zip

I am interested to hear your opinion.

With kind regards, Alex


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk