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: Nat Goodspeed (nat_at_[hidden])
Date: 2016-01-13 20:04:02

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;
}