enumerate_all_cliques

enumerate_all_cliques(G)

Returns all cliques in an undirected graph.

This function returns an iterator over cliques, each of which is a list of nodes. The iteration is ordered by cardinality of the cliques: first all cliques of size one, then all cliques of size two, etc.

Parameters

GNetworkX graph

An undirected graph.

Returns

iterator

An iterator over cliques, each of which is a list of nodes in G. The cliques are ordered according to size.

Notes

To obtain a list of all cliques, use list(enumerate_all_cliques(G)). However, be aware that in the worst-case, the length of this list can be exponential in the number of nodes in the graph (for example, when the graph is the complete graph). This function avoids storing all cliques in memory by only keeping current candidate node lists in memory during its search.

The implementation is adapted from the algorithm by Zhang, et al. (2005) [1] to output all cliques discovered.

This algorithm ignores self-loops and parallel edges, since cliques are not conventionally defined with such edges.

References

1

Yun Zhang, Abu-Khzam, F.N., Baldwin, N.E., Chesler, E.J., Langston, M.A., Samatova, N.F., “Genome-Scale Computational Approaches to Memory-Intensive Applications in Systems Biology”. Supercomputing, 2005. Proceedings of the ACM/IEEE SC 2005 Conference, pp. 12, 12–18 Nov. 2005. <https://doi.org/10.1109/SC.2005.29>.