ogdf::CliqueFinder Class Reference

Finds cliques and dense subgraphs. More...

#include <ogdf/graphalg/CliqueFinder.h>

List of all members.

Public Types
enum	postProcess { ppNone, ppSimple }
Public Member Functions
	CliqueFinder (const Graph &G)
	~CliqueFinder ()
void	call (NodeArray< int > &cliqueNumber)
	Searches for cliques and returns the clique index number for each node.
void	call (List< List< node > > &cliqueLists)
	Searches for cliques and returns the list of cliques.
void	setMinSize (int i)
	the minimum degree of the nodes within the clique/subgraph
void	setDensity (int density)
	set the abstract measure of density needed for subgraphs to be detected
Protected Member Functions
void	doCall (int minDegree=2)
void	setResults (NodeArray< int > &cliqueNumber)
void	setResults (List< List< node > > &cliqueLists)
void	setResults (List< List< node > * > &cliqueLists)
void	postProcessCliques (List< List< node > * > &cliqueList, EdgeArray< bool > &usableEdge)
bool	allAdjacent (node v, List< node > *vList)
void	writeGraph (Graph &G, NodeArray< int > &cliqueNumber, const String &fileName)
int	evaluate (node v, EdgeArray< bool > &usableEdge)
void	checkCliques (List< List< node > * > &cliqueList, bool sizeCheck=true)
bool	cliqueOK (List< node > *clique)
void	findClique (node v, List< node > &neighbours, int numRandom=0)
Private Attributes
const Graph *	m_pGraph
GraphCopy *	m_pCopy
NodeArray< int >	m_copyCliqueNumber
NodeArray< bool >	m_usedNode
int	m_minDegree
int	m_numberOfCliques
postProcess	m_postProcess
bool	m_callByList
List< List< node > > *	m_pList
int	m_density

---

Detailed Description

Finds cliques and dense subgraphs.

The class CliqueFinder can be called on a graph to retrieve (disjoint) cliques or dense subgraphs respectively. Uses SPQR trees to find 3-connected components.

In the following, clique always stands for a subgraph with properties that can be defined by the user to change the standard definition of a complete subgraph, e.g. a minimum size/degree etc. We search for cliques in graph G by first dividing G into its triconnnected components and then using a greedy heuristics within each component

Definition at line 84 of file CliqueFinder.h.

---

Member Enumeration Documentation

enum ogdf::CliqueFinder::postProcess

Enumerator:

ppNone
ppSimple

Definition at line 111 of file CliqueFinder.h.

---

Constructor & Destructor Documentation

ogdf::CliqueFinder::CliqueFinder

(

const Graph &

G

)

ogdf::CliqueFinder::~CliqueFinder

(

)

---

Member Function Documentation

bool ogdf::CliqueFinder::allAdjacent	(	node	v,
		List< node > *	vList
	)			[protected]

void ogdf::CliqueFinder::call

(

NodeArray< int > &

cliqueNumber

)

Searches for cliques and returns 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, -1 if not a clique member

void ogdf::CliqueFinder::call

(

List< List< node > > &

cliqueLists

)

Searches for cliques and returns the list of cliques.

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

void ogdf::CliqueFinder::checkCliques	(	List< List< node > * > &	cliqueList,
		bool	sizeCheck = true
	)			[protected]

bool ogdf::CliqueFinder::cliqueOK

(

List< node > *

clique

)

[protected]

void ogdf::CliqueFinder::doCall

(

int

minDegree = 2

)

[protected]

doing the real work, find subgraphs in graph G, skip all nodes with degree < minDegree value 2: all triangles are cliques

int ogdf::CliqueFinder::evaluate	(	node	v,
		EdgeArray< bool > &	usableEdge
	)			[protected]

void ogdf::CliqueFinder::findClique	(	node	v,
		List< node > &	neighbours,
		int	numRandom = 0
	)			[protected]

void ogdf::CliqueFinder::postProcessCliques	(	List< List< node > * > &	cliqueList,
		EdgeArray< bool > &	usableEdge
	)			[protected]

void ogdf::CliqueFinder::setDensity

(

int

density

)

[inline]

set the abstract measure of density needed for subgraphs to be detected

does not have effect for graphs with n<4

Definition at line 117 of file CliqueFinder.h.

void ogdf::CliqueFinder::setMinSize

(

int

i

)

[inline]

the minimum degree of the nodes within the clique/subgraph

Definition at line 110 of file CliqueFinder.h.

void ogdf::CliqueFinder::setResults

(

List< List< node > > &

cliqueLists

)

[protected]

void ogdf::CliqueFinder::setResults

(

List< List< node > * > &

cliqueLists

)

[protected]

void ogdf::CliqueFinder::setResults

(

NodeArray< int > &

cliqueNumber

)

[protected]

void ogdf::CliqueFinder::writeGraph	(	Graph &	G,
		NodeArray< int > &	cliqueNumber,
		const String &	fileName
	)			[protected]

---

Member Data Documentation

bool ogdf::CliqueFinder::m_callByList [private]

Definition at line 169 of file CliqueFinder.h.

NodeArray<int> ogdf::CliqueFinder::m_copyCliqueNumber [private]

Definition at line 163 of file CliqueFinder.h.

int ogdf::CliqueFinder::m_density [private]

Definition at line 172 of file CliqueFinder.h.

int ogdf::CliqueFinder::m_minDegree [private]

Definition at line 166 of file CliqueFinder.h.

int ogdf::CliqueFinder::m_numberOfCliques [private]

Definition at line 167 of file CliqueFinder.h.

GraphCopy* ogdf::CliqueFinder::m_pCopy [private]

Definition at line 162 of file CliqueFinder.h.

const Graph* ogdf::CliqueFinder::m_pGraph [private]

Definition at line 161 of file CliqueFinder.h.

List< List<node> >* ogdf::CliqueFinder::m_pList [private]

Definition at line 170 of file CliqueFinder.h.

postProcess ogdf::CliqueFinder::m_postProcess [private]

Definition at line 168 of file CliqueFinder.h.

NodeArray<bool> ogdf::CliqueFinder::m_usedNode [private]

Definition at line 164 of file CliqueFinder.h.

---

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

• ogdf/graphalg/CliqueFinder.h