Class BronKerboschCliqueFinder<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    public class BronKerboschCliqueFinder<V,​E>
    extends java.lang.Object
    This class implements Bron-Kerbosch clique detection algorithm as it is described in [Samudrala R.,Moult J.:A Graph-theoretic Algorithm for comparative Modeling of Protein Structure; J.Mol. Biol. (1998); vol 279; pp. 287-302]
    • Field Summary

      Fields 
      Modifier and Type Field Description
      private java.util.Collection<java.util.Set<V>> cliques  
      private Graph<V,​E> graph  
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private boolean end​(java.util.List<V> candidates, java.util.List<V> already_found)  
      private void findCliques​(java.util.List<V> potential_clique, java.util.List<V> candidates, java.util.List<V> already_found)  
      java.util.Collection<java.util.Set<V>> getAllMaximalCliques()
      Finds all maximal cliques of the graph.
      java.util.Collection<java.util.Set<V>> getBiggestMaximalCliques()
      Finds the biggest maximal cliques of the graph.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • graph

        private final Graph<V,​E> graph
      • cliques

        private java.util.Collection<java.util.Set<V>> cliques
    • Constructor Detail

      • BronKerboschCliqueFinder

        public BronKerboschCliqueFinder​(Graph<V,​E> graph)
        Creates a new clique finder.
        Parameters:
        graph - the graph in which cliques are to be found; graph must be simple
    • Method Detail

      • getAllMaximalCliques

        public java.util.Collection<java.util.Set<V>> getAllMaximalCliques()
        Finds all maximal cliques of the graph. A clique is maximal if it is impossible to enlarge it by adding another vertex from the graph. Note that a maximal clique is not necessarily the biggest clique in the graph.
        Returns:
        Collection of cliques (each of which is represented as a Set of vertices)
      • getBiggestMaximalCliques

        public java.util.Collection<java.util.Set<V>> getBiggestMaximalCliques()
        Finds the biggest maximal cliques of the graph.
        Returns:
        Collection of cliques (each of which is represented as a Set of vertices)
      • findCliques

        private void findCliques​(java.util.List<V> potential_clique,
                                 java.util.List<V> candidates,
                                 java.util.List<V> already_found)
      • end

        private boolean end​(java.util.List<V> candidates,
                            java.util.List<V> already_found)