Class BronKerboschCliqueFinder<V,E>

java.lang.Object

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

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 BaseBronKerboschCliqueFinder<V,E>

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.

See Also:

• PivotBronKerboschCliqueFinder
• DegeneracyBronKerboschCliqueFinder

Field Summary

Fields inherited from class BaseBronKerboschCliqueFinder

allMaximalCliques, graph, maxSize, nanos, timeLimitReached

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
private void	findCliques(List<V> potentialClique, List<V> candidates, List<V> alreadyFound, long nanosTimeLimit)
protected void	lazyRun()	Lazily execute the enumeration algorithm.

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

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 Details

lazyRun

protected void lazyRun()

Lazily execute the enumeration algorithm.

Specified by:

lazyRun in class BaseBronKerboschCliqueFinder<V,E>

findCliques

private void findCliques(List<V> potentialClique,
 List<V> candidates,
 List<V> alreadyFound,
 long nanosTimeLimit)