Open
Graph Drawing
Framework

 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

AdjacencyOraclem_adjOracle
 Adjacency oracle for m_pCopy. More...
 
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...
 

Additional Inherited Members

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

Constructor & Destructor Documentation

◆ CliqueFinderHeuristic()

ogdf::CliqueFinderHeuristic::CliqueFinderHeuristic ( )
explicit

Member Function Documentation

◆ allAdjacent()

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
vThe node to check.
vListThe 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
vThe node around which to search for a clique/dense subgraph.
neighboursThe 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
cliqueListThe 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
densityvalue 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
postProcessWhether postprocessing should be activated.

Definition at line 58 of file CliqueFinderHeuristic.h.

Member Data Documentation

◆ m_adjOracle

AdjacencyOracle* ogdf::CliqueFinderHeuristic::m_adjOracle
private

Adjacency oracle for m_pCopy.

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<bool> 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: