Boost.Coroutine meets Boost.Graph

coroutine.cc

#include <vector>
#include <iostream>
#include <iterator>

#include <boost/graph/compressed_sparse_row_graph.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/breadth_first_search.hpp>

#include <boost/coroutine/all.hpp>


using Graph = boost::compressed_sparse_row_graph<boost::directedS>;
using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor;
using Edge = typename boost::graph_traits<Graph>::edge_descriptor;

using Coroutine = boost::coroutines::asymmetric_coroutine<Vertex>;


struct DiscoverVisitor final : boost::default_bfs_visitor {
  explicit DiscoverVisitor(Coroutine::push_type& sink_) : sink{sink_} {}

  void discover_vertex(const Vertex vertex, const Graph&) { sink(vertex); }

  Coroutine::push_type& sink;
};


Graph makeGraph() {
  /*
   * 0 -> 1 -> 2
   * ^    |    |
   * |    v    v
   * 5 <- 4 <- 3
   */
  std::vector<Vertex> sources{0, 1, 1, 2, 3, 4, 5};
  std::vector<Vertex> targets{1, 2, 4, 3, 4, 5, 0};
  const auto numVertices = 6u;

  return {boost::construct_inplace_from_sources_and_targets, sources, targets, numVertices};
}


int main() {
  const auto graph = makeGraph();
  print_graph(graph, "0123456");

  const auto source = 0u;

  Coroutine::pull_type generator{[&](Coroutine::push_type& sink) { //
    breadth_first_search(graph, source, visitor(DiscoverVisitor{sink}));
  }};

  for (const auto vertex : generator) {
    std::cout << vertex << std::endl;
  }
}

=> https://github.com/daniel-j-h/cppnow2016