Package com.jgalgo.alg

Interface MaximalCliquesEnumerator

public interface MaximalCliquesEnumerator

Algorithm for enumerating over 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.

Use newInstance() to get a default implementation of this interface. A builder obtained via newBuilder() may support different options to obtain different implementations.

 
 Graph<String, Integer> g = ...;
 MaximalCliquesEnumerator maxCliquesAlgo = MaximalCliquesEnumerator.newInstance();

 for (Set<String> clique : maxCliquesAlgo.allMaximalCliques(g)) {
 	System.out.println("Clique in the graph:");
 	for (String v : clique)
 		System.out.println("\t" + v);
 }
 

Author:

Barak Ugav

Nested Class Summary

Nested Classes

Modifier and Type	Interface	Description
static interface	MaximalCliquesEnumerator.Builder	A builder for MaximalCliquesEnumerator objects.

Method Summary

Modifier and Type	Method	Description
default <V,E> List<Set<V>>	allMaximalCliques(Graph<V,E> g)	Finds all the maximal cliques in a graph.
<V,E> Iterator<Set<V>>	maximalCliquesIter(Graph<V,E> g)	Iterate over all maximal cliques in a graph.
static MaximalCliquesEnumerator.Builder	newBuilder()	Create a new builder for maximal cliques algorithms.
static MaximalCliquesEnumerator	newInstance()	Create a new maximal cliques algorithm object.

Method Detail

maximalCliquesIter

<V,E> Iterator<Set<V>> maximalCliquesIter(Graph<V,E> g)

Iterate over all maximal cliques in a graph.

In contrast to allMaximalCliques(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.

If g is IntGraph, the returned iterator will be iterate over IntSet.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

an iterator that iterates over all maximal cliques in the graph

allMaximalCliques

default <V,E> List<Set<V>> allMaximalCliques(Graph<V,E> 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 maximalCliquesIter(Graph) method instead, which may iterate the cliques one at a time without storing all them at the same time in memory.

If g is IntGraph, the returned object will be a list of IntSet.

Type Parameters:

V - the vertices type

E - the edges type

Parameters:

g - a graph

Returns:

a list containing all maximal cliques in the graph

newInstance

static MaximalCliquesEnumerator newInstance()

Create a new maximal cliques algorithm object.

This is the recommended way to instantiate a new MaximalCliquesEnumerator object. The MaximalCliquesEnumerator.Builder might support different options to obtain different implementations.

Returns:

a default implementation of MaximalCliquesEnumerator

newBuilder

static MaximalCliquesEnumerator.Builder newBuilder()

Create a new builder for maximal cliques algorithms.

Use newInstance() for a default implementation.

Returns:

a new builder for maximal cliques algorithms