69 lines
1.9 KiB
C++
69 lines
1.9 KiB
C++
// (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;
|
|
}
|
|
//]
|