Package com.jgalgo

Interface MaximalCliques

  • public interface MaximalCliques
    Finds all maximal cliques in a graph.

    A clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent (connected by an edge). A maximal clique is a clique that cannot be extended by including one more adjacent vertex. 

     
 Graph g = ...;
 MaximalCliques maxCliquesAlgo = MaximalCliques.newBuilder().build();

 for (IntCollection clique : maxCliquesAlgo.findAllMaximalCliques(g)) {
 	System.out.println("Clique in the graph:");
 	for (int v : clique)
 		System.out.println("\t" + v);
 }
    Author:
    Barak Ugav

    • Method Detail

      • findAllMaximalCliques

        default Collection<IntCollection> findAllMaximalCliques​(Graph g)
        Finds all the maximal cliques in a graph.

        The number of maximal cliques can be exponential in the number of vertices in the graph. If the graph is large, consider using the iterateMaximalCliques(Graph) method instead, which may iterate the cliques one at a time without storing all them at the same time in memory.

        Parameters:
        g - a graph
        Returns:
        a collection containing all maximal cliques in the graph

      • iterateMaximalCliques

        Iterator<IntCollection> iterateMaximalCliques​(Graph g)
        Iterate over all maximal cliques in a graph.

        In contrast to findAllMaximalCliques(Graph), this method may iterate the cliques one at a time and can be used to avoid storing all the cliques in memory at the the time.

        Parameters:
        g - a graph
        Returns:
        an iterator that iterates over all maximal cliques in the graph

      • newBuilder

        static MaximalCliques.Builder newBuilder()
        Create a new builder for maximal cliques algorithms.
        Returns:
        a new builder for maximal cliques algorithms