networkx.find_cliques

find_cliques(G)

Search for all maximal cliques in a graph.

This algorithm searches for maximal cliques in a graph. maximal cliques are the largest complete subgraph containing a given point. The largest maximal clique is sometimes called the maximum clique.

This implementation is a generator of lists each of which contains the members of a maximal clique. To obtain a list of cliques, use list(find_cliques(G)). The method essentially unrolls the recursion used in the references to avoid issues of recursion stack depth.

See also

find_cliques_recursive, A

References

Based on the algorithm published by Bron & Kerbosch (1973)

http://doi.acm.org/10.1145/362342.362367

as adapated by Tomita, Tanaka and Takahashi (2006)

http://dx.doi.org/10.1016/j.tcs.2006.06.015

and discussed in Cazals and Karande (2008)

http://dx.doi.org/10.1016/j.tcs.2008.05.010