123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596 |
- // 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;
- }
|