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 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.