1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768 |
- // (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;
- }
- //]
|