Boost logo

Boost :

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 <> 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
> ?
> 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

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