java.lang.Object
org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder<V,E>
org.jgrapht.alg.clique.PivotBronKerboschCliqueFinder<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
Iterable<Set<V>>
,MaximalCliqueEnumerationAlgorithm<V,
E>
- Direct Known Subclasses:
DegeneracyBronKerboschCliqueFinder
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.
- See Also:
-
Field Summary
Fields inherited from class org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder
allMaximalCliques, graph, maxSize, nanos, timeLimitReached
-
Constructor Summary
ConstructorsConstructorDescriptionPivotBronKerboschCliqueFinder
(Graph<V, E> graph) Constructs a new clique finder.PivotBronKerboschCliqueFinder
(Graph<V, E> graph, long timeout, TimeUnit unit) Constructs a new clique finder. -
Method Summary
Methods inherited from class org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder
isTimeLimitReached, iterator, maximumIterator
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
-
Constructor Details
-
PivotBronKerboschCliqueFinder
Constructs a new clique finder.- Parameters:
graph
- the input graph; must be simple
-
PivotBronKerboschCliqueFinder
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.- Specified by:
lazyRun
in classBaseBronKerboschCliqueFinder<V,
E>
-
choosePivot
Choose a pivot.- Parameters:
p
- vertices to consider adding to the cliquex
- vertices which must be excluded from the clique- Returns:
- a pivot
-
findCliques
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
-