Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
CPlanarSubClusteredST.h
Go to the documentation of this file.
1
32#pragma once
33
37
38namespace ogdf {
39namespace cluster_planarity {
40
43public:
45
47 virtual void call(const ClusterGraph& CG, EdgeArray<bool>& inST);
50 virtual void call(const ClusterGraph& CG, EdgeArray<bool>& inST, EdgeArray<double>& weight);
51
52private:
54 void dfsBuildOriginalST(/*ClusterGraph& CG,*/
55 node v,
56 ClusterArray<EdgeArray<bool>>& treeEdges, //edges in repgraph
57 EdgeArray<bool>& inST, //original edges
58 NodeArray<bool>& visited);
59 //builds spanning tree on graph of node v in treeEdges
61
66 // insert nodes for all child clusters
68 for (auto child : c->children) {
69 node v = g.newNode();
70 m_cRepNode[child] = v;
71 }
72 // insert nodes for all node entries in c
74 for (auto u : c->nodes) {
75 node v = g.newNode();
76 m_vRepNode[u] = v;
77 }
78 }
79
82 for (edge e : CG.constGraph().edges) {
83 //insert representation in RepGraph[allocation cluster]
84 //defined by lowest common ancestor of end points
85 node u = e->source();
86 node v = e->target();
88 cluster allocCluster = CG.commonClusterLastAncestors(u, v, uAncestor, vAncestor);
90 //now derive the real ancestors (maybe the nodes themselves from
91 //the supplied clusters
92
93 //Case1: both nodes in same cluster => connect the nodes in the
94 //cluster representation graph
95 if (uAncestor == vAncestor) {
96 m_repEdge[e] = RepGraph[uAncestor]->newEdge(m_vRepNode[u], m_vRepNode[v]);
97 } else {
98 OGDF_ASSERT(uAncestor != CG.rootCluster() || vAncestor != CG.rootCluster());
99 //now only one node can be directly in rootcluster
100 //this case now seems to fall together with else else...
101 if (uAncestor == CG.rootCluster()) {
103 } else if (vAncestor == CG.rootCluster()) {
105 } else {
106 OGDF_ASSERT(allocCluster != nullptr);
107 //now create edge in lowest common cluster
108 node v1, v2;
109 v1 = ((uAncestor == nullptr) ? m_vRepNode[u] : m_cRepNode[uAncestor]);
110 v2 = ((vAncestor == nullptr) ? m_vRepNode[v] : m_cRepNode[vAncestor]);
111 m_repEdge[e] = RepGraph[allocCluster]->newEdge(v1, v2);
112 }
113 }
114 }
115 }
116
125
127 for (cluster c : CG.clusters) {
128 delete RepGraph[c];
129 }
130 }
131
134
135#if 0
137 EdgeArray<int> m_edgeStatus;
138#endif
139
147#if 0
148 int m_genDebug; //only for debugging
149#endif
150};
151
152}
153}
Declaration and implementation of ClusterArray class.
Derived class of GraphObserver providing additional functionality to handle clustered graphs.
Declaration and implementation of EdgeArray class.
Dynamic arrays indexed with clusters.
Representation of clusters in a clustered graph.
ListContainer< node, ClusterElement > nodes
The container containing the nodes lying (directly) in this cluster.
ListContainer< cluster, ClusterElement > children
The container containing the child clusters (children in the cluster tree) of this cluster.
Representation of clustered graphs.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
node newNode()
Creates a new node and returns it.
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
Constructs a c-planar subclustered spanning tree of the input by setting edgearray values.
void dfsBuildSpanningTree(node v, EdgeArray< bool > &treeEdges, NodeArray< bool > &visited)
void constructRepresentationGraphNodes(const ClusterGraph &CG, Graph &g, cluster c)
constructs for every cluster a graph representing its main structure (children & their connections) o...
EdgeArray< cluster > m_allocCluster
store the allocation cluster to avoid multiple computation
void deleteRepresentationGraphs(const ClusterGraph &CG, ClusterArray< Graph * > &RepGraph)
virtual void call(const ClusterGraph &CG, EdgeArray< bool > &inST)
sets values in inST according to membership in c-planar STGraph
void dfsBuildOriginalST(node v, ClusterArray< EdgeArray< bool > > &treeEdges, EdgeArray< bool > &inST, NodeArray< bool > &visited)
builds spanning tree on original graph out of repgraphs STs
EdgeArray< edge > m_repEdge
store the representation edge
virtual void call(const ClusterGraph &CG, EdgeArray< bool > &inST, EdgeArray< double > &weight)
sets values in inST according to membership in c-planar STGraph, computes minimum spanning tree accor...
void computeRepresentationGraphs(const ClusterGraph &CG, ClusterArray< Graph * > &RepGraph)
Computes representation graphs used for spanning tree computation.
void initialize(const ClusterGraph &CG)
Initializes some internally used members on CG.
void constructRepresentationGraphEdges(const ClusterGraph &CG, ClusterArray< Graph * > &RepGraph)
insert rep edges for all edges in clustergraph
ClusterArray< node > m_cRepNode
store the representation nodes for nodes and clusters
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.