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
Graph *	m_pG
GraphCopy *	m_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 58 of file ModifiedNibbleClusterer.h.

Member Enumeration Documentation

StartNodeStrategy

enum ogdf::ModifiedNibbleClusterer::StartNodeStrategy

strong

Enumerator
MinDeg
MaxDeg
Random

Definition at line 103 of file ModifiedNibbleClusterer.h.

Constructor & Destructor Documentation

ModifiedNibbleClusterer()

ogdf::ModifiedNibbleClusterer::ModifiedNibbleClusterer ( )

inline

Definition at line 60 of file ModifiedNibbleClusterer.h.

~ModifiedNibbleClusterer()

ogdf::ModifiedNibbleClusterer::~ModifiedNibbleClusterer ( )

inline

Definition at line 69 of file ModifiedNibbleClusterer.h.

Member Function Documentation

activeNodeBound()

long ogdf::ModifiedNibbleClusterer::activeNodeBound ( )

inlineprotected

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

Definition at line 128 of file ModifiedNibbleClusterer.h.

aPGP()

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

inlineprotected

Definition at line 118 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 115 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 126 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 97 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 94 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 150 of file ModifiedNibbleClusterer.h.

Member Data Documentation

m_clusterThreshold

int ogdf::ModifiedNibbleClusterer::m_clusterThreshold

private

Definition at line 138 of file ModifiedNibbleClusterer.h.

m_maxActiveNodes

long ogdf::ModifiedNibbleClusterer::m_maxActiveNodes

private

Definition at line 140 of file ModifiedNibbleClusterer.h.

m_maxClusterSize

long ogdf::ModifiedNibbleClusterer::m_maxClusterSize

private

Definition at line 139 of file ModifiedNibbleClusterer.h.

m_pG

Graph* ogdf::ModifiedNibbleClusterer::m_pG

private

Definition at line 145 of file ModifiedNibbleClusterer.h.

m_pGC

GraphCopy* ogdf::ModifiedNibbleClusterer::m_pGC

private

Definition at line 146 of file ModifiedNibbleClusterer.h.

m_prob

NodeArray<double> ogdf::ModifiedNibbleClusterer::m_prob

private

Definition at line 144 of file ModifiedNibbleClusterer.h.

m_sns

StartNodeStrategy ogdf::ModifiedNibbleClusterer::m_sns

private

Definition at line 147 of file ModifiedNibbleClusterer.h.

m_spreadProbability

double ogdf::ModifiedNibbleClusterer::m_spreadProbability

private

Definition at line 142 of file ModifiedNibbleClusterer.h.

m_startNode

node ogdf::ModifiedNibbleClusterer::m_startNode

private

Definition at line 143 of file ModifiedNibbleClusterer.h.

m_steps

int ogdf::ModifiedNibbleClusterer::m_steps

private

Definition at line 137 of file ModifiedNibbleClusterer.h.

maxClusterNum

int ogdf::ModifiedNibbleClusterer::maxClusterNum

private

Definition at line 141 of file ModifiedNibbleClusterer.h.

---

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

• include/ogdf/graphalg/ModifiedNibbleClusterer.h