Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::CliqueFinderSPQR Class Reference

Finds cliques using SPQR trees. More...

#include <ogdf/clique/CliqueFinderSPQR.h>

+ Inheritance diagram for ogdf::CliqueFinderSPQR:

Public Member Functions

 CliqueFinderSPQR (CliqueFinderModule &cliqueFinder)
 Creates a new CliqueFinderSPQR. 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

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

Private Attributes

CliqueFinderModulem_cliqueFinder
 The clique finder to use on R-nodes. 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 using SPQR trees.

The class CliqueFinderSPQR can be called on a graph to retrieve (disjoint) cliques. It searches for cliques in a graph by first dividing it into its triconnected components using an SPQR tree and then using a given clique finder in each R-node.

Template Parameters
CFThe type of the clique finder to use on R-nodes.

Definition at line 49 of file CliqueFinderSPQR.h.

Constructor & Destructor Documentation

◆ CliqueFinderSPQR()

ogdf::CliqueFinderSPQR::CliqueFinderSPQR ( CliqueFinderModule cliqueFinder)
inlineexplicit

Creates a new CliqueFinderSPQR.

Parameters
cliqueFinderThe clique finder to use on R-nodes. During doCall(), its min size parameter is set to the min size of this.

Definition at line 57 of file CliqueFinderSPQR.h.

Member Function Documentation

◆ doCall()

void ogdf::CliqueFinderSPQR::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.

Member Data Documentation

◆ m_cliqueFinder

CliqueFinderModule& ogdf::CliqueFinderSPQR::m_cliqueFinder
private

The clique finder to use on R-nodes.

Definition at line 67 of file CliqueFinderSPQR.h.


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