Finds cliques. More...

#include <ogdf/clique/CliqueFinderModule.h>

Inheritance diagram for ogdf::CliqueFinderModule:

Public Member Functions
	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.

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

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.

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 Member Functions
virtual void	doCall ()=0
	Find cliques in m_pCopy.

Protected Attributes
NodeArray< int >	m_copyCliqueNumber
	The clique number for each node in m_pCopy.

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

GraphCopy *	m_pCopy
	Copy of m_pGraph without self-loops and multi-edges.

Private Member Functions
void	beginCall (const Graph &G)
	Initializes member variables and calls doCall().

void	endCall ()
	Frees memory after doCall().

bool	handleTrivialCases ()
	Checks whether finding cliques in m_pCopy is trivial, i.e.

void	setResults (List< List< node > * > &cliqueLists)
	Sets the results of doCall() using m_copyCliqueNumber.

void	setResults (NodeArray< int > &cliqueNumber)
	Sets the results of doCall() using m_copyCliqueNumber.

Private Attributes
const Graph *	m_pGraph
	The original Graph in which cliques are searched.

Detailed Description

Finds cliques.

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

Definition at line 52 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 60 of file CliqueFinderModule.h.

◆ ~CliqueFinderModule()

virtual ogdf::CliqueFinderModule::~CliqueFinderModule ( )

inlinevirtual

Definition at line 62 of file CliqueFinderModule.h.

Member Function Documentation

◆ beginCall()

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

private

Initializes member variables and calls doCall().

Parameters

G	The 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

G	The graph on which the clique finding algorithm is called.
cliqueLists	The 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

G	The graph on which the clique finding algorithm is called.
cliqueNumber	The 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

G	Graph the cliques belong to.
cliqueNumber	The clique number for each node.
GA	Is 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

G	Graph the cliques belong to.
cliqueLists	List of lists, each one representing a clique.
cliqueNumber	Is 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

G	Graph the cliques belong to.
cliqueNumber	The clique number for each node.
cliqueLists	Is 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

G	Graph the cliques belong to.
clique	The clique to check.
density	The 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 87 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

cliqueLists Is 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

cliqueNumber Is 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 180 of file CliqueFinderModule.h.

◆ m_minDegree

int ogdf::CliqueFinderModule::m_minDegree

protected

Minimum degree of the nodes in a found clique.

Definition at line 182 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 178 of file CliqueFinderModule.h.

◆ m_pGraph

const Graph* ogdf::CliqueFinderModule::m_pGraph

private

The original Graph in which cliques are searched.

Definition at line 175 of file CliqueFinderModule.h.

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

include/ogdf/clique/CliqueFinderModule.h

OpenGraph DrawingFramework

Public Member Functions

Static Public Member Functions

Protected Member Functions

Protected Attributes

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ CliqueFinderModule()

◆ ~CliqueFinderModule()

Member Function Documentation

◆ beginCall()

◆ call() [1/2]

◆ call() [2/2]

◆ cliqueGraphAttributes()

◆ cliqueListToNumber()

◆ cliqueNumberToList()

◆ cliqueOK()

◆ doCall()

◆ endCall()

◆ handleTrivialCases()

◆ setMinSize()

◆ setResults() [1/2]

◆ setResults() [2/2]

Member Data Documentation

◆ m_copyCliqueNumber

◆ m_minDegree

◆ m_pCopy

◆ m_pGraph

Open
Graph Drawing
Framework