Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

enumerate_all_cliques

enumerate_all_cliques(G)

Returns all cliques in an undirected graph.

This method returns cliques of size (cardinality) k = 1, 2, 3, …, maxDegree - 1.

Where maxDegree is the maximal degree of any node in the graph.

Parameters:G (undirected graph) – Returns:generator of lists Return type:generator of list for each clique.

Notes

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

Based on the algorithm published by Zhang et al. (2005) [1] and adapted to output all cliques discovered.

This algorithm is not applicable on 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 however, hopefully, does not run out of memory since it only keeps candidate sublists in memory and continuously removes exhausted sublists.

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. doi: 10.1109/SC.2005.29. http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1559964&isnumber=33129