]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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(). | |
f67539c2 | 22 | template < typename OutputStream > struct cycle_printer |
7c673cae | 23 | { |
f67539c2 | 24 | cycle_printer(OutputStream& stream) : os(stream) {} |
7c673cae | 25 | |
f67539c2 | 26 | template < typename Path, typename Graph > |
7c673cae FG |
27 | void cycle(const Path& p, const Graph& g) |
28 | { | |
29 | // Get the property map containing the vertex indices | |
30 | // so we can print them. | |
f67539c2 TL |
31 | typedef |
32 | typename property_map< Graph, vertex_index_t >::const_type IndexMap; | |
7c673cae FG |
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(); | |
f67539c2 TL |
37 | for (i = p.begin(); i != end; ++i) |
38 | { | |
7c673cae FG |
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; | |
f67539c2 TL |
48 | typedef graph_traits< Graph >::vertex_descriptor Vertex; |
49 | typedef graph_traits< Graph >::edge_descriptor Edge; | |
7c673cae | 50 | |
f67539c2 | 51 | int main(int argc, char* argv[]) |
7c673cae FG |
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 | |
f67539c2 | 58 | cycle_printer< ostream > vis(cout); |
7c673cae FG |
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 | //] |