Re: [boost] [graph] interest in resumable dijkstra?

Subject: Re: [boost] [graph] interest in resumable dijkstra?
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2012-07-13 14:24:58

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