Module org.jgrapht.core

Package org.jgrapht.alg.clique

Class BaseBronKerboschCliqueFinder<V,E>

java.lang.Object

org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder<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:

BronKerboschCliqueFinder, PivotBronKerboschCliqueFinder

abstract class BaseBronKerboschCliqueFinder<V,E>
extends java.lang.Object
implements MaximalCliqueEnumerationAlgorithm<V,E>

Base implementation of the Bron-Kerbosch algorithm.

Field Summary

Fields

Modifier and Type	Field	Description
protected java.util.List<java.util.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
BaseBronKerboschCliqueFinder(Graph<V,E> graph, long timeout, java.util.concurrent.TimeUnit unit)	Constructor

Method Summary

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 abstract void	lazyRun()	Lazily start the computation.
java.util.Iterator<java.util.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 java.util.List<java.util.Set<V>> allMaximalCliques

The result

maxSize

protected int maxSize

Size of biggest maximal clique found.

Constructor Detail

BaseBronKerboschCliqueFinder

public BaseBronKerboschCliqueFinder(Graph<V,E> graph,
                                    long timeout,
                                    java.util.concurrent.TimeUnit unit)

Constructor

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

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 interface java.lang.Iterable<V>

Specified by:

iterator in interface MaximalCliqueEnumerationAlgorithm<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

lazyRun

protected abstract void lazyRun()

Lazily start the computation.