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@trvx.org> 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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

On Mon, Jan 18, 2016 at 7:16 PM, Nat Goodspeed <nat@lindenlab.com> wrote:

On Mon, Jan 18, 2016 at 8:54 AM, Daniel Hofmann <daniel@trvx.org> wrote:

...

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.

Nice. I'm glad you're using the coroutine library's iterator support for range 'for'.

I meant to say, I also like your use of default_bfs_visitor. More elegant than my explicit visitor!