]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | ||
f67539c2 TL |
23 | namespace cycle_test_detail |
24 | { | |
25 | using namespace boost; | |
7c673cae | 26 | |
f67539c2 TL |
27 | struct cycle_validator |
28 | { | |
29 | explicit cycle_validator(std::size_t& number_of_cycles) | |
30 | : cycles(number_of_cycles) | |
31 | { | |
32 | } | |
7c673cae | 33 | |
f67539c2 TL |
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); | |
7c673cae | 47 | } |
f67539c2 TL |
48 | BOOST_ASSERT(edge(p.back(), p.front(), g).second); |
49 | } | |
7c673cae | 50 | |
f67539c2 TL |
51 | std::size_t& cycles; |
52 | }; | |
7c673cae | 53 | |
f67539c2 TL |
54 | template < typename Graph, typename Algorithm > |
55 | void test_one(Algorithm algorithm) | |
56 | { | |
57 | typedef erdos_renyi_iterator< minstd_rand, Graph > er; | |
7c673cae | 58 | |
f67539c2 TL |
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; | |
7c673cae | 64 | |
f67539c2 TL |
65 | Graph g(er(rng, N, P), er(), N); |
66 | renumber_indices(g); | |
67 | print_edges(g, get(vertex_index, g)); | |
7c673cae | 68 | |
f67539c2 TL |
69 | std::size_t cycles = 0; |
70 | cycle_validator vis(cycles); | |
71 | algorithm(g, vis); | |
72 | std::cout << "# cycles: " << vis.cycles << "\n"; | |
73 | } | |
7c673cae FG |
74 | } // end namespace cycle_test_detail |
75 | ||
f67539c2 TL |
76 | template < typename Algorithm > void cycle_test(Algorithm const& algorithm) |
77 | { | |
7c673cae | 78 | std::cout << "*** undirected ***\n"; |
f67539c2 | 79 | cycle_test_detail::test_one< boost::undirected_graph<> >(algorithm); |
7c673cae FG |
80 | |
81 | std::cout << "*** directed ***\n"; | |
f67539c2 | 82 | cycle_test_detail::test_one< boost::directed_graph<> >(algorithm); |
7c673cae FG |
83 | } |
84 | ||
85 | #endif // !BOOST_GRAPH_TEST_CYCLE_TEST_HPP |