Package org.graph4j.clique

Class MaximalCliqueFinder

java.lang.Object
org.graph4j.SimpleGraphAlgorithm
org.graph4j.clique.MaximalCliqueFinder
public class MaximalCliqueFinder extends SimpleGraphAlgorithm
Computes a maximal clique. This class contains both a simple heuristic for determining a single maximal clique and a method that attempts to find the maximum clique by enumerating all of them using Bron-Kerbosch algorithm. A maximal clique is a clique that cannot be extended by including one more adjacent vertex. A maximum clique is a clique of largest size in the graph. Determining a maximum clique is a NP-hard problem.
Author:
Cristian Frăsinaru
See Also:

  • Constructor Details

    • MaximalCliqueFinder

      public MaximalCliqueFinder(Graph graph)

  • Method Details

    • getMaximalClique

      public Clique getMaximalClique()
      Returns a maximal clique. The algorithm tries to create a maximal clique starting with vertices of higher degree. For each vertex, it invokes the method getMaximalClique(int) in order to construct a maximal clique including that vertex. At the end, it returns the largest clique found.
      Returns:
      a maximal clique.

    • getMaximalClique

      public Clique getMaximalClique(int startVertex)
      Creates a maximal clique starting with the given vertex. The additional vertices of the clique are added in descending order of their degree in the graph.
      Parameters:
      startVertex - the first vertex added to the maximal clique.
      Returns:
      a maximal clique.

    • findMaximumClique

      public Clique findMaximumClique(long timeLimit)
      This method iterates over all maximal cliques of the graph, in order to find the maximum one.If it cannot finish in the alloted time, it returns null.
      Parameters:
      timeLimit - a time limit in milliseconds (0 for no time limit).
      Returns:
      the maximum clique of the graph or null if it cannot be found in the alloted time.