Package org.jgrapht.alg.clique

Class 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 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 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 List<Set<V>> allMaximalCliques
        The result

      • maxSize

        protected int maxSize
        Size of biggest maximal clique found.

    • Constructor Detail

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

      • lazyRun

        protected void lazyRun()
        Lazily execute the enumeration algorithm.

      • 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

      • 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