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: alex (alexhighviz_at_[hidden])
Date: 2015-11-18 07:09:38

>-----Original Message-----
>From: Boost-users [mailto:boost-users-bounces_at_[hidden]] On Behalf Of
>Daniel Hofmann
>Sent: 17 November 2015 15:55
>To: boost-users_at_[hidden]
>Subject: [Boost-users] Using Coroutines in the Visitor Pattern (use-case:
BGL
>event visitor)
>
>(Disclaimer: this is not only specific to BGL, I can think of similar
>use-cases where the visitor pattern is used --- I will still explain it
>in the BGL context, as it is probably easier to understand)
>
>
>Suppose you have a BGL graph and want to implement s-t shortest path
>queries. It is possible to do this by using a bi-directional approach,
>that is starting a Dijkstra search [1] from the start and starting a
>additional Dijkstra search from the target. As soon as they "meet in the
>middle", you can unpack the two sub-paths.
>
>[snip]
>
>It then came to my mind that I could use Coroutines for cooperative
>multitasking, without the downsides that come with threading.
>
>My idea was to invert the callbacks using Coroutines as it is shown in
>the SAX parsing example [3], in order to get a lazy range of vertices
>each visitor examines. I then could simply walk the two ranges,
>terminating as soon as there is the same element in both.

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.

>
>
>But due to way the dijkstra_shortest_path function adds an additional
>level of indirection I failed to implement this, and I have strong
>doubts that it is possible with Coroutines at all.
I>
>I'm mainly struggling with wrapping my head around stopping and resuming
>the dijkstra_shortest_path function, when all I can modify is the
>visitor it takes. That is, the reason I can not make it work is that I
>can not launch two dijkstra_shortest_path functions asynchronously with
>just Coroutines.
>

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). 
2. Reimplement the dijkstra function as 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. 

https://github.com/ahhz/resumable_dijkstra 

I used the lightweight stackless coroutine of Boost ASIO. 

http://www.boost.org/doc/libs/1_59_0/doc/html/boost_asio/reference/coroutine
.html 

>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

>I appreciate any tips in this regard, even if it's a "just use your 15
>lines of threading code instead of trying to be fancy" :)
>

I think it would be great to have a fancy solution for this in BGL.