find_cliques¶

find_cliques(G)[source]¶

Search for all maximal cliques in a graph.

Maximal cliques are the largest complete subgraph containing a given node. The largest maximal clique is sometimes called the maximum clique.

Returns :	generator of lists: genetor of member list for each maximal clique

See also

find_cliques_recursive, A

Notes

To obtain a list of cliques, use list(find_cliques(G)).

Based on the algorithm published by Bron & Kerbosch (1973) [R195] as adapated by Tomita, Tanaka and Takahashi (2006) [R196] and discussed in Cazals and Karande (2008) [R197]. The method essentially unrolls the recursion used in the references to avoid issues of recursion stack depth.

This algorithm is not suitable for directed graphs.

This algorithm ignores self-loops and parallel edges as clique is not conventionally defined with such edges.

There are often many cliques in graphs. This algorithm can run out of memory for large graphs.

References

[R195]

(1, 2) Bron, C. and Kerbosch, J. 1973. Algorithm 457: finding all cliques of an undirected graph. Commun. ACM 16, 9 (Sep. 1973), 575-577. http://portal.acm.org/citation.cfm?doid=362342.362367

[R196]

(1, 2) Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi, The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, Volume 363, Issue 1, Computing and Combinatorics, 10th Annual International Conference on Computing and Combinatorics (COCOON 2004), 25 October 2006, Pages 28-42 http://dx.doi.org/10.1016/j.tcs.2006.06.015

[R197]

(1, 2) F. Cazals, C. Karande, A note on the problem of reporting maximal cliques, Theoretical Computer Science, Volume 407, Issues 1-3, 6 November 2008, Pages 564-568, http://dx.doi.org/10.1016/j.tcs.2008.05.010