All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Public Member Functions | Protected Attributes | List of all members
NetworKit::MaximalCliques Class Reference

Algorithm for listing all maximal cliques. More...

#include <MaximalCliques.h>

Public Member Functions

 MaximalCliques (const Graph &G, bool maximumOnly=false)
 Construct the maximal cliques algorithm with the given graph. More...
 
 MaximalCliques (const Graph &G, std::function< void(const std::vector< node > &)> callback)
 Construct the maximal cliques algorithm with the given graph and a callback. More...
 
void run () override
 Execute the maximal clique listing algorithm. More...
 
const std::vector< std::vector
< node > > & 
getCliques () const
 Return all found cliques unless a callback was given. More...
 
- Public Member Functions inherited from NetworKit::Algorithm
 Algorithm ()
 Constructor to the algorithm base class. More...
 
virtual ~Algorithm ()=default
 Virtual default destructor. More...
 
bool hasFinished () const
 Indicates whether an algorithm has completed computation or not. More...
 
void assureFinished () const
 Assure that the algorithm has been run, throws a std::runtime_error otherwise. More...
 
virtual std::string toString () const
 Returns a string with the algorithm's name and its parameters, if there are any. More...
 
virtual bool isParallel () const
 

Protected Attributes

const GraphG
 
std::vector< std::vector< node > > result
 
std::function< void(const
std::vector< node > &)> 
callback
 
bool maximumOnly
 
- Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
 A boolean variable indicating whether an algorithm has finished its computation or not. More...
 

Detailed Description

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 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.

Constructor & Destructor Documentation

NetworKit::MaximalCliques::MaximalCliques ( const Graph G,
bool  maximumOnly = false 
)

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.

Parameters
GThe graph to list the cliques for.
maximumOnlyIf only a maximum clique shall be found.
NetworKit::MaximalCliques::MaximalCliques ( const Graph G,
std::function< void(const std::vector< node > &)>  callback 
)

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.

Parameters
GThe graph to list cliques for
callbackThe callback to call for each clique.

Member Function Documentation

const std::vector< std::vector< node > > & NetworKit::MaximalCliques::getCliques ( ) const

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.

Returns
a vector of cliques, each being represented as a vector of nodes.
void NetworKit::MaximalCliques::run ( )
overridevirtual

Execute the maximal clique listing algorithm.

Implements NetworKit::Algorithm.

Member Data Documentation

std::function<void(const std::vector<node>&)> NetworKit::MaximalCliques::callback
protected
const Graph& NetworKit::MaximalCliques::G
protected
bool NetworKit::MaximalCliques::maximumOnly
protected
std::vector<std::vector<node> > NetworKit::MaximalCliques::result
protected

The documentation for this class was generated from the following files: