#include <ogdf/cluster/ClusterAnalysis.h>

Public Member Functions
	ClusterAnalysis (const ClusterGraph &C, bool indyBags=false)
	Constructor. Performs all analyses and in case indyBags is set to true, also computes a partition into independently solvable subproblems for cluster planarization (if applicable).

	ClusterAnalysis (const ClusterGraph &C, bool oalists, bool indyBags)
	Additionally allows to forbid storing lists of outer active vertices.

	~ClusterAnalysis ()

int	bagIndex (node v, cluster c)
	Returns bag index number for a vertex `v` in cluster `c`.

int	indyBagIndex (node v)
	Returns independent bag index number for a vertex `v`.

cluster	indyBagRoot (int i)
	Returns root cluster of independent bag. Note that this cluster either has direct vertex members or more than one child.

int	innerActive (cluster c) const
	Returns number of inneractive vertices of cluster c.

bool	isInnerActive (node v, cluster c) const

bool	isOuterActive (node v, cluster c) const
	Returns outer activity status for vertex `v` wrt cluster `c`.

List< edge > &	lcaEdges (cluster c)
	Returns list of edges for cluster c with lca c.

int	minIALevel (node v) const
	Returns the highest (smallest) level depth for which a vertex is inner active, only initialized if vertex is inner active.

int	minIOALevel (node v) const
	Returns the highest (smallest) level depth for which a vertex is inner or outer active.

int	minOALevel (node v) const
	Returns the highest (smallest) level depth for which a vertex is outer active, only initialized if vertex is outer active.

int	numberOfBags (cluster c) const
	Returns number of bags for cluster `c`.

int	numberOfIndyBags ()
	Returns number of independent bags in clustergraph, -1 in case no independent bags were computed. Ascending consecutive numbers are assigned, starting from 0.

List< node > &	oaNodes (cluster c)
	Returns list of outeractive vertices for cluster `c`. The result is only valid if lists are stored, i.e. m_storeoalists is true.

int	outerActive (cluster c) const
	Returns number of outeractive vertices of cluster c.

Static Public Attributes
static const int	DefaultIndex

static const int	IsNotActiveBound

Protected Member Functions
void	computeBags ()
	Compute bags per cluster and store result as vertex-bag index in m_bagIndex.

void	computeIndyBags ()
	Compute independent bags per cluster and store result as vertex-indyBag index in m_indyBagNumber.

Private Member Functions
void	cleanUp ()
	Deletes dynamically allocated structures.

void	init ()
	Initialize the structures, performs analyses.

void	partitionCluster (ListConstIterator< node > &nodeIt, cluster c, HashArray< int, List< node > > &bagNodes, HashArray< int, bool > &indyBag, Skiplist< int * > &indexNumbers, Array< cluster > &bagRoots)
	Runs through a list of vertices (starting with the one `nodeIT` points to) which is expected to be a full list of cluster vertices in `c`. Depending on outer activity and bag index number of the vertices, independent bags are detected and a corresponding index is assigned accordingly for each vertex. If omitChildBags is set to true, already processed vertices are skipped.

Private Attributes
NodeArray< ClusterArray< int > * >	m_bagindex
	We store the bag affiliation of the vertices for each cluster. A value of -1 indicates that the vertex is not a member of the cluster.

ClusterArray< int > *	m_bags
	Number of bags per cluster (stored even if vertex list is not stored)

const ClusterGraph *	m_C

NodeArray< ClusterArray< int > * >	m_iactive

NodeArray< int >	m_ialevel

ClusterArray< int > *	m_ianum
	Number of inner active vertices.

NodeArray< int >	m_indyBagNumber
	Each independent bag has a different number.

cluster *	m_indyBagRoots

const bool	m_indyBags
	If true, a node partition into independent bags is computed which can be used for dividing the input instance into smaller problems wrt cluster planarization.

ClusterArray< List< edge > > *	m_lcaEdges
	For each cluster c we store the edges with lca c.

int	m_numIndyBags

NodeArray< ClusterArray< int > * >	m_oactive

NodeArray< int >	m_oalevel

ClusterArray< List< node > > *	m_oalists
	For each cluster we store the outeractive vertices. In case you want to save space, set m_storeoalists to false.

ClusterArray< int > *	m_oanum
	Number of outer active vertices.

const bool	m_storeoalists
	If set to true (default) lists of outeractive vertices are stored.

Detailed Description

Definition at line 55 of file ClusterAnalysis.h.

Constructor & Destructor Documentation

◆ ClusterAnalysis() [1/2]

ogdf::ClusterAnalysis::ClusterAnalysis	(	const ClusterGraph &	C,
		bool	indyBags = `false`
	)

explicit

Constructor. Performs all analyses and in case indyBags is set to true, also computes a partition into independently solvable subproblems for cluster planarization (if applicable).

◆ ClusterAnalysis() [2/2]

ogdf::ClusterAnalysis::ClusterAnalysis	(	const ClusterGraph &	C,
		bool	oalists,
		bool	indyBags
	)

Additionally allows to forbid storing lists of outer active vertices.

◆ ~ClusterAnalysis()

ogdf::ClusterAnalysis::~ClusterAnalysis ( )

Member Function Documentation

◆ bagIndex()

int ogdf::ClusterAnalysis::bagIndex	(	node	v,
		cluster	c
	)

Returns bag index number for a vertex v in cluster c.

◆ cleanUp()

void ogdf::ClusterAnalysis::cleanUp ( )

private

Deletes dynamically allocated structures.

◆ computeBags()

void ogdf::ClusterAnalysis::computeBags ( )

protected

Compute bags per cluster and store result as vertex-bag index in m_bagIndex.

◆ computeIndyBags()

void ogdf::ClusterAnalysis::computeIndyBags ( )

protected

Compute independent bags per cluster and store result as vertex-indyBag index in m_indyBagNumber.

◆ indyBagIndex()

int ogdf::ClusterAnalysis::indyBagIndex ( node v )

Returns independent bag index number for a vertex v.

Precondition: indyBags parameter in constructor was set to true, i.e. indyBags were computed.

◆ indyBagRoot()

cluster ogdf::ClusterAnalysis::indyBagRoot ( int i )

Returns root cluster of independent bag. Note that this cluster either has direct vertex members or more than one child.

Parameters

i	is the independent bag number for which the root is returned.

◆ init()

void ogdf::ClusterAnalysis::init ( )

private

Initialize the structures, performs analyses.

◆ innerActive()

int ogdf::ClusterAnalysis::innerActive ( cluster c ) const

Returns number of inneractive vertices of cluster c.

◆ isInnerActive()

bool ogdf::ClusterAnalysis::isInnerActive	(	node	v,
		cluster	c
	)		const

◆ isOuterActive()

bool ogdf::ClusterAnalysis::isOuterActive	(	node	v,
		cluster	c
	)		const

Returns outer activity status for vertex v wrt cluster c.

Parameters

c	is the cluster for which vertex v's activity status is stored.
v	is the vertex for which the activity status is returned.

◆ lcaEdges()

List< edge > & ogdf::ClusterAnalysis::lcaEdges ( cluster c )

Returns list of edges for cluster c with lca c.

◆ minIALevel()

int ogdf::ClusterAnalysis::minIALevel ( node v ) const

inline

Returns the highest (smallest) level depth for which a vertex is inner active, only initialized if vertex is inner active.

Definition at line 83 of file ClusterAnalysis.h.

◆ minIOALevel()

int ogdf::ClusterAnalysis::minIOALevel ( node v ) const

inline

Returns the highest (smallest) level depth for which a vertex is inner or outer active.

Definition at line 79 of file ClusterAnalysis.h.

◆ minOALevel()

int ogdf::ClusterAnalysis::minOALevel ( node v ) const

inline

Returns the highest (smallest) level depth for which a vertex is outer active, only initialized if vertex is outer active.

Definition at line 87 of file ClusterAnalysis.h.

◆ numberOfBags()

int ogdf::ClusterAnalysis::numberOfBags ( cluster c ) const

Returns number of bags for cluster c.

◆ numberOfIndyBags()

int ogdf::ClusterAnalysis::numberOfIndyBags ( )

inline

Returns number of independent bags in clustergraph, -1 in case no independent bags were computed. Ascending consecutive numbers are assigned, starting from 0.

Definition at line 122 of file ClusterAnalysis.h.

◆ oaNodes()

List< node > & ogdf::ClusterAnalysis::oaNodes ( cluster c )

Returns list of outeractive vertices for cluster c. The result is only valid if lists are stored, i.e. m_storeoalists is true.

◆ outerActive()

int ogdf::ClusterAnalysis::outerActive ( cluster c ) const

Returns number of outeractive vertices of cluster c.

◆ partitionCluster()

void ogdf::ClusterAnalysis::partitionCluster	(	ListConstIterator< node > &	nodeIt,
		cluster	c,
		HashArray< int, List< node > > &	bagNodes,
		HashArray< int, bool > &	indyBag,
		Skiplist< int * > &	indexNumbers,
		Array< cluster > &	bagRoots
	)

private

Runs through a list of vertices (starting with the one nodeIT points to) which is expected to be a full list of cluster vertices in c. Depending on outer activity and bag index number of the vertices, independent bags are detected and a corresponding index is assigned accordingly for each vertex. If omitChildBags is set to true, already processed vertices are skipped.

Member Data Documentation

◆ DefaultIndex

const int ogdf::ClusterAnalysis::DefaultIndex

static

Definition at line 58 of file ClusterAnalysis.h.

◆ IsNotActiveBound

const int ogdf::ClusterAnalysis::IsNotActiveBound

static

Definition at line 57 of file ClusterAnalysis.h.

◆ m_bagindex

NodeArray<ClusterArray<int>*> ogdf::ClusterAnalysis::m_bagindex

private

We store the bag affiliation of the vertices for each cluster. A value of -1 indicates that the vertex is not a member of the cluster.

Definition at line 158 of file ClusterAnalysis.h.

◆ m_bags

ClusterArray<int>* ogdf::ClusterAnalysis::m_bags

private

Number of bags per cluster (stored even if vertex list is not stored)

Definition at line 165 of file ClusterAnalysis.h.

◆ m_C

const ClusterGraph* ogdf::ClusterAnalysis::m_C

private

Definition at line 149 of file ClusterAnalysis.h.

◆ m_iactive

NodeArray<ClusterArray<int>*> ogdf::ClusterAnalysis::m_iactive

private

Definition at line 153 of file ClusterAnalysis.h.

◆ m_ialevel

NodeArray<int> ogdf::ClusterAnalysis::m_ialevel

private

Definition at line 160 of file ClusterAnalysis.h.

◆ m_ianum

ClusterArray<int>* ogdf::ClusterAnalysis::m_ianum

private

Number of inner active vertices.

Definition at line 164 of file ClusterAnalysis.h.

◆ m_indyBagNumber

NodeArray<int> ogdf::ClusterAnalysis::m_indyBagNumber

private

Each independent bag has a different number.

Definition at line 177 of file ClusterAnalysis.h.

◆ m_indyBagRoots

cluster* ogdf::ClusterAnalysis::m_indyBagRoots

private

Definition at line 179 of file ClusterAnalysis.h.

◆ m_indyBags

const bool ogdf::ClusterAnalysis::m_indyBags

private

If true, a node partition into independent bags is computed which can be used for dividing the input instance into smaller problems wrt cluster planarization.

Definition at line 176 of file ClusterAnalysis.h.

◆ m_lcaEdges

ClusterArray<List<edge> >* ogdf::ClusterAnalysis::m_lcaEdges

private

For each cluster c we store the edges with lca c.

Definition at line 172 of file ClusterAnalysis.h.

◆ m_numIndyBags

int ogdf::ClusterAnalysis::m_numIndyBags

private

Definition at line 178 of file ClusterAnalysis.h.

◆ m_oactive

NodeArray<ClusterArray<int>*> ogdf::ClusterAnalysis::m_oactive

private

Definition at line 154 of file ClusterAnalysis.h.

◆ m_oalevel

NodeArray<int> ogdf::ClusterAnalysis::m_oalevel

private

Definition at line 161 of file ClusterAnalysis.h.

◆ m_oalists

ClusterArray<List<node> >* ogdf::ClusterAnalysis::m_oalists

private

For each cluster we store the outeractive vertices. In case you want to save space, set m_storeoalists to false.

Definition at line 169 of file ClusterAnalysis.h.

◆ m_oanum

ClusterArray<int>* ogdf::ClusterAnalysis::m_oanum

private

Number of outer active vertices.

Definition at line 163 of file ClusterAnalysis.h.

◆ m_storeoalists

const bool ogdf::ClusterAnalysis::m_storeoalists

private

If set to true (default) lists of outeractive vertices are stored.

Definition at line 170 of file ClusterAnalysis.h.

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

include/ogdf/cluster/ClusterAnalysis.h

OpenGraph DrawingFramework

Public Member Functions

Static Public Attributes

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ ClusterAnalysis() [1/2]

◆ ClusterAnalysis() [2/2]

◆ ~ClusterAnalysis()

Member Function Documentation

◆ bagIndex()

◆ cleanUp()

◆ computeBags()

◆ computeIndyBags()

◆ indyBagIndex()

◆ indyBagRoot()

◆ init()

◆ innerActive()

◆ isInnerActive()

◆ isOuterActive()

◆ lcaEdges()

◆ minIALevel()

◆ minIOALevel()

◆ minOALevel()

◆ numberOfBags()

◆ numberOfIndyBags()

◆ oaNodes()

◆ outerActive()

◆ partitionCluster()

Member Data Documentation

◆ DefaultIndex

◆ IsNotActiveBound

◆ m_bagindex

◆ m_bags

◆ m_C

◆ m_iactive

◆ m_ialevel

◆ m_ianum

◆ m_indyBagNumber

◆ m_indyBagRoots

◆ m_indyBags

◆ m_lcaEdges

◆ m_numIndyBags

◆ m_oactive

◆ m_oalevel

◆ m_oalists

◆ m_oanum

◆ m_storeoalists

Open
Graph Drawing
Framework