123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778 |
- // (C) Copyright 2007-2009 Andrew Sutton
- //
- // Use, modification and distribution are subject to the
- // Boost Software License, Version 1.0 (See accompanying file
- // LICENSE_1_0.txt or http://www.boost.org/LICENSE_1_0.txt)
- #include <iostream>
- #include <iterator>
- #include <algorithm>
- #include <vector>
- #include <map>
- #include <boost/graph/graph_utility.hpp>
- #include <boost/graph/undirected_graph.hpp>
- #include <boost/graph/directed_graph.hpp>
- #include <boost/graph/bron_kerbosch_all_cliques.hpp>
- #include <boost/graph/erdos_renyi_generator.hpp>
- #include <boost/random/linear_congruential.hpp>
- using namespace std;
- using namespace boost;
- // TODO: This is probably not a very good test. We should be able to define
- // an identity test - something like find the clique of K5.
- struct clique_validator
- {
- clique_validator()
- { }
- template <typename Clique, typename Graph>
- inline void
- clique(const Clique& c, Graph& g)
- {
- // Simply assert that each vertex in the clique is connected
- // to all others in the clique.
- typename Clique::const_iterator i, j, end = c.end();
- for(i = c.begin(); i != end; ++i) {
- for(j = c.begin(); j != end; ++j) {
- if(i != j) {
- BOOST_ASSERT(edge(*i, *j, g).second);
- }
- }
- }
- }
- };
- template <typename Graph>
- void test()
- {
- typedef erdos_renyi_iterator<boost::minstd_rand, Graph> er;
- // Generate random graphs with 15 vertices and 15% probability
- // of edge connection.
- static const size_t N = 20;
- static const double P = 0.1;
- boost::minstd_rand rng;
- Graph g(er(rng, N, P), er(), N);
- renumber_indices(g);
- print_edges(g, get(vertex_index, g));
- bron_kerbosch_all_cliques(g, clique_validator());
- }
- int
- main(int, char *[])
- {
- typedef undirected_graph<> Graph;
- typedef directed_graph<> DiGraph;
- std::cout << "*** undirected ***\n";
- test<Graph>();
- std::cout << "*** directed ***\n";
- test<DiGraph>();
- }
|