Module org.jgrapht.core
Package org.jgrapht.alg.clique
Class DegeneracyBronKerboschCliqueFinder<V,E>
java.lang.Object
org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder<V,E>
org.jgrapht.alg.clique.PivotBronKerboschCliqueFinder<V,E>
org.jgrapht.alg.clique.DegeneracyBronKerboschCliqueFinder<V,E>
- Type Parameters:
V
- the graph vertex typeE
- the graph edge type
- All Implemented Interfaces:
Iterable<Set<V>>
,MaximalCliqueEnumerationAlgorithm<V,
E>
Bron-Kerbosch maximal clique enumeration algorithm with pivot and degeneracy ordering.
The algorithm is a variant of the Bron-Kerbosch algorithm which apart from the pivoting uses a degeneracy ordering of the vertices. The algorithm is described in
- David Eppstein, Maarten Löffler and Darren Strash. Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. Algorithms and Computation: 21st International Symposium (ISSAC), 403--414, 2010.
and has running time $O(d n 3^{d/3})$ where $n$ is the number of vertices of the graph and $d$ is the degeneracy of the graph. The algorithm looks for a maximal clique parameterized by degeneracy, a frequently-used measure of the sparseness of a graph that is closely related to other common sparsity measures such as arboricity and thickness, and that has previously been used for other fixed-parameter problems.
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
ConstructorsConstructorDescriptionDegeneracyBronKerboschCliqueFinder
(Graph<V, E> graph) Constructs a new clique finder.DegeneracyBronKerboschCliqueFinder
(Graph<V, E> graph, long timeout, TimeUnit unit) Constructs a new clique finder. -
Method Summary
Modifier and TypeMethodDescriptionprotected void
lazyRun()
Lazily execute the enumeration algorithm.Methods inherited from class org.jgrapht.alg.clique.PivotBronKerboschCliqueFinder
findCliques
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
-
DegeneracyBronKerboschCliqueFinder
Constructs a new clique finder.- Parameters:
graph
- the input graph; must be simple
-
DegeneracyBronKerboschCliqueFinder
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.- Overrides:
lazyRun
in classPivotBronKerboschCliqueFinder<V,
E>
-