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:
Iterable<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:
  • 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, 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.
      Specified by:
      lazyRun in class BaseBronKerboschCliqueFinder<V,E>
    • choosePivot

      private V choosePivot(Set<V> p, 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(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