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 {
clique_validatorclique_validator29 clique_validator() {}
30
31 template < typename Clique, typename Graph >
cliqueclique_validator32 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
test()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
main(int,char * [])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