Bases: Algorithm
Algorithm for listing all maximal cliques.
The implementation is based on the “hybrid” algorithm described in
Eppstein, D., & Strash, D. (2011). Listing All Maximal Cliques in Large Sparse Real-World Graphs. In P. M. Pardalos & S. Rebennack (Eds.), Experimental Algorithms (pp. 364375). Springer Berlin Heidelberg. Retrieved from http://link.springer.com/chapter/10.1007/978-3-642-20662-7_31
The running time of this algorithm should be in \(O(d^2 * n * 3^{d/3})\) where f is the degeneracy of the graph, i.e., the maximum core number. The running time in practive depends on the structure of the graph. In particular for complex networks it is usually quite fast, even graphs with millions of edges can usually be processed in less than a minute.
G (networkit.Graph) – The graph to list the cliques for
maximumOnly (bool, optional) – A value of True denotes that only one maximum clique is desired. This enables further optimizations of the algorithm to skip smaller cliques more efficiently. This parameter is only considered when no callback is given. Default: False
callback (callable, optional) – If a callable Python object is given, it will be called once for each maximal clique. Then no cliques will be stored. The callback must accept one parameter which is a list of nodes. Default: None
Return all found cliques unless a callback was given.
This method will throw if a callback was given and thus the cliques were not stored. If only the maximum clique was stored, it will return exactly one clique unless the graph is empty.
A list of cliques, each being represented as a list of nodes.
list(list(int))