Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::ModifiedNibbleClusterer Class Reference

The modified nibble clustering algorithm. More...

#include <ogdf/graphalg/ModifiedNibbleClusterer.h>

Public Types

enum  StartNodeStrategy { StartNodeStrategy::MinDeg, StartNodeStrategy::MaxDeg, StartNodeStrategy::Random }
 

Public Member Functions

 ModifiedNibbleClusterer ()
 
 ~ModifiedNibbleClusterer ()
 
long call (Graph &G, NodeArray< long > &clusterNum)
 Call method: Creates a clustering of G Returns number of created clusters and sets cluster index for each node in clusterNum. More...
 
long call (Graph &G, NodeArray< long > &clusterNum, NodeArray< long > &topLevelNum)
 A convenience method. Due to the characteristics of the algorithm (not very accurate, fast for large graphs), we could have a medium number (several hundreds) of clusters, and could need a further level of clustering. On the other hand, fully recursive clustering does not make much sense as after a second level there will be not to many clusters left. topLevelNum keeps a cluster number in the top level of the two level cluster hierarchy. More...
 
void setClusterSizeThreshold (int threshold)
 
void setMaxClusterNum (int i)
 Call method: Creates a clustering of G in C Returns number of created clusters. More...
 
void setMaxClusterSize (long i)
 

Protected Member Functions

long activeNodeBound ()
 
int aPGP (int i)
 
double findBestCluster (NodeArray< bool > &isActive, std::vector< node > &activeNodes, std::vector< node > &cluster)
 
void initialize ()
 
long maxClusterSize ()
 
void modifiedNibble (node snode, std::vector< node > &bestCluster)
 main step with walks starting from snode More...
 
void postProcess ()
 
double pot (double r, long i)
 
node selectStartNode ()
 select start node according to some strategy More...
 
void spreadValues (NodeArray< bool > &isActive, std::vector< node > &activeNodes, NodeArray< double > &probUpdate)
 

Private Member Functions

bool testSpreadSum ()
 

Private Attributes

int m_clusterThreshold
 
long m_maxActiveNodes
 
long m_maxClusterSize
 
Graphm_pG
 
GraphCopym_pGC
 
NodeArray< double > m_prob
 
StartNodeStrategy m_sns
 
double m_spreadProbability
 
node m_startNode
 
int m_steps
 
int maxClusterNum
 

Detailed Description

The modified nibble clustering algorithm.

Modified Nibble Clustering Algorithm (as given in Graph Clustering for Keyword Search. R. Catherine, S. Sudarshan). The algorithm is very fast (and thus suited for huge graphs) and simple to implement, however not very accurate.

State: Experimental - Only use when you know what you are doing

To be used in remainders of graph decomposition for clustering (Remove trees first, then use BC, SPQR,)

Definition at line 54 of file ModifiedNibbleClusterer.h.

Member Enumeration Documentation

◆ StartNodeStrategy

Enumerator
MinDeg 
MaxDeg 
Random 

Definition at line 102 of file ModifiedNibbleClusterer.h.

Constructor & Destructor Documentation

◆ ModifiedNibbleClusterer()

ogdf::ModifiedNibbleClusterer::ModifiedNibbleClusterer ( )
inline

Definition at line 57 of file ModifiedNibbleClusterer.h.

◆ ~ModifiedNibbleClusterer()

ogdf::ModifiedNibbleClusterer::~ModifiedNibbleClusterer ( )
inline

Definition at line 68 of file ModifiedNibbleClusterer.h.

Member Function Documentation

◆ activeNodeBound()

long ogdf::ModifiedNibbleClusterer::activeNodeBound ( )
inlineprotected

< f in publication Rose Catherine K., S. Sudarshan

Definition at line 130 of file ModifiedNibbleClusterer.h.

◆ aPGP()

int ogdf::ModifiedNibbleClusterer::aPGP ( int  i)
inlineprotected

Definition at line 116 of file ModifiedNibbleClusterer.h.

◆ call() [1/2]

long ogdf::ModifiedNibbleClusterer::call ( Graph G,
NodeArray< long > &  clusterNum 
)

Call method: Creates a clustering of G Returns number of created clusters and sets cluster index for each node in clusterNum.

◆ call() [2/2]

long ogdf::ModifiedNibbleClusterer::call ( Graph G,
NodeArray< long > &  clusterNum,
NodeArray< long > &  topLevelNum 
)

A convenience method. Due to the characteristics of the algorithm (not very accurate, fast for large graphs), we could have a medium number (several hundreds) of clusters, and could need a further level of clustering. On the other hand, fully recursive clustering does not make much sense as after a second level there will be not to many clusters left. topLevelNum keeps a cluster number in the top level of the two level cluster hierarchy.

◆ findBestCluster()

double ogdf::ModifiedNibbleClusterer::findBestCluster ( NodeArray< bool > &  isActive,
std::vector< node > &  activeNodes,
std::vector< node > &  cluster 
)
protected

◆ initialize()

void ogdf::ModifiedNibbleClusterer::initialize ( )
protected

◆ maxClusterSize()

long ogdf::ModifiedNibbleClusterer::maxClusterSize ( )
inlineprotected

Definition at line 111 of file ModifiedNibbleClusterer.h.

◆ modifiedNibble()

void ogdf::ModifiedNibbleClusterer::modifiedNibble ( node  snode,
std::vector< node > &  bestCluster 
)
protected

main step with walks starting from snode

◆ postProcess()

void ogdf::ModifiedNibbleClusterer::postProcess ( )
protected

◆ pot()

double ogdf::ModifiedNibbleClusterer::pot ( double  r,
long  i 
)
inlineprotected

Definition at line 125 of file ModifiedNibbleClusterer.h.

◆ selectStartNode()

node ogdf::ModifiedNibbleClusterer::selectStartNode ( )
protected

select start node according to some strategy

◆ setClusterSizeThreshold()

void ogdf::ModifiedNibbleClusterer::setClusterSizeThreshold ( int  threshold)
inline

Definition at line 95 of file ModifiedNibbleClusterer.h.

◆ setMaxClusterNum()

void ogdf::ModifiedNibbleClusterer::setMaxClusterNum ( int  i)
inline

Call method: Creates a clustering of G in C Returns number of created clusters.

Definition at line 92 of file ModifiedNibbleClusterer.h.

◆ setMaxClusterSize()

void ogdf::ModifiedNibbleClusterer::setMaxClusterSize ( long  i)
inline

Definition at line 93 of file ModifiedNibbleClusterer.h.

◆ spreadValues()

void ogdf::ModifiedNibbleClusterer::spreadValues ( NodeArray< bool > &  isActive,
std::vector< node > &  activeNodes,
NodeArray< double > &  probUpdate 
)
protected

◆ testSpreadSum()

bool ogdf::ModifiedNibbleClusterer::testSpreadSum ( )
inlineprivate

Definition at line 153 of file ModifiedNibbleClusterer.h.

Member Data Documentation

◆ m_clusterThreshold

int ogdf::ModifiedNibbleClusterer::m_clusterThreshold
private

Definition at line 141 of file ModifiedNibbleClusterer.h.

◆ m_maxActiveNodes

long ogdf::ModifiedNibbleClusterer::m_maxActiveNodes
private

Definition at line 143 of file ModifiedNibbleClusterer.h.

◆ m_maxClusterSize

long ogdf::ModifiedNibbleClusterer::m_maxClusterSize
private

Definition at line 142 of file ModifiedNibbleClusterer.h.

◆ m_pG

Graph* ogdf::ModifiedNibbleClusterer::m_pG
private

Definition at line 148 of file ModifiedNibbleClusterer.h.

◆ m_pGC

GraphCopy* ogdf::ModifiedNibbleClusterer::m_pGC
private

Definition at line 149 of file ModifiedNibbleClusterer.h.

◆ m_prob

NodeArray<double> ogdf::ModifiedNibbleClusterer::m_prob
private

Definition at line 147 of file ModifiedNibbleClusterer.h.

◆ m_sns

StartNodeStrategy ogdf::ModifiedNibbleClusterer::m_sns
private

Definition at line 150 of file ModifiedNibbleClusterer.h.

◆ m_spreadProbability

double ogdf::ModifiedNibbleClusterer::m_spreadProbability
private

Definition at line 145 of file ModifiedNibbleClusterer.h.

◆ m_startNode

node ogdf::ModifiedNibbleClusterer::m_startNode
private

Definition at line 146 of file ModifiedNibbleClusterer.h.

◆ m_steps

int ogdf::ModifiedNibbleClusterer::m_steps
private

Definition at line 140 of file ModifiedNibbleClusterer.h.

◆ maxClusterNum

int ogdf::ModifiedNibbleClusterer::maxClusterNum
private

Definition at line 144 of file ModifiedNibbleClusterer.h.


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