- java.lang.Object
-
- org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder<V,E>
-
- org.jgrapht.alg.clique.BronKerboschCliqueFinder<V,E>
-
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
java.lang.Iterable<java.util.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.
-
-
Field Summary
-
Fields inherited from class org.jgrapht.alg.clique.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, java.util.concurrent.TimeUnit unit)
Constructs a new clique finder.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description private void
findCliques(java.util.List<V> potentialClique, java.util.List<V> candidates, java.util.List<V> alreadyFound, long nanosTimeLimit)
protected void
lazyRun()
Lazily execute the enumeration algorithm.-
Methods inherited from class org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder
isTimeLimitReached, iterator, maximumIterator
-
-
-
-
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, java.util.concurrent.TimeUnit unit)
Constructs a new clique finder.- Parameters:
graph
- the input graph; must be simpletimeout
- the maximum time to wait, if zero no timeoutunit
- the time unit of the timeout argument
-
-
Method Detail
-
lazyRun
protected void lazyRun()
Lazily execute the enumeration algorithm.- Specified by:
lazyRun
in classBaseBronKerboschCliqueFinder<V,E>
-
-