Defined in File MaximalCliques.hpp
public NetworKit::Algorithm (Class 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. 364 - 375). 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 \cdot n \cdot 3^{d/3})\) where \(d\) is the degeneracy of the graph, i.e., the maximum core number. The running time in practice 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.
Public Functions
Construct the maximal cliques algorithm with the given graph.
If the maximumOnly argument is set, the algorithm will only store the clique of maximum size. Further, this enables some optimizations to skip smaller cliques more efficiently leading to a reduced running time.
G – The graph to list the cliques for.
maximumOnly – If only a maximum clique shall be found.
Construct the maximal cliques algorithm with the given graph and a callback.
The callback is called once for each found clique with a reference to the clique. Note that the reference is to an internal object, the callback should not assume that this reference is still valid after it returned.
G – The graph to list cliques for
callback – The callback to call for each clique.
Execute the maximal clique listing algorithm.
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 vector of cliques, each being represented as a vector of nodes.