ceph/src/boost/libs/graph/example/hawick_circuits.cpp

   1 // Copyright Louis Dionne 2013
   2
   3 // Use, modification and distribution is subject to the Boost Software
   4 // License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy
   5 // at http://www.boost.org/LICENSE_1_0.txt)
   6
   7 #include <boost/assert.hpp>
   8 #include <boost/graph/directed_graph.hpp>
   9 #include <boost/graph/graph_traits.hpp>
  10 #include <boost/graph/hawick_circuits.hpp>
  11 #include <boost/lexical_cast.hpp>
  12 #include <boost/next_prior.hpp>
  13 #include <boost/property_map/property_map.hpp>
  14 #include <cstdlib>
  15 #include <iostream>
  16 #include <iterator>
  17 #include <map>
  18
  19
  20 template <typename OutputStream>
  21 struct cycle_printer
  22 {
  23     cycle_printer(OutputStream& stream)
  24         : os(stream)
  25     { }
  26
  27     template <typename Path, typename Graph>
  28     void cycle(Path const& p, Graph const& g)
  29     {
  30         if (p.empty())
  31             return;
  32
  33         // Get the property map containing the vertex indices
  34         // so we can print them.
  35         typedef typename boost::property_map<
  36                     Graph, boost::vertex_index_t
  37                 >::const_type IndexMap;
  38
  39         IndexMap indices = get(boost::vertex_index, g);
  40
  41         // Iterate over path printing each vertex that forms the cycle.
  42         typename Path::const_iterator i, before_end = boost::prior(p.end());
  43         for (i = p.begin(); i != before_end; ++i) {
  44             os << get(indices, *i) << " ";
  45         }
  46         os << get(indices, *i) << '\n';
  47     }
  48     OutputStream& os;
  49 };
  50
  51
  52 // VertexPairIterator is an iterator over pairs of whitespace separated
  53 // vertices `u` and `v` representing a directed edge from `u` to `v`.
  54 template <typename Graph, typename VertexPairIterator>
  55 void build_graph(Graph& graph, unsigned int const nvertices,
  56                  VertexPairIterator first, VertexPairIterator last) {
  57     typedef boost::graph_traits<Graph> Traits;
  58     typedef typename Traits::vertex_descriptor vertex_descriptor;
  59     std::map<unsigned int, vertex_descriptor> vertices;
  60
  61     for (unsigned int i = 0; i < nvertices; ++i)
  62         vertices[i] = add_vertex(graph);
  63
  64     for (; first != last; ++first) {
  65         unsigned int u = *first++;
  66
  67         BOOST_ASSERT_MSG(first != last,
  68             "there is a lonely vertex at the end of the edge list");
  69
  70         unsigned int v = *first;
  71
  72         BOOST_ASSERT_MSG(vertices.count(u) == 1 && vertices.count(v) == 1,
  73             "specified a vertex over the number of vertices in the graph");
  74
  75         add_edge(vertices[u], vertices[v], graph);
  76     }
  77     BOOST_ASSERT(num_vertices(graph) == nvertices);
  78 }
  79
  80
  81 int main(int argc, char const* argv[]) {
  82     if (argc < 2) {
  83         std::cout << "usage: " << argv[0] << " num_vertices < input\n";
  84         return EXIT_FAILURE;
  85     }
  86
  87     unsigned int num_vertices = boost::lexical_cast<unsigned int>(argv[1]);
  88     std::istream_iterator<unsigned int> first_vertex(std::cin), last_vertex;
  89     boost::directed_graph<> graph;
  90     build_graph(graph, num_vertices, first_vertex, last_vertex);
  91
  92     cycle_printer<std::ostream> visitor(std::cout);
  93     boost::hawick_circuits(graph, visitor);
  94
  95     return EXIT_SUCCESS;
  96 }