Class BronKerboschCliqueFinder<V,E>

java.lang.Object
org.jgrapht.alg.clique.BaseBronKerboschCliqueFinder<V,E>
org.jgrapht.alg.clique.BronKerboschCliqueFinder<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
All Implemented Interfaces:
Iterable<Set<V>>, MaximalCliqueEnumerationAlgorithm<V,E>

public class BronKerboschCliqueFinder<V,E> extends BaseBronKerboschCliqueFinder<V,E>
Bron-Kerbosch maximal clique enumeration algorithm.

Implementation of the Bron-Kerbosch clique enumeration algorithm as described in:

  • R. Samudrala and J. Moult. A graph-theoretic algorithm for comparative modeling of protein structure. Journal of Molecular Biology, 279(1):287--302, 1998.

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

    • BronKerboschCliqueFinder

      public BronKerboschCliqueFinder(Graph<V,E> graph)
      Constructs a new clique finder.
      Parameters:
      graph - the input graph; must be simple
    • BronKerboschCliqueFinder

      public BronKerboschCliqueFinder(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>
    • findCliques

      private void findCliques(List<V> potentialClique, List<V> candidates, List<V> alreadyFound, long nanosTimeLimit)