Package org.jgrapht.alg.clique
Class DegeneracyBronKerboschCliqueFinder<V,E>
- java.lang.Object
-
- 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:
java.lang.Iterable<java.util.Set<V>>
,MaximalCliqueEnumerationAlgorithm<V,E>
public class DegeneracyBronKerboschCliqueFinder<V,E> extends PivotBronKerboschCliqueFinder<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.
- Author:
- Dimitrios Michail
- See Also:
BronKerboschCliqueFinder
,PivotBronKerboschCliqueFinder
-
-
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 DegeneracyBronKerboschCliqueFinder(Graph<V,E> graph)
Constructs a new clique finder.DegeneracyBronKerboschCliqueFinder(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 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.-
Methods inherited from class org.jgrapht.alg.clique.PivotBronKerboschCliqueFinder
findCliques
-
-
-
-
Field Detail
-
graph
protected final Graph<V,E> graph
The underlying graph
-
nanos
protected final long nanos
Timeout in nanoseconds
-
timeLimitReached
protected boolean timeLimitReached
Whether the last computation terminated due to a time limit.
-
allMaximalCliques
protected java.util.List<java.util.Set<V>> allMaximalCliques
The result
-
maxSize
protected int maxSize
Size of biggest maximal clique found.
-
-
Constructor Detail
-
DegeneracyBronKerboschCliqueFinder
public DegeneracyBronKerboschCliqueFinder(Graph<V,E> graph)
Constructs a new clique finder.- Parameters:
graph
- the input graph; must be simple
-
DegeneracyBronKerboschCliqueFinder
public DegeneracyBronKerboschCliqueFinder(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.- Overrides:
lazyRun
in classPivotBronKerboschCliqueFinder<V,E>
-
iterator
public java.util.Iterator<java.util.Set<V>> 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
public java.util.Iterator<java.util.Set<V>> 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
-
-