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:

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

Direct Known Subclasses:

BronKerboschCliqueFinder, PivotBronKerboschCliqueFinder

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

Base implementation of the Bron-Kerbosch algorithm.

Field Summary

Fields

Modifier and Type	Field	Description
protected List<Set<V>>	allMaximalCliques	The result
protected final Graph<V,E>	graph	The underlying graph
protected int	maxSize	Size of biggest maximal clique found.
protected final 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, 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.
Iterator<Set<V>>	iterator()	Returns an iterator over all maximal cliques.
protected abstract void	lazyRun()	Lazily start the computation.
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 Details

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 Details

BaseBronKerboschCliqueFinder

public BaseBronKerboschCliqueFinder(Graph<V,E> graph,
 long timeout,
 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 Details

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

lazyRun

protected abstract void lazyRun()

Lazily start the computation.