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
AdjacencyOracle *	m_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...

GraphCopy *	m_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 51 of file CliqueFinderHeuristic.h.

Constructor & Destructor Documentation

◆ CliqueFinderHeuristic()

ogdf::CliqueFinderHeuristic::CliqueFinderHeuristic ( )

explicit

Creates a CliqueFinderHeuristic.

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

v	The node to check.
vList	The 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

v	The node around which to search for a clique/dense subgraph.
neighbours	The 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

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

density value in [0.0 ... 1.0]

Definition at line 72 of file CliqueFinderHeuristic.h.

◆ setPostProcessing()

void ogdf::CliqueFinderHeuristic::setPostProcessing ( bool postProcess )

inline

Sets whether postprocessing should be activated.

Parameters

postProcess Whether postprocessing should be activated.

Definition at line 61 of file CliqueFinderHeuristic.h.

Member Data Documentation

◆ m_adjOracle

AdjacencyOracle* ogdf::CliqueFinderHeuristic::m_adjOracle

private

Adjacency oracle for m_pCopy.

Definition at line 139 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 135 of file CliqueFinderHeuristic.h.

◆ m_postProcess

bool ogdf::CliqueFinderHeuristic::m_postProcess

private

Whether postprocessing should be activated.

Definition at line 137 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 141 of file CliqueFinderHeuristic.h.

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

include/ogdf/clique/CliqueFinderHeuristic.h

OpenGraph DrawingFramework

Public Member Functions

Protected Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ CliqueFinderHeuristic()

Member Function Documentation

◆ allAdjacent()

◆ doCall()

◆ evaluate()

◆ findClique()

◆ postProcessCliques()

◆ preProcess()

◆ setDensity()

◆ setPostProcessing()

Member Data Documentation

◆ m_adjOracle

◆ m_density

◆ m_postProcess

◆ m_usedNode

Open
Graph Drawing
Framework