// (C) Copyright Andrew Sutton 2007
//
// Use, modification and distribution are subject to the
// Boost Software License, Version 1.0 (See accompanying file
// LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)

//[tiernan_print_cycles
#include <iostream>

#include <boost/graph/directed_graph.hpp>
#include <boost/graph/tiernan_all_cycles.hpp>

#include "helper.hpp"

using namespace std;
using namespace boost;

// The cycle_printer is a visitor that will print the path that comprises
// the cycle. Note that the back() vertex of the path is not the same as
// the front(). It is implicit in the listing of vertices that the back()
// vertex is connected to the front().
template <typename OutputStream>
struct cycle_printer
{
    cycle_printer(OutputStream& stream)
        : os(stream)
    { }

    template <typename Path, typename Graph>
    void cycle(const Path& p, const Graph& g)
    {
        // Get the property map containing the vertex indices
        // so we can print them.
        typedef typename property_map<Graph, vertex_index_t>::const_type IndexMap;
        IndexMap indices = get(vertex_index, g);

        // Iterate over path printing each vertex that forms the cycle.
        typename Path::const_iterator i, end = p.end();
        for(i = p.begin(); i != end; ++i) {
            os << get(indices, *i) << " ";
        }
        os << endl;
    }
    OutputStream& os;
};

// Declare the graph type and its vertex and edge types.
typedef directed_graph<> Graph;
typedef graph_traits<Graph>::vertex_descriptor Vertex;
typedef graph_traits<Graph>::edge_descriptor Edge;

int
main(int argc, char *argv[])
{
    // Create the graph and read it from standard input.
    Graph g;
    read_graph(g, cin);

    // Instantiate the visitor for printing cycles
    cycle_printer<ostream> vis(cout);

    // Use the Tiernan algorithm to visit all cycles, printing them
    // as they are found.
    tiernan_all_cycles(g, vis);

    return 0;
}
//]