graph/test/bron_kerbosch_all_cliques.cpp

// (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 graph with N vertices and probability P
    // 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 >();
}