1 // (C) Copyright Andrew Sutton 2007
2 //
3 // Use, modification and distribution are subject to the
4 // Boost Software License, Version 1.0 (See accompanying file
5 // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
6
7 //[tiernan_print_cycles
8 #include <iostream>
9
10 #include <boost/graph/directed_graph.hpp>
11 #include <boost/graph/tiernan_all_cycles.hpp>
12
13 #include "helper.hpp"
14
15 using namespace std;
16 using namespace boost;
17
18 // The cycle_printer is a visitor that will print the path that comprises
19 // the cycle. Note that the back() vertex of the path is not the same as
20 // the front(). It is implicit in the listing of vertices that the back()
21 // vertex is connected to the front().
22 template < typename OutputStream > struct cycle_printer
23 {
cycle_printercycle_printer24 cycle_printer(OutputStream& stream) : os(stream) {}
25
26 template < typename Path, typename Graph >
cyclecycle_printer27 void cycle(const Path& p, const Graph& g)
28 {
29 // Get the property map containing the vertex indices
30 // so we can print them.
31 typedef
32 typename property_map< Graph, vertex_index_t >::const_type IndexMap;
33 IndexMap indices = get(vertex_index, g);
34
35 // Iterate over path printing each vertex that forms the cycle.
36 typename Path::const_iterator i, end = p.end();
37 for (i = p.begin(); i != end; ++i)
38 {
39 os << get(indices, *i) << " ";
40 }
41 os << endl;
42 }
43 OutputStream& os;
44 };
45
46 // Declare the graph type and its vertex and edge types.
47 typedef directed_graph<> Graph;
48 typedef graph_traits< Graph >::vertex_descriptor Vertex;
49 typedef graph_traits< Graph >::edge_descriptor Edge;
50
main(int argc,char * argv[])51 int main(int argc, char* argv[])
52 {
53 // Create the graph and read it from standard input.
54 Graph g;
55 read_graph(g, cin);
56
57 // Instantiate the visitor for printing cycles
58 cycle_printer< ostream > vis(cout);
59
60 // Use the Tiernan algorithm to visit all cycles, printing them
61 // as they are found.
62 tiernan_all_cycles(g, vis);
63
64 return 0;
65 }
66 //]
67