Re: [Boost-users] Using Coroutines in the Visitor Pattern (use-case: BGL event visitor)

Subject: Re: [Boost-users] Using Coroutines in the Visitor Pattern (use-case: BGL event visitor)
From: Nat Goodspeed (nat_at_[hidden])
Date: 2016-01-13 20:20:31

On Wed, Nov 18, 2015 at 7:09 AM, alex <alexhighviz_at_[hidden]> wrote:

> Jeremiah Willcock gave a good description of how this could work:
>
> http://lists.boost.org/Archives/boost/2012/07/195300.php
>
> The way he describes it is really using coroutines instead of the visitor
> pattern.

My example in previous mail only forwards a single visitor event, as
described in the original problem statement. If you wanted to pass
additional dijkstra_shortest_path() visitor events through the
inversion of control, you could use an approach similar to the
recursive SAX parsing example. That's what I think you're citing from
Jeremiah's linked mail.

> I think there are two options:
> 1. Let your visitor throw an exception to get out of the dijkstra shortest
> path function; use some version of the function that skips initialization to
> resume again (the existing dijkstra_shortest_path_no_init is not good
> enough, so you would have to make one).

Possible, but yes, you would have to reimplement the algorithm to
pursue this approach.

> 2. Reimplement the dijkstra function as a coroutine.

Fortunately this is not necessary, as shown in previous mail. You can
simply call dijkstra_shortest_paths() in a coroutine.

> I have implemented both, but have only really used option 1; whereas option
> 2 remained a toy experiment. In both cases the tricky part was to properly
> initialize and keep track of(and not re-initialize on resume) all parameters
> that are input to the dijkstra function, i.e. color_map, queue,
> distance_map, etc.

Using a real coroutine makes that problem go away entirely. To the
dijkstra_shortest_paths() algorithm running in a coroutine, the
operation of passing each examined vertex to the consuming program
simply looks like a function call. All existing state is preserved.
Each time it returns from that function call, it resumes as it would
with any ordinary visitor.

> I used the lightweight stackless coroutine of Boost ASIO.

Aha! That would indeed cause you the troubles you describe. This is
the great benefit of using *stackful* coroutines a la Boost.Coroutine:
you can run a recursive algorithm on one stack, completely
independently of the control flow on another stack.

>>The control flow I need would probably look like this: start the first
>>Dijkstra search, on its first vertex it visits, "jump back out" and
>>start the second Dijkstra visitor. From there on ping-pong between the
>>two visitors exclusively. And I'm not sure this is possible with the
>>Coroutine approach.

> It depends how much you are willing to re-implement. It is possible in
> principle

It is possible in practice, without any reimplementation at all, as
shown in previous mail.