Package org.jgrapht.alg.clique

Class BronKerboschCliqueFinder<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>
    public class BronKerboschCliqueFinder<V,​E>
extends java.lang.Object
    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.

    Author:
    Ewgenij Proschak
    See Also:
    PivotBronKerboschCliqueFinder, 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.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      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 Detail

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

      • 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,
                                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 Detail

      • lazyRun

        protected void lazyRun()
        Lazily execute the enumeration algorithm.

      • 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