-----Original Message----- From: Boost-users [mailto:boost-users-bounces@lists.boost.org] On Behalf Of Daniel Hofmann Sent: 17 November 2015 15:55 To: boost-users@lists.boost.org 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.