Class DegeneracyBronKerboschCliqueFinder<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 DegeneracyBronKerboschCliqueFinder<V,​E>
    extends PivotBronKerboschCliqueFinder<V,​E>
    Bron-Kerbosch maximal clique enumeration algorithm with pivot and degeneracy ordering.

    The algorithm is a variant of the Bron-Kerbosch algorithm which apart from the pivoting uses a degeneracy ordering of the vertices. The algorithm is described in

    • David Eppstein, Maarten Löffler and Darren Strash. Listing All Maximal Cliques in Sparse Graphs in Near-Optimal Time. Algorithms and Computation: 21st International Symposium (ISSAC), 403--414, 2010.

    and has running time $O(d n 3^{d/3})$ where $n$ is the number of vertices of the graph and $d$ is the degeneracy of the graph. The algorithm looks for a maximal clique parameterized by degeneracy, a frequently-used measure of the sparseness of a graph that is closely related to other common sparsity measures such as arboricity and thickness, and that has previously been used for other fixed-parameter problems.

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

      • DegeneracyBronKerboschCliqueFinder

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

        public DegeneracyBronKerboschCliqueFinder​(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

      • 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