Graph Drawing

 v. 2023.09 (Elderberry)

No Matches
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.
- Public Member Functions inherited from ogdf::CliqueFinderModule
 CliqueFinderModule ()
 Creates a CliqueFinderModule.
virtual ~CliqueFinderModule ()
void call (const Graph &G, List< List< node > * > &cliqueLists)
 Searches for cliques and returns the list of cliques.
void call (const Graph &G, NodeArray< int > &cliqueNumber)
 Searches for cliques and sets the clique index number for each node.
void setMinSize (int i)
 Sets the minimum size of a clique.

Protected Member Functions

void doCall () override
 Find cliques in m_pCopy.

Private Attributes

 The clique finder to use on R-nodes.

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.
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.
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.
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.
- Protected Attributes inherited from ogdf::CliqueFinderModule
NodeArray< intm_copyCliqueNumber
 The clique number for each node in m_pCopy.
int m_minDegree
 Minimum degree of the nodes in a found clique.
 Copy of m_pGraph without self-loops and multi-edges.

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)

Creates a new CliqueFinderSPQR.

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 56 of file CliqueFinderSPQR.h.

Member Function Documentation

◆ doCall()

void ogdf::CliqueFinderSPQR::doCall ( )

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

The clique finder to use on R-nodes.

Definition at line 64 of file CliqueFinderSPQR.h.

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