Package org.jgrapht.alg.clique

Class BronKerboschCliqueFinder<V,E>

java.lang.Object

org.jgrapht.alg.clique.BronKerboschCliqueFinder<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 BronKerboschCliqueFinder<V,E>
extends Object

Bron-Kerbosch maximal clique enumeration algorithm.

Implementation of the Bron-Kerbosch clique enumeration algorithm as described in:

• R. Samudrala and J. Moult. A graph-theoretic algorithm for comparative modeling of protein structure. Journal of Molecular Biology, 279(1):287--302, 1998.

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:

Ewgenij Proschak

See Also:

PivotBronKerboschCliqueFinder, DegeneracyBronKerboschCliqueFinder

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
BronKerboschCliqueFinder(Graph<V,E> graph)	Constructs a new clique finder.
BronKerboschCliqueFinder(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 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

BronKerboschCliqueFinder

public BronKerboschCliqueFinder(Graph<V,E> graph)

Constructs a new clique finder.

Parameters:

graph - the input graph; must be simple

BronKerboschCliqueFinder

public BronKerboschCliqueFinder(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.

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