Package org.jgrapht.alg.clique

Class DegeneracyBronKerboschCliqueFinder<V,E>

java.lang.Object

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.

Author:

Dimitrios Michail

See Also:

BronKerboschCliqueFinder, PivotBronKerboschCliqueFinder

Field Summary

Fields

Modifier and Type	Field	Description
protected List<Set<V>>	allMaximalCliques	The result
protected Graph<V,E>	graph	The underlying graph
protected int	maxSize	Size of biggest maximal clique found.
protected long	nanos	Timeout in nanoseconds
protected boolean	timeLimitReached	Whether the last computation terminated due to a time limit.

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
boolean	isTimeLimitReached()	Check the computation has stopped due to a time limit or due to computing all maximal cliques.
Iterator<Set<V>>	iterator()	Returns an iterator over all maximal cliques.
protected void	lazyRun()	Lazily execute the enumeration algorithm.
Iterator<Set<V>>	maximumIterator()	Create an iterator which returns only the maximum cliques of a graph.

Methods inherited from class org.jgrapht.alg.clique.PivotBronKerboschCliqueFinder

findCliques

Methods inherited from class java.lang.Object

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

Methods inherited from interface java.lang.Iterable

forEach, spliterator

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

lazyRun

protected void lazyRun()

Lazily execute the enumeration algorithm.

Overrides:

lazyRun in class PivotBronKerboschCliqueFinder<V,E>

iterator

public Iterator<Set<V>> iterator()

Description copied from interface: MaximalCliqueEnumerationAlgorithm

Returns an iterator over all maximal cliques.

Specified by:

iterator in interface Iterable<V>

Specified by:

iterator in interface MaximalCliqueEnumerationAlgorithm<V,E>

Returns:

an iterator over all maximal cliques

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