V - the graph vertex typeE - the graph edge typepublic class DegeneracyBronKerboschCliqueFinder<V,E> extends PivotBronKerboschCliqueFinder<V,E>
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
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.
BronKerboschCliqueFinder,
PivotBronKerboschCliqueFinder| Modifier and Type | Field and Description |
|---|---|
protected List<Set<V>> |
allMaximalCliques
The result
|
protected Graph<V,E> |
graph
The underlying graph
|
protected int |
maxSize
Size of biggest maximal clique found.
|
protected long |
nanos
Timeout in nanoseconds
|
protected boolean |
timeLimitReached
Whether the last computation terminated due to a time limit.
|
| Constructor and Description |
|---|
DegeneracyBronKerboschCliqueFinder(Graph<V,E> graph)
Constructs a new clique finder.
|
DegeneracyBronKerboschCliqueFinder(Graph<V,E> graph,
long timeout,
TimeUnit unit)
Constructs a new clique finder.
|
| Modifier and Type | Method and Description |
|---|---|
boolean |
isTimeLimitReached()
Check the computation has stopped due to a time limit or due to computing all maximal
cliques.
|
Iterator<Set<V>> |
iterator()
Returns an iterator over all maximal cliques.
|
protected void |
lazyRun()
Lazily execute the enumeration algorithm.
|
Iterator<Set<V>> |
maximumIterator()
Create an iterator which returns only the maximum cliques of a graph.
|
findCliquesclone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, waitforEach, spliteratorprotected final Graph<V,E> graph
protected final long nanos
protected boolean timeLimitReached
protected int maxSize
public DegeneracyBronKerboschCliqueFinder(Graph<V,E> graph)
graph - the input graph; must be simplepublic DegeneracyBronKerboschCliqueFinder(Graph<V,E> graph, long timeout, TimeUnit unit)
graph - the input graph; must be simpletimeout - the maximum time to wait, if zero no timeoutunit - the time unit of the timeout argumentprotected void lazyRun()
lazyRun in class PivotBronKerboschCliqueFinder<V,E>public Iterator<Set<V>> iterator()
MaximalCliqueEnumerationAlgorithmiterator in interface Iterable<Set<V>>iterator in interface MaximalCliqueEnumerationAlgorithm<V,E>public Iterator<Set<V>> maximumIterator()
public boolean isTimeLimitReached()
Copyright © 2019. All rights reserved.