Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ogdf::ClusterAnalysis Class Reference

#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). More...
 
 ClusterAnalysis (const ClusterGraph &C, bool oalists, bool indyBags)
 Additionally allows to forbid storing lists of outer active vertices. More...
 
 ~ClusterAnalysis ()
 
int bagIndex (node v, cluster c)
 Returns bag index number for a vertex v in cluster c. More...
 
int indyBagIndex (node v)
 Returns independent bag index number for a vertex v. More...
 
cluster indyBagRoot (int i)
 Returns root cluster of independent bag. Note that this cluster either has direct vertex members or more than one child. More...
 
int innerActive (cluster c) const
 Returns number of inneractive vertices of cluster c. More...
 
bool isInnerActive (node v, cluster c) const
 
bool isOuterActive (node v, cluster c) const
 Returns outer activity status for vertex v wrt cluster c. More...
 
List< edge > & lcaEdges (cluster c)
 Returns list of edges for cluster c with lca c. More...
 
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. More...
 
int minIOALevel (node v) const
 Returns the highest (smallest) level depth for which a vertex is inner or outer active. More...
 
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. More...
 
int numberOfBags (cluster c) const
 Returns number of bags for cluster c. More...
 
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. More...
 
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. More...
 
int outerActive (cluster c) const
 Returns number of outeractive vertices of cluster c. More...
 

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. More...
 
void computeIndyBags ()
 Compute independent bags per cluster and store result as vertex-indyBag index in m_indyBagNumber. More...
 

Private Member Functions

void cleanUp ()
 Deletes dynamically allocated structures. More...
 
void init ()
 Initialize the structures, performs analyses. More...
 
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. More...
 

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. More...
 
ClusterArray< int > * m_bags
 Number of bags per cluster (stored even if vertex list is not stored) More...
 
const ClusterGraphm_C
 
NodeArray< ClusterArray< int > * > m_iactive
 
NodeArray< int > m_ialevel
 
ClusterArray< int > * m_ianum
 Number of inner active vertices. More...
 
NodeArray< int > m_indyBagNumber
 Each independent bag has a different number. More...
 
clusterm_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. More...
 
ClusterArray< List< edge > > * m_lcaEdges
 For each cluster c we store the edges with lca c. More...
 
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. More...
 
ClusterArray< int > * m_oanum
 Number of outer active vertices. More...
 
const bool m_storeoalists
 If set to true (default) lists of outeractive vertices are stored. More...
 

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
iis 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
cis the cluster for which vertex v's activity status is stored.
vis 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 91 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 86 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 96 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 133 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 65 of file ClusterAnalysis.h.

◆ IsNotActiveBound

const int ogdf::ClusterAnalysis::IsNotActiveBound
static

Definition at line 64 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 169 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 176 of file ClusterAnalysis.h.

◆ m_C

const ClusterGraph* ogdf::ClusterAnalysis::m_C
private

Definition at line 160 of file ClusterAnalysis.h.

◆ m_iactive

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

Definition at line 164 of file ClusterAnalysis.h.

◆ m_ialevel

NodeArray<int> ogdf::ClusterAnalysis::m_ialevel
private

Definition at line 171 of file ClusterAnalysis.h.

◆ m_ianum

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

Number of inner active vertices.

Definition at line 175 of file ClusterAnalysis.h.

◆ m_indyBagNumber

NodeArray<int> ogdf::ClusterAnalysis::m_indyBagNumber
private

Each independent bag has a different number.

Definition at line 188 of file ClusterAnalysis.h.

◆ m_indyBagRoots

cluster* ogdf::ClusterAnalysis::m_indyBagRoots
private

Definition at line 190 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 187 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 183 of file ClusterAnalysis.h.

◆ m_numIndyBags

int ogdf::ClusterAnalysis::m_numIndyBags
private

Definition at line 189 of file ClusterAnalysis.h.

◆ m_oactive

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

Definition at line 165 of file ClusterAnalysis.h.

◆ m_oalevel

NodeArray<int> ogdf::ClusterAnalysis::m_oalevel
private

Definition at line 172 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 180 of file ClusterAnalysis.h.

◆ m_oanum

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

Number of outer active vertices.

Definition at line 174 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 181 of file ClusterAnalysis.h.


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