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 | #include <iterator> |
9 | #include <algorithm> |
10 | #include <vector> |
11 | #include <map> |
12 | |
13 | #include <boost/graph/graph_utility.hpp> |
14 | #include <boost/graph/undirected_graph.hpp> |
15 | #include <boost/graph/directed_graph.hpp> |
16 | #include <boost/graph/bron_kerbosch_all_cliques.hpp> |
17 | #include <boost/graph/erdos_renyi_generator.hpp> |
18 | |
19 | #include <boost/random/linear_congruential.hpp> |
20 | |
21 | using namespace std; |
22 | using namespace boost; |
23 | |
24 | // TODO: This is probably not a very good test. We should be able to define |
25 | // an identity test - something like find the clique of K5. |
26 | |
27 | struct clique_validator |
28 | { |
29 | clique_validator() {} |
30 | |
31 | template < typename Clique, typename Graph > |
32 | inline void clique(const Clique& c, Graph& g) |
33 | { |
34 | // Simply assert that each vertex in the clique is connected |
35 | // to all others in the clique. |
36 | typename Clique::const_iterator i, j, end = c.end(); |
37 | for (i = c.begin(); i != end; ++i) |
38 | { |
39 | for (j = c.begin(); j != end; ++j) |
40 | { |
41 | if (i != j) |
42 | { |
43 | BOOST_ASSERT(edge(*i, *j, g).second); |
44 | } |
45 | } |
46 | } |
47 | } |
48 | }; |
49 | |
50 | template < typename Graph > void test() |
51 | { |
52 | typedef erdos_renyi_iterator< boost::minstd_rand, Graph > er; |
53 | |
54 | // Generate random graphs with 15 vertices and 15% probability |
55 | // of edge connection. |
56 | static const size_t N = 20; |
57 | static const double P = 0.1; |
58 | |
59 | boost::minstd_rand rng; |
60 | Graph g(er(rng, N, P), er(), N); |
61 | renumber_indices(g); |
62 | print_edges(g, get(vertex_index, g)); |
63 | |
64 | bron_kerbosch_all_cliques(g, clique_validator()); |
65 | } |
66 | |
67 | int main(int, char*[]) |
68 | { |
69 | typedef undirected_graph<> Graph; |
70 | typedef directed_graph<> DiGraph; |
71 | |
72 | std::cout << "*** undirected ***\n" ; |
73 | test< Graph >(); |
74 | |
75 | std::cout << "*** directed ***\n" ; |
76 | test< DiGraph >(); |
77 | } |
78 | |