org.jgrapht.alg
Class BronKerboschCliqueFinder<V,E>

java.lang.Object
  extended by org.jgrapht.alg.BronKerboschCliqueFinder<V,E>

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]

Author:
Ewgenij Proschak

Constructor Summary
BronKerboschCliqueFinder(Graph<V,E> graph)
          Creates a new clique finder.
 
Method Summary
 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
 

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)