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: Daniel Hofmann (daniel_at_[hidden])
Date: 2016-01-18 08:54:43

Nat, your solution is beautiful and I'm glad you posted it!

I played around with your approach for a bit and it is really easy to
grasp the main idea behind it once you have seen the general technique.

For example this is a small breadth first search example I came up with:

> https://gist.github.com/daniel-j-h/e405071c553ea660c4ce

where you can just iterate over the vertices in breadth first order, due
to how the control flow is inverted.

I love it, and I think pairing Boost.Coroutine and Boost.Graph is simply
beautiful and probably even worth writing a blog post or a small article
about it.

Cheers,
Daniel J H

On 01/14/2016 02:04 AM, Nat Goodspeed wrote:
> On Tue, Nov 17, 2015 at 10:55 AM, Daniel Hofmann <daniel_at_[hidden]> wrote:
> 
>> 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.
>>
>> 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.
> 
> Great idea! I've thought for a year or so that the BGL and coroutines
> might be a fruitful pairing. What has stopped me to this point is my
> almost total ignorance of the BGL. Your post nudged me to take action.
> I'm sorry it has taken me so long to get back to you on this, but I
> needed a sufficient chunk of free time to poke at the BGL.
> 
>> 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.
> 
> It is possible. See below.
> 
>> 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.
> 
> See below...
> 
>> 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.
> 
> You're absolutely right.
> 
>> I appreciate any tips in this regard
> 
> I apologize for the clumsiness of my BGL use; as I said, I'm a BGL
> newbie. But I think the working program below functions as proof of
> concept. Perhaps you could clean up the graph definition and
> construction?
> 
> ==== fruit on the bottom ====
> 
> // Portions of this source were excerpted from
> // http://www.boost.org/doc/libs/release/libs/graph/example/dave.cpp
> // and are therefore copyrighted:
> 
> //=======================================================================
> // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
> // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
> //
> // Distributed under the Boost Software License, Version 1.0. (See
> // accompanying file LICENSE_1_0.txt or copy at
> // http://www.boost.org/LICENSE_1_0.txt)
> //=======================================================================
> 
> #include <boost/coroutine/all.hpp>
> 
> #include <boost/graph/adjacency_list.hpp>
> #include <boost/graph/visitors.hpp>
> #include <boost/graph/dijkstra_shortest_paths.hpp>
> #include <boost/graph/graph_utility.hpp>
> 
> #include <set>
> 
> using namespace boost;
> 
> typedef property<vertex_color_t, default_color_type,
>          property<vertex_distance_t,int> > VProperty;
> typedef int weight_t;
> typedef property<edge_weight_t,weight_t> EProperty;
> 
> // Our Graph type
> typedef adjacency_list<vecS, vecS, bidirectionalS, VProperty, EProperty > Graph;
> // and its Vertex type
> typedef boost::graph_traits<Graph>::vertex_descriptor Vertex;
> // coroutine type producing Vertex values
> typedef boost::coroutines::asymmetric_coroutine<Vertex> coro_t;
> 
> // Name and ID numbers for the vertices
> char name[] = "abcdefg";
> enum { a, b, c, d, e, f, g, N};
> 
> // Our Dijkstra visitor must bind a push_type coroutine, so write the class
> // out by hand instead of using make_dijkstra_visitor().
> class Visitor
> {
> public:
>     Visitor(coro_t::push_type& sink):
>         mSink(sink)
>     {}
> 
>     // irrelevant event callbacks
>     void initialize_vertex(Vertex u, const Graph& g) {}
>     template <typename Edge>
>     void examine_edge(Edge e, const Graph& g) {}
>     void discover_vertex(Vertex u, const Graph& g) {}
>     template <typename Edge>
>     void edge_relaxed(Edge e, const Graph& g) {}
>     template <typename Edge>
>     void edge_not_relaxed(Edge e, const Graph& g) {}
>     void finish_vertex(Vertex u, const Graph& g) {}
> 
>     // the one event callback about which we care
>     void examine_vertex(Vertex u, const Graph& g)
>     {
>         mSink(u);
>     }
> 
> private:
>     coro_t::push_type& mSink;
> };
> 
> int
> main(int , char* [])
> {
>     Graph G(N);
>     boost::property_map<Graph, vertex_index_t>::type
>         vertex_id = get(vertex_index, G);
> 
>     std::vector<weight_t> distance(N, (std::numeric_limits<weight_t>::max)());
> 
>     typedef std::pair<int,int> E;
> 
>     E edges[] = { E(a,c), E(a,d),
>                   E(b,a), E(b,d),
>                   E(c,f),
>                   E(d,c), E(d,e), E(d,f),
>                   E(e,b), E(e,g),
>                   E(f,e), E(f,g) };
> 
>     int weight[] = { 3, 4,
>                      6, 8,
>                      12,
>                      7, 0, 5,
>                      10, 3,
>                      1, 2 };
> 
>     for (int i = 0; i < (sizeof(edges)/sizeof(edges[0])); ++i)
>     {
>         add_edge(edges[i].first, edges[i].second, weight[i], G);
>         add_edge(edges[i].second, edges[i].first, weight[i], G);
>     }
> 
>     // starting from Vertex a
>     coro_t::pull_type from_a([&G, &distance, vertex_id]
>                              (coro_t::push_type& sink){
>         boost::dijkstra_shortest_paths(
>             G, vertex(a, G),
>             distance_map(make_iterator_property_map(distance.begin(), vertex_id,
>                                                     distance[0])).
>             visitor(Visitor(sink)));
>     });
> 
>     // starting from Vertex g
>     coro_t::pull_type from_g([&G, &distance, vertex_id]
>                              (coro_t::push_type& sink){
>         boost::dijkstra_shortest_paths(
>             G, vertex(g, G),
>             distance_map(make_iterator_property_map(distance.begin(), vertex_id,
>                                                     distance[0])).
>             visitor(Visitor(sink)));
>     });
> 
>     std::set<Vertex> visited_from_a, visited_from_g;
>     Vertex middle = N;
> 
>     while (from_a && from_g)
>     {
>         // peek at the next Vertex encountered starting from a
>         Vertex next = from_a.get();
>         std::cout << "from_a returned " << name[next] << std::endl;
>         // did we already encounter that starting from g?
>         if (visited_from_g.find(next) != visited_from_g.end())
>         {
>             // if so, we're done!
>             middle = next;
>             break;
>         }
>         // not done, capture this Vertex
>         visited_from_a.insert(next);
>         // and step the Dijkstra search from a by one Vertex
>         from_a();
> 
>         // peek at the next Vertex encountered starting from g
>         next = from_g.get();
>         std::cout << "from_g returned " << name[next] << std::endl;
>         // did we already encounter that starting from a?
>         if (visited_from_a.find(next) != visited_from_a.end())
>         {
>             // if so, we're done!
>             middle = next;
>             break;
>         }
>         // not done, capture this Vertex
>         visited_from_g.insert(next);
>         // and step the Dijkstra search from g by one Vertex
>         from_g();
>     }
> 
>     if (middle == N)
>     {
>         std::cout << "Cannot make ends meet" << std::endl;
>     }
>     else
>     {
>         std::cout << "Searches met at Vertex " << name[middle] << std::endl;
>     }
> 
>     return 0;
> }
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>