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:
java.lang.Iterable<java.util.Set<V>>, MaximalCliqueEnumerationAlgorithm<V,​E>
Direct Known Subclasses:
DegeneracyBronKerboschCliqueFinder
public class PivotBronKerboschCliqueFinder<V,​E>
extends java.lang.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 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
    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
    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.
    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 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 java.util.List<java.util.Set<V>> allMaximalCliques
      The result

    • maxSize

      protected int maxSize
      Size of biggest maximal clique found.

  • Constructor Details

    • 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 Details

    • lazyRun

      protected void lazyRun()
      Lazily execute the enumeration algorithm.

    • 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

    • 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