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

Cut clustering algorithm as defined in Flake, Gary William; Tarjan, Robert E. More...

#include <CutClustering.h>

Public Member Functions

 CutClustering (const Graph &G, edgeweight alpha)
 Initialize cut clustering algorithm with parameter alpha. More...
 
virtual void run () override
 Apply algorithm to graph. More...
 
virtual std::string toString () const override
 
- Public Member Functions inherited from NetworKit::CommunityDetectionAlgorithm
 CommunityDetectionAlgorithm (const Graph &G)
 A community detection algorithm operates on a graph, so the constructor expects a graph. More...
 
 CommunityDetectionAlgorithm (const Graph &G, const Partition baseClustering)
 A community detection algorithm operates on a graph, so the constructor expects a graph. More...
 
virtual ~CommunityDetectionAlgorithm ()=default
 Default destructor. More...
 
virtual Partition getPartition ()
 Returns the result of the run method or throws an error, if the algorithm hasn't run yet. 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 bool isParallel () const
 

Static Public Member Functions

static std::map< edgeweight,
Partition
getClusterHierarchy (const Graph &G)
 Get the complete hierarchy with all possible parameter values. More...
 

Additional Inherited Members

- Protected Attributes inherited from NetworKit::CommunityDetectionAlgorithm
const GraphG
 
Partition result
 
- Protected Attributes inherited from NetworKit::Algorithm
bool hasRun
 A boolean variable indicating whether an algorithm has finished its computation or not. More...
 

Detailed Description

Cut clustering algorithm as defined in Flake, Gary William; Tarjan, Robert E.

; Tsioutsiouliklis, Kostas. Graph Clustering and Minimum Cut Trees. Internet Mathematics 1 (2003), no. 4, 385–408.

Constructor & Destructor Documentation

NetworKit::CutClustering::CutClustering ( const Graph G,
NetworKit::edgeweight  alpha 
)

Initialize cut clustering algorithm with parameter alpha.

A value of 0 gives a clustering with one cluster with all nodes, A value that equals to the largest edge weight gives singleton clusters.

Parameters
alphaThe parameter for the cut clustering

Member Function Documentation

std::map< NetworKit::edgeweight, NetworKit::Partition > NetworKit::CutClustering::getClusterHierarchy ( const Graph G)
static

Get the complete hierarchy with all possible parameter values.

Each reported parameter value is the lower bound for the range in which the corresponding clustering is calculated by the cut clustering algorithm.

Warning: all reported parameter values are slightly too high in order to avoid wrong clusterings because of numerical inaccuracies. Furthermore the completeness of the hierarchy cannot be guaranteed because of these inaccuracies. This implementation hasn't been optimized for performance.

Parameters
GThe Graph instance for which the hierarchy shall be calculated
Returns
The hierarchy as map
void NetworKit::CutClustering::run ( )
overridevirtual

Apply algorithm to graph.

Warning: due to numerical errors the resulting clusters might not be correct. This implementation uses the Edmonds-Karp algorithm for the cut calculation.

Implements NetworKit::CommunityDetectionAlgorithm.

std::string NetworKit::CutClustering::toString ( ) const
overridevirtual
Returns
string representation of algorithm and parameters.

Reimplemented from NetworKit::CommunityDetectionAlgorithm.


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