Module org.jgrapht.core

Package org.jgrapht.alg.clique

Class PivotBronKerboschCliqueFinder<V,E>

java.lang.Object

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

Type Parameters:

V - the graph vertex type

E - the graph edge type

All Implemented Interfaces:

Iterable<Set<V>>, MaximalCliqueEnumerationAlgorithm<V,E>

Direct Known Subclasses:

DegeneracyBronKerboschCliqueFinder

public class PivotBronKerboschCliqueFinder<V,E>
extends Object

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.

Author:

Dimitrios Michail

See Also:

BronKerboschCliqueFinder, DegeneracyBronKerboschCliqueFinder

Field Summary

Fields

Modifier and Type	Field	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 Summary

Constructors

Constructor	Description
PivotBronKerboschCliqueFinder(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

Modifier and Type	Method	Description
protected void	findCliques(Set<V> p, Set<V> r, Set<V> x, long nanosTimeLimit)	Recursive implementation of the Bron-Kerbosch with pivot.
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.

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

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 List<Set<V>> allMaximalCliques

The result

maxSize

protected int maxSize

Size of biggest maximal clique found.

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,
                                     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.

findCliques

protected void findCliques(Set<V> p,
                           Set<V> r,
                           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

iterator

public Iterator<Set<V>> iterator()

Description copied from interface: MaximalCliqueEnumerationAlgorithm

Returns an iterator over all maximal cliques.

Specified by:

iterator in interface Iterable<V>

Specified by:

iterator in interface MaximalCliqueEnumerationAlgorithm<V,E>

Returns:

an iterator over all maximal cliques

maximumIterator

public Iterator<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