Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function

Subject: Re: [boost] [graph][heap][coroutine] interruptable dijkstra shortest path function
From: Alex Hagen-Zanker (ahh34_at_[hidden])
Date: 2012-10-05 08:07:07

On 05/10/2012 02:36, Dave Abrahams wrote:
> on Sat Sep 22 2012, Alex Hagen-Zanker <ahh34-AT-cam.ac.uk> wrote:
>
>> [apologies for double posting, send it to wrong list before]
>> 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.
> ...
>
> Have you seen
> http://cpp-next.com/archive/2012/09/portable-stackless-coroutines-in-one-header/
> ?
>
> This approach might be sufficiently lightweight that it would allow us
> to maintain one version of the algorithm with some macros.
>

It is very nice indeed. I did not try it with the shortest path 
algorithm, but instead a simple sum algorithm where yield is used to get 
the running total.

Using the stackless boost asio coroutine from the link you provided is 
just as simple as using the proposed boost coroutine.

Summing  10,000,000 times the number 2 while yielding intermediate sums 
gave me the following results:

sum plain      : 20000000 time: 0.01
sum fragmented : 20000000 time: 0.232
sum boost coro : 20000000 time: 0.448
sum asio coro  : 20000000 time: 0.034

Without yielding intermediate results, I got the following:

sum plain      : 20000000 time: 0.008
sum fragmented : 20000000 time: 0.029
sum boost coro : 20000000 time: 0.027
sum asio coro  : 20000000 time: 0.012

I'd say it it definately worth investigating to use the boost asio 
method as a means of creating algorithm objects. From this example it 
appears that:

1. It is an efficient way of interrupting and resuming algorithms.
2. It leaves the algorithms coded in a readable state, although it seems 
that all local variables should become member variables.
3. If you decide not to interrupt the algorithm, the additional cost due 
to being part of an algorithm object is less than for the alternatives.

I am not working on this anymore, but please see the source for above 
trial in the attachment.

Kind regards, Alex