
Boost Users : 
Subject: Re: [Boostusers] Using Coroutines in the Visitor Pattern (usecase: BGL event visitor)
From: Daniel Hofmann (daniel_at_[hidden])
Date: 20160118 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/danieljh/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 st shortest path
>> queries. It is possible to do this by using a bidirectional 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 subpaths.
>>
>> 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 singlestep 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 pingpong 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, LieQuan 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;
> }
> _______________________________________________
> Boostusers mailing list
> Boostusers_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boostusers
>
Boostusers list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net