| // Copyright Louis Dionne 2013 |
| |
| // Use, modification and distribution is subject to 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/assert.hpp> |
| #include <boost/graph/directed_graph.hpp> |
| #include <boost/graph/graph_traits.hpp> |
| #include <boost/graph/hawick_circuits.hpp> |
| #include <boost/lexical_cast.hpp> |
| #include <boost/next_prior.hpp> |
| #include <boost/property_map/property_map.hpp> |
| #include <cstdlib> |
| #include <iostream> |
| #include <iterator> |
| #include <map> |
| |
| |
| template <typename OutputStream> |
| struct cycle_printer |
| { |
| cycle_printer(OutputStream& stream) |
| : os(stream) |
| { } |
| |
| template <typename Path, typename Graph> |
| void cycle(Path const& p, Graph const& g) |
| { |
| if (p.empty()) |
| return; |
| |
| // Get the property map containing the vertex indices |
| // so we can print them. |
| typedef typename boost::property_map< |
| Graph, boost::vertex_index_t |
| >::const_type IndexMap; |
| |
| IndexMap indices = get(boost::vertex_index, g); |
| |
| // Iterate over path printing each vertex that forms the cycle. |
| typename Path::const_iterator i, before_end = boost::prior(p.end()); |
| for (i = p.begin(); i != before_end; ++i) { |
| os << get(indices, *i) << " "; |
| } |
| os << get(indices, *i) << '\n'; |
| } |
| OutputStream& os; |
| }; |
| |
| |
| // VertexPairIterator is an iterator over pairs of whitespace separated |
| // vertices `u` and `v` representing a directed edge from `u` to `v`. |
| template <typename Graph, typename VertexPairIterator> |
| void build_graph(Graph& graph, unsigned int const nvertices, |
| VertexPairIterator first, VertexPairIterator last) { |
| typedef boost::graph_traits<Graph> Traits; |
| typedef typename Traits::vertex_descriptor vertex_descriptor; |
| std::map<unsigned int, vertex_descriptor> vertices; |
| |
| for (unsigned int i = 0; i < nvertices; ++i) |
| vertices[i] = add_vertex(graph); |
| |
| for (; first != last; ++first) { |
| unsigned int u = *first++; |
| |
| BOOST_ASSERT_MSG(first != last, |
| "there is a lonely vertex at the end of the edge list"); |
| |
| unsigned int v = *first; |
| |
| BOOST_ASSERT_MSG(vertices.count(u) == 1 && vertices.count(v) == 1, |
| "specified a vertex over the number of vertices in the graph"); |
| |
| add_edge(vertices[u], vertices[v], graph); |
| } |
| BOOST_ASSERT(num_vertices(graph) == nvertices); |
| } |
| |
| |
| int main(int argc, char const* argv[]) { |
| if (argc < 2) { |
| std::cout << "usage: " << argv[0] << " num_vertices < input\n"; |
| return EXIT_FAILURE; |
| } |
| |
| unsigned int num_vertices = boost::lexical_cast<unsigned int>(argv[1]); |
| std::istream_iterator<unsigned int> first_vertex(std::cin), last_vertex; |
| boost::directed_graph<> graph; |
| build_graph(graph, num_vertices, first_vertex, last_vertex); |
| |
| cycle_printer<std::ostream> visitor(std::cout); |
| boost::hawick_circuits(graph, visitor); |
| |
| return EXIT_SUCCESS; |
| } |