Cliques¶
Algorithms¶
The following algorithms are available:

jgrapht.algorithms.cliques.
bron_kerbosch
(graph, timeout=0)[source]¶ BronKerbosch maximal clique enumeration algorithm.
Implementation of the BronKerbosch clique enumeration algorithm as described in:
R. Samudrala and J. Moult. A graphtheoretic algorithm for comparative modeling of protein structure. Journal of Molecular Biology, 279(1):287–302, 1998.
The algorithm first computes all maximal cliques and then returns the result to the user. A timeout (in seconds) can be set using the parameters.
 Parameters
graph – The input graph which should be simple
timeout – Timeout in seconds. No timeout if zero
 Returns
An iterator over maximal cliques

jgrapht.algorithms.cliques.
bron_kerbosch_with_degeneracy_ordering
(graph, timeout=0)[source]¶ BronKerbosch maximal clique enumeration algorithm with pivot and degeneracy ordering.
The algorithm is a variant of the BronKerbosch algorithm which apart from the pivoting uses a degeneracy ordering of the vertices. The algorithm is described in
David Eppstein, Maarten Löffler and Darren Strash. Listing All Maximal Cliques in Sparse Graphs in NearOptimal Time. Algorithms and Computation: 21st International Symposium (ISSAC), 403–414, 2010.
and has running time \(\mathcal{O}(d n 3^{d/3})\) where \(n\) is the number of vertices of the graph and \(d\) is the degeneracy of the graph. The algorithm looks for a maximal clique parameterized by degeneracy, a frequentlyused measure of the sparseness of a graph that is closely related to other common sparsity measures such as arboricity and thickness, and that has previously been used for other fixedparameter problems.
The algorithm first computes all maximal cliques and then returns the result to the user. A timeout (in seconds) can be set using the parameters.
 Parameters
graph – The input graph which should be simple
timeout – Timeout in seconds. No timeout if zero
 Returns
An iterator over maximal cliques

jgrapht.algorithms.cliques.
bron_kerbosch_with_pivot
(graph, timeout=0)[source]¶ BronKerbosch maximal clique enumeration algorithm with pivot.
The pivoting follows the rule from the paper:
E. Tomita, A. Tanaka, and H. Takahashi. The worstcase time complexity for generating all maximal cliques and computational experiments. Theor. Comput. Sci. 363(1):28–42, 2006.
where the authors show that using that rule guarantees that the BronKerbosch algorithm has worstcase running time \(\mathcal{O}(3^{n/3})\) where \(n\) is the number of vertices of the graph, excluding time to write the output, which is worstcase optimal.
The algorithm first computes all maximal cliques and then returns the result to the user. A timeout (in seconds) can be set using the parameters.
 Parameters
graph – The input graph which should be simple
timeout – Timeout in seconds. No timeout if zero
 Returns
An iterator over maximal cliques

jgrapht.algorithms.cliques.
chordal_max_clique
(graph)[source]¶ Find a maximum clique in a chordal graph.
The algorithms first computes a perfect elimination ordering and then a maximum clique. Running time \(\mathcal{O}(n+m)\).
 Parameters
graph – the chordal graph. If the graph is not chordal an error is raised
 Returns
a clique as a vertex set