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

Subject: [Boost-users] Using Coroutines in the Visitor Pattern (use-case: BGL event visitor)
From: Daniel Hofmann (daniel_at_[hidden])
Date: 2015-11-17 10:55:16

(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.

In terms of the BGL this would roughly look like the following
(simplified, with synchronization and visitor omitted):

    Vertex middle;
    async(dijkstra_shortest_paths(g, start, visitor(v{middle})));
    async(dijkstra_shortest_paths(g, target, visitor(v{middle})));

where the visitors single-step all vertices in their examine_vertex
callback [2] and check if they met in the middle.

While this is quite easy to implement with threading, is has its
downsides, mainly in synchronization for this ping-pong play between the
two visitors, resulting in contention on the synchronization locks. But
also the overhead of using threads might be too high for smaller graphs.

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.

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'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.

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.

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" :)

Cheers,
Daniel J H

[1]
http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/dijkstra_shortest_paths.html

[2] http://www.boost.org/doc/libs/1_59_0/libs/graph/doc/DijkstraVisitor.html

[3]
http://www.boost.org/doc/libs/1_59_0/libs/coroutine/doc/html/coroutine/motivation.html#coroutine.motivation.recursive_sax_parsing