Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
ClusterAnalysis.h
Go to the documentation of this file.
1
40#pragma once
41
43#include <ogdf/basic/Skiplist.h>
45
46namespace ogdf {
47
48/***
49 * @ingroup ga-cplanarity
50 *
51 * Although most parts of the code are written with efficiency in mind,
52 * this class is meant to be used in a static one-time analysis way,
53 * not for dynamic checks over and over again.
54 */
56public:
57 static const int IsNotActiveBound;
58 static const int DefaultIndex; // Vertex index for independent bags, used to detect processing status.
59
63 explicit ClusterAnalysis(const ClusterGraph& C, bool indyBags = false);
67
68 // Quantitative
70 // @param c is the cluster for which the active vertices are counted
71 int outerActive(cluster c) const;
72
74 // @param c is the cluster for which the active vertices are counted
75 int innerActive(cluster c) const;
76
79 int minIOALevel(node v) const { return min(minIALevel(v), minOALevel(v)); }
80
83 int minIALevel(node v) const { return m_ialevel[v]; }
84
87 int minOALevel(node v) const { return m_oalevel[v]; }
88
89 // Qualitative
91
95 bool isOuterActive(node v, cluster c) const;
96 bool isInnerActive(node v, cluster c) const;
97
100
104
107
109 int numberOfBags(cluster c) const;
110
111#if 0
112 //TODO
113 void reInit(const ClusterGraph &C);
114#endif
115
119
123
128
129protected:
133
137
138private:
147 void init();
148 void cleanUp();
150 // we keep data structures to save inner/outer activity status
151 // instead of computing them on the fly when needed
152 // keep number of activity defining adjacent edges
155
159
162
166
170 const bool m_storeoalists;
171
173
176 const bool m_indyBags;
178 int m_numIndyBags; //<! Number of independent bags in clustergraph
179 cluster* m_indyBagRoots; //<! Root clusters of independent bags (only when computed).
180};
181}
Derived class of GraphObserver providing additional functionality to handle clustered graphs.
Declaration and implementation of HashArray class.
Declaration of class Skiplist.
The parameterized class Array implements dynamic arrays of type E.
Definition Array.h:214
List< node > & oaNodes(cluster c)
Returns list of outeractive vertices for cluster c. The result is only valid if lists are stored,...
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 fu...
ClusterAnalysis(const ClusterGraph &C, bool indyBags=false)
Constructor. Performs all analyses and in case indyBags is set to true, also computes a partition int...
void computeIndyBags()
Compute independent bags per cluster and store result as vertex-indyBag index in m_indyBagNumber.
const bool m_storeoalists
If set to true (default) lists of outeractive vertices are stored.
void cleanUp()
Deletes dynamically allocated structures.
NodeArray< ClusterArray< int > * > m_iactive
int innerActive(cluster c) const
Returns number of inneractive vertices of cluster c.
NodeArray< int > m_ialevel
static const int DefaultIndex
ClusterArray< List< edge > > * m_lcaEdges
For each cluster c we store the edges with lca c.
int minIALevel(node v) const
Returns the highest (smallest) level depth for which a vertex is inner active, only initialized if ve...
NodeArray< int > m_indyBagNumber
Each independent bag has a different number.
const ClusterGraph * m_C
int minOALevel(node v) const
Returns the highest (smallest) level depth for which a vertex is outer active, only initialized if ve...
bool isOuterActive(node v, cluster c) const
Returns outer activity status for vertex v wrt cluster c.
static const int IsNotActiveBound
int numberOfBags(cluster c) const
Returns number of bags for cluster c.
ClusterArray< List< node > > * m_oalists
For each cluster we store the outeractive vertices. In case you want to save space,...
ClusterArray< int > * m_bags
Number of bags per cluster (stored even if vertex list is not stored)
NodeArray< int > m_oalevel
const bool m_indyBags
If true, a node partition into independent bags is computed which can be used for dividing the input ...
int indyBagIndex(node v)
Returns independent bag index number for a vertex v.
bool isInnerActive(node v, cluster c) const
int outerActive(cluster c) const
Returns number of outeractive vertices of cluster c.
int bagIndex(node v, cluster c)
Returns bag index number for a vertex v in cluster c.
cluster indyBagRoot(int i)
Returns root cluster of independent bag. Note that this cluster either has direct vertex members or m...
void init()
Initialize the structures, performs analyses.
NodeArray< ClusterArray< int > * > m_bagindex
We store the bag affiliation of the vertices for each cluster. A value of -1 indicates that the verte...
ClusterArray< int > * m_oanum
Number of outer active vertices.
NodeArray< ClusterArray< int > * > m_oactive
void computeBags()
Compute bags per cluster and store result as vertex-bag index in m_bagIndex.
ClusterAnalysis(const ClusterGraph &C, bool oalists, bool indyBags)
Additionally allows to forbid storing lists of outer active vertices.
ClusterArray< int > * m_ianum
Number of inner active vertices.
int minIOALevel(node v) const
Returns the highest (smallest) level depth for which a vertex is inner or outer active.
int numberOfIndyBags()
Returns number of independent bags in clustergraph, -1 in case no independent bags were computed....
List< edge > & lcaEdges(cluster c)
Returns list of edges for cluster c with lca c.
Dynamic arrays indexed with clusters.
Representation of clusters in a clustered graph.
Representation of clustered graphs.
Indexed arrays using hashing for element access.
Definition HashArray.h:93
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Encapsulates a pointer to a list element.
Definition List.h:103
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
A randomized skiplist.
Definition Skiplist.h:52
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.