java.lang.Object
org.jgrapht.alg.clique.PivotBronKerboschCliqueFinder<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>
- Direct Known Subclasses:
DegeneracyBronKerboschCliqueFinder
public class PivotBronKerboschCliqueFinder<V,E>
extends java.lang.Object
Bron-Kerbosch maximal clique enumeration algorithm with pivot.
The pivoting follows the rule from the paper
- E. Tomita, A. Tanaka, and H. Takahashi. The worst-case time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci. 363(1):28–42, 2006.
where the authors show that using that rule guarantees that the Bron-Kerbosch algorithm has worst-case running time $O(3^{n/3})$ where $n$ is the number of vertices of the graph, excluding time to write the output, which is worst-case optimal.
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
,DegeneracyBronKerboschCliqueFinder
-
Field Summary
Fields Modifier and Type Field Description protected java.util.List<java.util.Set<V>>
allMaximalCliques
The resultprotected Graph<V,E>
graph
The underlying graphprotected int
maxSize
Size of biggest maximal clique found.protected long
nanos
Timeout in nanosecondsprotected boolean
timeLimitReached
Whether the last computation terminated due to a time limit. -
Constructor Summary
Constructors Constructor Description PivotBronKerboschCliqueFinder(Graph<V,E> graph)
Constructs a new clique finder.PivotBronKerboschCliqueFinder(Graph<V,E> graph, long timeout, java.util.concurrent.TimeUnit unit)
Constructs a new clique finder. -
Method Summary
Modifier and Type Method Description protected void
findCliques(java.util.Set<V> P, java.util.Set<V> R, java.util.Set<V> X, long nanosTimeLimit)
Recursive implementation of the Bron-Kerbosch with pivot.boolean
isTimeLimitReached()
Check the computation has stopped due to a time limit or due to computing all maximal cliques.java.util.Iterator<java.util.Set<V>>
iterator()
Returns an iterator over all maximal cliques.protected void
lazyRun()
Lazily execute the enumeration algorithm.java.util.Iterator<java.util.Set<V>>
maximumIterator()
Create an iterator which returns only the maximum cliques of a graph.
-
Field Details
-
graph
The underlying graph -
nanos
protected final long nanosTimeout in nanoseconds -
timeLimitReached
protected boolean timeLimitReachedWhether the last computation terminated due to a time limit. -
allMaximalCliques
The result -
maxSize
protected int maxSizeSize of biggest maximal clique found.
-
-
Constructor Details
-
PivotBronKerboschCliqueFinder
Constructs a new clique finder.- Parameters:
graph
- the input graph; must be simple
-
PivotBronKerboschCliqueFinder
public PivotBronKerboschCliqueFinder(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 Details
-
lazyRun
protected void lazyRun()Lazily execute the enumeration algorithm. -
findCliques
protected void findCliques(java.util.Set<V> P, java.util.Set<V> R, java.util.Set<V> X, long nanosTimeLimit)Recursive implementation of the Bron-Kerbosch with pivot.- Parameters:
P
- vertices to consider adding to the cliqueR
- a possibly non-maximal cliqueX
- vertices which must be excluded from the cliquenanosTimeLimit
- time limit
-
iterator
Description copied from interface:MaximalCliqueEnumerationAlgorithm
Returns an iterator over all maximal cliques.- Specified by:
iterator
in interfacejava.lang.Iterable<V>
- Specified by:
iterator
in interfaceMaximalCliqueEnumerationAlgorithm<V,E>
- Returns:
- an iterator over all maximal cliques
-
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
-