org.jgrapht.alg.clique

## Class DegeneracyBronKerboschCliqueFinder<V,E>

• Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
Iterable<Set<V>>, MaximalCliqueEnumerationAlgorithm<V,E>

public class DegeneracyBronKerboschCliqueFinder<V,E>
extends PivotBronKerboschCliqueFinder<V,E>
Bron-Kerbosch maximal clique enumeration algorithm with pivot and degeneracy ordering.

The algorithm is a variant of the Bron-Kerbosch algorithm which apart from the pivoting uses a degeneracy ordering of the vertices. The algorithm is described in

• David Eppstein, Maarten Löffler and Darren Strash. Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. Algorithms and Computation: 21st International Symposium (ISSAC), 403--414, 2010.

and has running time $O(d n 3^{d/3})$ where $n$ is the number of vertices of the graph and $d$ is the degeneracy of the graph. The algorithm looks for a maximal clique parameterized by degeneracy, a frequently-used measure of the sparseness of a graph that is closely related to other common sparsity measures such as arboricity and thickness, and that has previously been used for other fixed-parameter problems.

The algorithm first computes all maximal cliques and then returns the result to the user. A timeout can be set using the constructor parameters.

Author:
Dimitrios Michail
BronKerboschCliqueFinder, PivotBronKerboschCliqueFinder
• ### Field Detail

• #### graph

protected final Graph<V,E> graph
The underlying graph
• #### nanos

protected final long nanos
Timeout in nanoseconds
• #### timeLimitReached

protected boolean timeLimitReached
Whether the last computation terminated due to a time limit.
• #### allMaximalCliques

protected List<Set<V>> allMaximalCliques
The result
• #### maxSize

protected int maxSize
Size of biggest maximal clique found.
• ### Constructor Detail

• #### DegeneracyBronKerboschCliqueFinder

public DegeneracyBronKerboschCliqueFinder(Graph<V,E> graph)
Constructs a new clique finder.
Parameters:
graph - the input graph; must be simple
• #### DegeneracyBronKerboschCliqueFinder

public DegeneracyBronKerboschCliqueFinder(Graph<V,E> graph,
long timeout,
TimeUnit unit)
Constructs a new clique finder.
Parameters:
graph - the input graph; must be simple
timeout - the maximum time to wait, if zero no timeout
unit - the time unit of the timeout argument
• ### Method Detail

• #### maximumIterator

public Iterator<Set<V>> maximumIterator()
Create an iterator which returns only the maximum cliques of a graph. The iterator computes all maximal cliques and then filters them by the size of the maximum found clique.
Returns:
an iterator which returns only the maximum cliques of a graph
• #### isTimeLimitReached

public boolean isTimeLimitReached()
Check the computation has stopped due to a time limit or due to computing all maximal cliques.
Returns:
true if the computation has stopped due to a time limit, false otherwise