1 | // (C) Copyright 2013 Louis Dionne |
2 | // |
3 | // Modified from `tiernan_all_cycles.cpp`. |
4 | // |
5 | // Use, modification and distribution are subject to the |
6 | // Boost Software License, Version 1.0 (See accompanying file |
7 | // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt) |
8 | |
9 | #ifndef BOOST_GRAPH_TEST_CYCLE_TEST_HPP |
10 | #define BOOST_GRAPH_TEST_CYCLE_TEST_HPP |
11 | |
12 | #include <boost/assert.hpp> |
13 | #include <boost/graph/directed_graph.hpp> |
14 | #include <boost/graph/erdos_renyi_generator.hpp> |
15 | #include <boost/graph/graph_traits.hpp> |
16 | #include <boost/graph/graph_utility.hpp> |
17 | #include <boost/graph/undirected_graph.hpp> |
18 | #include <boost/next_prior.hpp> |
19 | #include <boost/random/linear_congruential.hpp> |
20 | #include <cstddef> |
21 | #include <iostream> |
22 | |
23 | namespace cycle_test_detail |
24 | { |
25 | using namespace boost; |
26 | |
27 | struct cycle_validator |
28 | { |
29 | explicit cycle_validator(std::size_t& number_of_cycles) |
30 | : cycles(number_of_cycles) |
31 | { |
32 | } |
33 | |
34 | template < typename Path, typename Graph > |
35 | void cycle(Path const& p, Graph const& g) |
36 | { |
37 | ++cycles; |
38 | // Check to make sure that each of the vertices in the path |
39 | // is truly connected and that the back is connected to the |
40 | // front - it's not validating that we find all paths, just |
41 | // that the paths are valid. |
42 | typename Path::const_iterator i, j, last = prior(p.end()); |
43 | for (i = p.begin(); i != last; ++i) |
44 | { |
45 | j = boost::next(i); |
46 | BOOST_ASSERT(edge(*i, *j, g).second); |
47 | } |
48 | BOOST_ASSERT(edge(p.back(), p.front(), g).second); |
49 | } |
50 | |
51 | std::size_t& cycles; |
52 | }; |
53 | |
54 | template < typename Graph, typename Algorithm > |
55 | void test_one(Algorithm algorithm) |
56 | { |
57 | typedef erdos_renyi_iterator< minstd_rand, Graph > er; |
58 | |
59 | // Generate random graphs with 15 vertices and 15% probability |
60 | // of edge connection. |
61 | static std::size_t const N = 20; |
62 | static double const P = 0.1; |
63 | minstd_rand rng; |
64 | |
65 | Graph g(er(rng, N, P), er(), N); |
66 | renumber_indices(g); |
67 | print_edges(g, get(vertex_index, g)); |
68 | |
69 | std::size_t cycles = 0; |
70 | cycle_validator vis(cycles); |
71 | algorithm(g, vis); |
72 | std::cout << "# cycles: " << vis.cycles << "\n" ; |
73 | } |
74 | } // end namespace cycle_test_detail |
75 | |
76 | template < typename Algorithm > void cycle_test(Algorithm const& algorithm) |
77 | { |
78 | std::cout << "*** undirected ***\n" ; |
79 | cycle_test_detail::test_one< boost::undirected_graph<> >(algorithm); |
80 | |
81 | std::cout << "*** directed ***\n" ; |
82 | cycle_test_detail::test_one< boost::directed_graph<> >(algorithm); |
83 | } |
84 | |
85 | #endif // !BOOST_GRAPH_TEST_CYCLE_TEST_HPP |
86 | |