Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::CliqueFinderModule Class Referenceabstract

Finds cliques. More...

#include <ogdf/clique/CliqueFinderModule.h>

+ Inheritance diagram for ogdf::CliqueFinderModule:

Public Member Functions

 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...
 
Parameter Setters
void setMinSize (int i)
 Sets the minimum size of a clique. More...
 

Static Public Member Functions

Helper Functions
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 Member Functions

virtual void doCall ()=0
 Find cliques in m_pCopy. More...
 

Protected Attributes

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

Private Member Functions

void beginCall (const Graph &G)
 Initializes member variables and calls doCall(). More...
 
void endCall ()
 Frees memory after doCall(). More...
 
bool handleTrivialCases ()
 Checks whether finding cliques in m_pCopy is trivial, i.e. More...
 
void setResults (List< List< node > * > &cliqueLists)
 Sets the results of doCall() using m_copyCliqueNumber. More...
 
void setResults (NodeArray< int > &cliqueNumber)
 Sets the results of doCall() using m_copyCliqueNumber. More...
 

Private Attributes

const Graphm_pGraph
 The original Graph in which cliques are searched. More...
 

Detailed Description

Finds cliques.

A CliqueFinderModule can be called on a graph to retrieve (disjoint) cliques.

Definition at line 46 of file CliqueFinderModule.h.

Constructor & Destructor Documentation

◆ CliqueFinderModule()

ogdf::CliqueFinderModule::CliqueFinderModule ( )
inlineexplicit

Creates a CliqueFinderModule.

By default, it searches for cliques containing at least three nodes. This setting can be changed with setMinSize().

Definition at line 55 of file CliqueFinderModule.h.

◆ ~CliqueFinderModule()

virtual ogdf::CliqueFinderModule::~CliqueFinderModule ( )
inlinevirtual

Definition at line 61 of file CliqueFinderModule.h.

Member Function Documentation

◆ beginCall()

void ogdf::CliqueFinderModule::beginCall ( const Graph G)
private

Initializes member variables and calls doCall().

Parameters
GThe graph in which to search for cliques.

◆ call() [1/2]

void ogdf::CliqueFinderModule::call ( const Graph G,
List< List< node > * > &  cliqueLists 
)

Searches for cliques and returns the list of cliques.

Each clique is represented by a list of member nodes in the list of cliques cliqueLists.

Parameters
GThe graph on which the clique finding algorithm is called.
cliqueListsThe list of cliques.

◆ call() [2/2]

void ogdf::CliqueFinderModule::call ( const Graph G,
NodeArray< int > &  cliqueNumber 
)

Searches for cliques and sets the clique index number for each node.

Each clique will be assigned a different number. Each node gets the number of the clique it is contained in or -1 if the node is not a clique member.

Parameters
GThe graph on which the clique finding algorithm is called.
cliqueNumberThe clique number for each node.

◆ cliqueGraphAttributes()

static void ogdf::CliqueFinderModule::cliqueGraphAttributes ( const Graph G,
const NodeArray< int > &  cliqueNumber,
GraphAttributes GA 
)
static

Labels and colors nodes in the given GraphAttributes according to their clique number.

Note that the coordinates of the nodes are not changed: A separate layout algorithm has to be used to this end.

Parameters
GGraph the cliques belong to.
cliqueNumberThe clique number for each node.
GAIs assigned the node colors and labels.

◆ cliqueListToNumber()

static void ogdf::CliqueFinderModule::cliqueListToNumber ( const Graph G,
const List< List< node > * > &  cliqueLists,
NodeArray< int > &  cliqueNumber 
)
static

Uses a list of cliques to get the clique number of each node.

Parameters
GGraph the cliques belong to.
cliqueListsList of lists, each one representing a clique.
cliqueNumberIs assigned the clique number for each node.

◆ cliqueNumberToList()

static void ogdf::CliqueFinderModule::cliqueNumberToList ( const Graph G,
const NodeArray< int > &  cliqueNumber,
List< List< node > * > &  cliqueLists 
)
static

Uses the clique number for each node to create a list of cliques.

Parameters
GGraph the cliques belong to.
cliqueNumberThe clique number for each node.
cliqueListsIs assigned a list of lists, each one representing a clique.

◆ cliqueOK()

static bool ogdf::CliqueFinderModule::cliqueOK ( const Graph G,
List< node > *  clique,
double  density = 1.0 
)
static

Checks whether density times the number of possible edges exist between clique members.

Parameters
GGraph the cliques belong to.
cliqueThe clique to check.
densityThe fraction in [0,1] of possible edges between clique members that have to exist in order for the check to succeed.
Returns
Whether the check succeeded.

◆ doCall()

virtual void ogdf::CliqueFinderModule::doCall ( )
protectedpure virtual

Find cliques in m_pCopy.

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

Implemented in ogdf::CliqueFinderHeuristic, and ogdf::CliqueFinderSPQR.

◆ endCall()

void ogdf::CliqueFinderModule::endCall ( )
private

Frees memory after doCall().

◆ handleTrivialCases()

bool ogdf::CliqueFinderModule::handleTrivialCases ( )
private

Checks whether finding cliques in m_pCopy is trivial, i.e.

n < 3 or n < m_minDegree, and sets m_copyCliqueNumber if that is the case.

Returns
true iff m_pCopy is a trivial instance.

◆ setMinSize()

void ogdf::CliqueFinderModule::setMinSize ( int  i)
inline

Sets the minimum size of a clique.

Definition at line 86 of file CliqueFinderModule.h.

◆ setResults() [1/2]

void ogdf::CliqueFinderModule::setResults ( List< List< node > * > &  cliqueLists)
private

Sets the results of doCall() using m_copyCliqueNumber.

Warning
The caller is responsible for deleting the list pointers.
Parameters
cliqueListsIs assigned a list of pointers, each one pointing to a list of nodes representing a clique.

◆ setResults() [2/2]

void ogdf::CliqueFinderModule::setResults ( NodeArray< int > &  cliqueNumber)
private

Sets the results of doCall() using m_copyCliqueNumber.

Parameters
cliqueNumberIs assigned the clique number for each node.

Member Data Documentation

◆ m_copyCliqueNumber

NodeArray<int> ogdf::CliqueFinderModule::m_copyCliqueNumber
protected

The clique number for each node in m_pCopy.

Definition at line 184 of file CliqueFinderModule.h.

◆ m_minDegree

int ogdf::CliqueFinderModule::m_minDegree
protected

Minimum degree of the nodes in a found clique.

Definition at line 186 of file CliqueFinderModule.h.

◆ m_pCopy

GraphCopy* ogdf::CliqueFinderModule::m_pCopy
protected

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

Definition at line 182 of file CliqueFinderModule.h.

◆ m_pGraph

const Graph* ogdf::CliqueFinderModule::m_pGraph
private

The original Graph in which cliques are searched.

Definition at line 179 of file CliqueFinderModule.h.


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