97 lines
3.0 KiB
C++
97 lines
3.0 KiB
C++
// 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;
|
|
}
|