Class DegeneracyBronKerboschCliqueFinder<V,E>

java.lang.Object

org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder<V,E>

org.jgrapht.alg.clique.PivotBronKerboschCliqueFinder<V,E>

org.jgrapht.alg.clique.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.

See Also:

• BronKerboschCliqueFinder
• PivotBronKerboschCliqueFinder

Field Summary

Fields inherited from class BaseBronKerboschCliqueFinder

allMaximalCliques, graph, maxSize, nanos, timeLimitReached

Constructor Summary

Constructors

Constructor	Description
DegeneracyBronKerboschCliqueFinder(Graph<V,E> graph)	Constructs a new clique finder.
DegeneracyBronKerboschCliqueFinder(Graph<V,E> graph, long timeout, TimeUnit unit)	Constructs a new clique finder.

Method Summary

Modifier and Type	Method	Description
protected void	lazyRun()	Lazily execute the enumeration algorithm.

Methods inherited from class PivotBronKerboschCliqueFinder

findCliques

Methods inherited from class BaseBronKerboschCliqueFinder

isTimeLimitReached, iterator, maximumIterator

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface Iterable

forEach, spliterator

Constructor Details

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 Details

lazyRun

protected void lazyRun()

Lazily execute the enumeration algorithm.

Overrides:

lazyRun in class PivotBronKerboschCliqueFinder<V,E>