Module org.jgrapht.core

Package org.jgrapht.alg.clique

Class PivotBronKerboschCliqueFinder<V,E>

java.lang.Object

org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder<V,E>

org.jgrapht.alg.clique.PivotBronKerboschCliqueFinder<V,E>

Type Parameters:

V - the graph vertex type

E - 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 BaseBronKerboschCliqueFinder<V,E>

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:

BronKerboschCliqueFinder, DegeneracyBronKerboschCliqueFinder

Field Summary

Fields inherited from class org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder

allMaximalCliques, graph, maxSize, nanos, timeLimitReached

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
private V	choosePivot(java.util.Set<V> p, java.util.Set<V> x)	Choose a pivot.
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.
protected void	lazyRun()	Lazily execute the enumeration algorithm.

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 Detail

PivotBronKerboschCliqueFinder

public PivotBronKerboschCliqueFinder(Graph<V,E> graph)

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 simple

timeout - the maximum time to wait, if zero no timeout

unit - the time unit of the timeout argument

Method Detail

lazyRun

protected void lazyRun()

Lazily execute the enumeration algorithm.

Specified by:

lazyRun in class BaseBronKerboschCliqueFinder<V,E>

choosePivot

private V choosePivot(java.util.Set<V> p,
                      java.util.Set<V> x)

Choose a pivot.

Parameters:

p - vertices to consider adding to the clique

x - vertices which must be excluded from the clique

Returns:

a pivot

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 clique

r - a possibly non-maximal clique

x - vertices which must be excluded from the clique

nanosTimeLimit - time limit