# OpenGraph DrawingFramework

v. 2022.02 (Dogwood)

ogdf::CliqueFinderHeuristic Class Reference

Finds cliques and dense subgraphs using a heuristic. More...

#include <ogdf/clique/CliqueFinderHeuristic.h>

Inheritance diagram for ogdf::CliqueFinderHeuristic:

## Public Member Functions

CliqueFinderHeuristic ()
Creates a CliqueFinderHeuristic. More...

void setDensity (double density)
Sets the density needed for subgraphs to be detected. More...

void setPostProcessing (bool postProcess)
Sets whether postprocessing should be activated. More...

Public Member Functions inherited from ogdf::CliqueFinderModule
CliqueFinderModule ()
Creates a CliqueFinderModule. More...

virtual ~CliqueFinderModule ()

void call (const Graph &G, List< List< node > * > &cliqueLists)
Searches for cliques and returns the list of cliques. More...

void call (const Graph &G, NodeArray< int > &cliqueNumber)
Searches for cliques and sets the clique index number for each node. More...

void setMinSize (int i)
Sets the minimum size of a clique. More...

## Protected Member Functions

bool allAdjacent (node v, List< node > *vList) const
Checks whether v is adjacent to (at least m_density times) all nodes in vList. More...

void doCall () override
Find cliques in m_pCopy. More...

int evaluate (node v)
Evaluates v in m_pCopy heuristically concerning its qualification as a clique start node. More...

void findClique (node v, List< node > &neighbours)
Searches for a clique/dense subgraph around node v in list neighbours. More...

void postProcessCliques (List< List< node > * > &cliqueList)
If postprocessing is activated, use the result of the first phase and revisit cliques that are too small. More...

void preProcess ()
Deletes all nodes from m_pCopy with degree < m_density * m_minDegree in O(n+m). More...

## Private Attributes

double m_density
Value in [0,1] defining how dense subgraphs need to be. More...

bool m_postProcess
Whether postprocessing should be activated. More...

NodeArray< bool > m_usedNode
Whether the node is already assigned to a clique. More...

Static Public Member Functions inherited from ogdf::CliqueFinderModule
static void cliqueListToNumber (const Graph &G, const List< List< node > * > &cliqueLists, NodeArray< int > &cliqueNumber)
Uses a list of cliques to get the clique number of each node. More...

static void cliqueNumberToList (const Graph &G, const NodeArray< int > &cliqueNumber, List< List< node > * > &cliqueLists)
Uses the clique number for each node to create a list of cliques. More...

static void cliqueGraphAttributes (const Graph &G, const NodeArray< int > &cliqueNumber, GraphAttributes &GA)
Labels and colors nodes in the given GraphAttributes according to their clique number. More...

static bool cliqueOK (const Graph &G, List< node > *clique, double density=1.0)
Checks whether density times the number of possible edges exist between clique members. More...

Protected Attributes inherited from ogdf::CliqueFinderModule
NodeArray< int > m_copyCliqueNumber
The clique number for each node in m_pCopy. More...

int m_minDegree
Minimum degree of the nodes in a found clique. More...

GraphCopym_pCopy
Copy of m_pGraph without self-loops and multi-edges. More...

## Detailed Description

Finds cliques and dense subgraphs using a heuristic.

The class CliqueFinderHeuristic can be called on a graph to retrieve (disjoint) cliques or dense subgraphs respectively by using a greedy heuristic.

Definition at line 47 of file CliqueFinderHeuristic.h.

## ◆ CliqueFinderHeuristic()

 ogdf::CliqueFinderHeuristic::CliqueFinderHeuristic ( )
explicit

## Member Function Documentation

 bool ogdf::CliqueFinderHeuristic::allAdjacent ( node v, List< node > * vList ) const
protected

Checks whether v is adjacent to (at least m_density times) all nodes in vList.

Warning
m_pGraph must be parallel free!
Parameters
 v The node to check. vList The nodes that potentially form a dense subgraph with v.
Returns
whether node v is adjacent to (at least m_density times) all nodes in vList.

## ◆ doCall()

 void ogdf::CliqueFinderHeuristic::doCall ( )
overrideprotectedvirtual

Find cliques in m_pCopy.

The found cliques are noted in m_copyCliqueNumber. Clique nodes get a number >= 0, all other nodes -1.

Implements ogdf::CliqueFinderModule.

## ◆ evaluate()

 int ogdf::CliqueFinderHeuristic::evaluate ( node v )
protected

Evaluates v in m_pCopy heuristically concerning its qualification as a clique start node.

The higher this value, the better the node as a clique start node.

Returns
The number of 3-circles starting at v.

## ◆ findClique()

 void ogdf::CliqueFinderHeuristic::findClique ( node v, List< node > & neighbours )
protected

Searches for a clique/dense subgraph around node v in list neighbours.

neighbours + v will form a clique/dense subgraph afterwards.

Parameters
 v The node around which to search for a clique/dense subgraph. neighbours The nodes which potentially form a clique together with v. Is assigned a list of nodes that actually forms a clique/dense subgraph together with v.

## ◆ postProcessCliques()

 void ogdf::CliqueFinderHeuristic::postProcessCliques ( List< List< node > * > & cliqueList )
protected

If postprocessing is activated, use the result of the first phase and revisit cliques that are too small.

These cliques are rearranged to potentially find new, bigger cliques.

Parameters
 cliqueList The cliques to postprocess.

## ◆ preProcess()

 void ogdf::CliqueFinderHeuristic::preProcess ( )
protected

Deletes all nodes from m_pCopy with degree < m_density * m_minDegree in O(n+m).

## ◆ setDensity()

 void ogdf::CliqueFinderHeuristic::setDensity ( double density )
inline

Sets the density needed for subgraphs to be detected.

For a subgraph of size k to recognized as dense, it has to contain at least (density * (k*(k-1))/2) edges. This setting does not have an effect for graphs with less than 3 nodes.

Parameters
 density value in [0.0 ... 1.0]

Definition at line 71 of file CliqueFinderHeuristic.h.

## ◆ setPostProcessing()

 void ogdf::CliqueFinderHeuristic::setPostProcessing ( bool postProcess )
inline

Sets whether postprocessing should be activated.

Parameters
 postProcess Whether postprocessing should be activated.

Definition at line 58 of file CliqueFinderHeuristic.h.

## Member Data Documentation

private

Definition at line 138 of file CliqueFinderHeuristic.h.

## ◆ m_density

 double ogdf::CliqueFinderHeuristic::m_density
private

Value in [0,1] defining how dense subgraphs need to be.

Definition at line 134 of file CliqueFinderHeuristic.h.

## ◆ m_postProcess

 bool ogdf::CliqueFinderHeuristic::m_postProcess
private

Whether postprocessing should be activated.

Definition at line 136 of file CliqueFinderHeuristic.h.

## ◆ m_usedNode

 NodeArray ogdf::CliqueFinderHeuristic::m_usedNode
private

Whether the node is already assigned to a clique.

Definition at line 140 of file CliqueFinderHeuristic.h.

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