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 template < typename OutputStream > struct cycle_printer
20 {
cycle_printercycle_printer21 cycle_printer(OutputStream& stream) : os(stream) {}
22
23 template < typename Path, typename Graph >
cyclecycle_printer24 void cycle(Path const& p, Graph const& g)
25 {
26 if (p.empty())
27 return;
28
29 // Get the property map containing the vertex indices
30 // so we can print them.
31 typedef typename boost::property_map< Graph,
32 boost::vertex_index_t >::const_type IndexMap;
33
34 IndexMap indices = get(boost::vertex_index, g);
35
36 // Iterate over path printing each vertex that forms the cycle.
37 typename Path::const_iterator i, before_end = boost::prior(p.end());
38 for (i = p.begin(); i != before_end; ++i)
39 {
40 os << get(indices, *i) << " ";
41 }
42 os << get(indices, *i) << '\n';
43 }
44 OutputStream& os;
45 };
46
47 // VertexPairIterator is an iterator over pairs of whitespace separated
48 // vertices `u` and `v` representing a directed edge from `u` to `v`.
49 template < typename Graph, typename VertexPairIterator >
build_graph(Graph & graph,unsigned int const nvertices,VertexPairIterator first,VertexPairIterator last)50 void build_graph(Graph& graph, unsigned int const nvertices,
51 VertexPairIterator first, VertexPairIterator last)
52 {
53 typedef boost::graph_traits< Graph > Traits;
54 typedef typename Traits::vertex_descriptor vertex_descriptor;
55 std::map< unsigned int, vertex_descriptor > vertices;
56
57 for (unsigned int i = 0; i < nvertices; ++i)
58 vertices[i] = add_vertex(graph);
59
60 for (; first != last; ++first)
61 {
62 unsigned int u = *first++;
63
64 BOOST_ASSERT_MSG(first != last,
65 "there is a lonely vertex at the end of the edge list");
66
67 unsigned int v = *first;
68
69 BOOST_ASSERT_MSG(vertices.count(u) == 1 && vertices.count(v) == 1,
70 "specified a vertex over the number of vertices in the graph");
71
72 add_edge(vertices[u], vertices[v], graph);
73 }
74 BOOST_ASSERT(num_vertices(graph) == nvertices);
75 }
76
main(int argc,char const * argv[])77 int main(int argc, char const* argv[])
78 {
79 if (argc < 2)
80 {
81 std::cout << "usage: " << argv[0] << " num_vertices < input\n";
82 return EXIT_FAILURE;
83 }
84
85 unsigned int num_vertices = boost::lexical_cast< unsigned int >(argv[1]);
86 std::istream_iterator< unsigned int > first_vertex(std::cin), last_vertex;
87 boost::directed_graph<> graph;
88 build_graph(graph, num_vertices, first_vertex, last_vertex);
89
90 cycle_printer< std::ostream > visitor(std::cout);
91 boost::hawick_circuits(graph, visitor);
92
93 return EXIT_SUCCESS;
94 }
95