1 | // (C) Copyright 2007-2009 Andrew Sutton |
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 | #include <iostream> |
8 | |
9 | #include <boost/graph/graph_utility.hpp> |
10 | #include <boost/graph/undirected_graph.hpp> |
11 | #include <boost/graph/directed_graph.hpp> |
12 | #include <boost/graph/tiernan_all_cycles.hpp> |
13 | #include <boost/graph/erdos_renyi_generator.hpp> |
14 | |
15 | #include <boost/random/linear_congruential.hpp> |
16 | |
17 | using namespace std; |
18 | using namespace boost; |
19 | |
20 | struct cycle_validator |
21 | { |
22 | cycle_validator(size_t& c) : cycles(c) {} |
23 | |
24 | template < typename Path, typename Graph > |
25 | void cycle(const Path& p, const Graph& g) |
26 | { |
27 | ++cycles; |
28 | // Check to make sure that each of the vertices in the path |
29 | // is truly connected and that the back is connected to the |
30 | // front - it's not validating that we find all paths, just |
31 | // that the paths are valid. |
32 | typename Path::const_iterator i, j, last = prior(p.end()); |
33 | for (i = p.begin(); i != last; ++i) |
34 | { |
35 | j = boost::next(i); |
36 | BOOST_ASSERT(edge(*i, *j, g).second); |
37 | } |
38 | BOOST_ASSERT(edge(p.back(), p.front(), g).second); |
39 | } |
40 | |
41 | size_t& cycles; |
42 | }; |
43 | |
44 | template < typename Graph > void test() |
45 | { |
46 | typedef erdos_renyi_iterator< boost::minstd_rand, Graph > er; |
47 | |
48 | // Generate random graphs with 15 vertices and 15% probability |
49 | // of edge connection. |
50 | static const size_t N = 20; |
51 | static const double P = 0.1; |
52 | boost::minstd_rand rng; |
53 | |
54 | Graph g(er(rng, N, P), er(), N); |
55 | renumber_indices(g); |
56 | print_edges(g, get(vertex_index, g)); |
57 | |
58 | size_t cycles = 0; |
59 | cycle_validator vis(cycles); |
60 | tiernan_all_cycles(g, vis); |
61 | cout << "# cycles: " << vis.cycles << "\n" ; |
62 | } |
63 | |
64 | int main(int, char*[]) |
65 | { |
66 | typedef undirected_graph<> Graph; |
67 | typedef directed_graph<> DiGraph; |
68 | |
69 | std::cout << "*** undirected ***\n" ; |
70 | test< Graph >(); |
71 | |
72 | std::cout << "*** directed ***\n" ; |
73 | test< DiGraph >(); |
74 | } |
75 | |