Re: [Boost-users] Counting all cliques of a given size in an undirected graph

Subject: Re: [Boost-users] Counting all cliques of a given size in an undirected graph
From: Jeremiah Willcock (jewillco_at_[hidden])
Date: 2013-07-01 13:05:16

On Mon, 1 Jul 2013, Andrea Cassioli wrote:

> Dear all Boost users,
> I need to count all cliques of a given size in an undirected graph. I
> am using Boost Graph and I have found the Bron-Kerbosch algorithm
> implemented in version 1.53 but not documented. My question is
> two-fold:

> 1) why the algorithm is somehow hidden?

There does not appear to be a documentation page for it, so it's likely 
one hasn't been written.  It is not hidden on purpose otherwise.

> 2) Is this algorithm able to count the occurrencies of cliques of a
> certain dimension or just the maximal cliques?

It looks like it only finds maximal cliques that are over the size that 
you specify.  You could get all cliques over a certain size n by 
enumerating all maximal cliques of size >=n, then choosing all size-n 
subsets of vertices of the maximal clique.

-- Jeremiah Willcock