max_cliques

Contents

max_cliques#

graph_tool.topology.max_cliques(g)[source]#

Return an iterator over the maximal cliques of the graph.

Parameters:
gGraph

Graph to be used.

Returns:
max_cliquesiterator over numpy.ndarray instances

Iterator over lists of vertices corresponding to the maximal cliques.

Notes

This implements the Bron-Kerbosh algorithm [bron_algorithm_1973] [bron-kerbosh-wiki] with pivoting [tomita_worst-case_2006] [cazals_note_2008].

The worst case complexity of this algorithm is \(O(3^{V/3})\) for a graph of \(V\) vertices, but for sparse graphs it is typically much faster.

References

[bron_algorithm_1973]

Coen Bron and Joep Kerbosch, “Algorithm 457: finding all cliques of an undirected graph”, Commun. ACM 16, 9, 575-577 (1973), DOI: 10.1145/362342.362367 [sci-hub, @tor]

[tomita_worst-case_2006]

Etsuji Tomita, Akira Tanaka, and Haruhisa Takahashi. “The worst-case time complexity for generating all maximal cliques and computational experiments.” Theoretical Computer Science 363.1 28-42 (2006), DOI: 10.1016/j.tcs.2006.06.015 [sci-hub, @tor]

[cazals_note_2008]

Frédéric Cazals, and Chinmay Karande, “A note on the problem of reporting maximal cliques.” Theoretical Computer Science 407.1-3 564-568 (2008), DOI: 10.1016/j.tcs.2008.05.010 [sci-hub, @tor]

Examples

>>> g = gt.collection.data["polblogs"]
>>> sum(1 for c in gt.max_cliques(g))
49618
Contents