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

      • findCliques

        private void findCliques​(java.util.List<V> potentialClique,
                                 java.util.List<V> candidates,
                                 java.util.List<V> alreadyFound,
                                 long nanosTimeLimit)