Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
CconnectClusterPlanarEmbed.h
Go to the documentation of this file.
1
34#pragma once
35
39
40namespace ogdf {
41
43
47public:
48 enum class ErrorCode {
49 none = 0,
50 nonConnected = 1,
51 nonCConnected = 2,
52 nonPlanar = 3,
53 nonCPlanar = 4
54 };
55
56 ErrorCode errCode() { return m_errorCode; }
57
60
63
65 virtual bool embed(ClusterGraph& C, Graph& G);
66
67private:
69
70 bool planarityTest(ClusterGraph& C, const cluster act, Graph& G);
71
73
75
79
82
84
86
87
90
92
94
96
99
100 // Stores for every cluster the PQTree corresponding
101 // to the biconnected component containing the outgoing
102 // edges of the cluster.
104
105 //save errorcode for postprocessing if not c-planar
107
114
118
119 ClusterGraph* m_instance; //The graph that has to be embedded
120
121
122 // Stores for every cluster the (partial) embedding of the
123 // biconnected components not having outgoing
124 // edges of the cluster.
125 // The NodeArrays are associated with the subgraphs.
126 // The ClusterArray is associtated with the original graph.
128
129 // Stores for every cluster the subgraph constructed to test
130 // the planarity of the cluster
131 // The ClusterArray is associated with the original graph.
133
134 // Marks for every subgraph of a cluster the nodes that are
135 // hubs as true.
136 // The NodeArrays are associated with the subgraphs.
137 // The ClusterArray is associated with the original graph.
139
140
141 // Stores for every node of every subgraph of a cluster
142 // if this node belongs to a wheel graph, corresponding to
143 // a child cluster
144 // The NodeArrays are associated with the subgraphs.
145 // The ClusterArray is associated with the original graph.
147
148
149 // Stores for every mode of every subgraph of a cluster its
150 // corresponding node on the original graph G, if there exists one.
152
153
156
157 // When constructing a wheel graph, we store here for
158 // every wheel graph node the corresponding cluster
159 // Array is associated with the cluster graph copy.
161
162 // Stores for every node in the current graph, if
163 // it is a hub.
164 // Array is associated with the cluster graph copy.
166
167
168 // Stores for every cluster of Ccopy the corresponding cluster
169 // in the original graph. A key variable, since we track
170 // all information via the original clusters.
172
173 // Needed to construct the ClusterArray m_clusterTableCopy2Orig.
175
176 // Stores for every subgraph the super sink of the subgraph.
178
179
180 // Stores for every node in Gcopy its corresponding node
181 // in the original graph unless the node belongs to
182 // a wheel graph.
183 // The NodeArray is associated with Gcopy.
185
186 // Needed to construct the NodeArray m_nodeTableCopy2Orig.
188
189
192
193 // Stores for every original cluster all information on
194 // the PQ-Tree that is necessary to construct the embedding.
196
197 // Stores the clusters in calling order of the testing algorithm
198 // The stack stores the clusters of the original graph.
199 // Needed for recursive embed.
201
202 // Is true for every original cluster, if the cluster does not
203 // have a correspondand in the copy of the cluster graph.
204 // This is the case if:
205 // a. cluster is son of root cluster and does have exactly one
206 // childcluster and no nodes;
207 // b. recursive version of a;
208 // c. cluster does have no child clusters and no nodes;
209 // d. recursive version of c.
211
213};
214
215}
Declaration and implementation of ClusterArray class.
Declaration of ClusterPQContainer.
Declaration of the class EmbedPQTree.
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition ArrayBuffer.h:56
C-planarity test and embedding by Cohen, Feng and Eades.
void copyEmbedding(ClusterGraph &Ccopy, Graph &Gcopy, ClusterGraph &C, Graph &G)
ClusterArray< EdgeArray< ArrayBuffer< edge > * > * > m_clusterOutgoingEdgesAnker
bool preparation(Graph &subGraph, const cluster origCluster, node superSink)
EdgeArray< ListPure< edge > > m_parallelEdges
bool doEmbed(Graph *biconComp, NodeArray< int > &numbering, const cluster origCluster, node superSink, Graph &subGraph, EdgeArray< edge > &tableEdgesBiComp2SubGraph, EdgeArray< edge > &tableEdgesSubGraph2BiComp, NodeArray< node > &tableNodesBiComp2SubGraph)
void hubControl(Graph &G, NodeArray< bool > &hubs)
virtual bool embed(ClusterGraph &C, Graph &G)
Tests if a clustered graph (C, G) is C-planar and embeds it.
void constructWheelGraph(ClusterGraph &C, Graph &G, cluster &parent, cluster &origCl, EmbedPQTree *T, EdgeArray< node > &outgoingTable, node superSink)
void nonPlanarCleanup(ClusterGraph &Ccopy, Graph &Gcopy)
EdgeArray< ArrayBuffer< edge > * > m_outgoingEdgesAnker
ClusterArray< NodeArray< bool > * > m_clusterSubgraphHubs
bool planarityTest(ClusterGraph &C, const cluster act, Graph &G)
ClusterArray< cluster_planarity::ClusterPQContainer > m_clusterPQContainer
ClusterArray< EmbedPQTree * > m_clusterPQTree
ClusterArray< NodeArray< SListPure< adjEntry > > * > m_clusterEmbedding
bool preProcess(ClusterGraph &Ccopy, Graph &Gcopy)
CconnectClusterPlanarEmbed()
Constructor.
ClusterArray< ClusterGraph * > m_clusterClusterGraph
ClusterArray< NodeArray< node > * > m_clusterNodeTableNew2Orig
void entireEmbed(Graph &biconComp, NodeArray< SListPure< adjEntry > > &entireEmbedding, NodeArray< SListIterator< adjEntry > > &adjMarker, NodeArray< bool > &mark, node v)
void recursiveEmbed(ClusterGraph &Ccopy, Graph &Gcopy)
virtual ~CconnectClusterPlanarEmbed()
Destructor.
ClusterArray< ClusterArray< cluster > * > m_clusterClusterTableOrig2New
ClusterArray< NodeArray< cluster > * > m_clusterSubgraphWheelGraph
Dynamic arrays indexed with clusters.
Representation of clusters in a clustered graph.
Representation of clustered graphs.
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Data type for general directed graphs (adjacency list representation).
Definition Graph_d.h:521
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Encapsulates a pointer to an ogdf::SList element.
Definition SList.h:92
Singly linked lists.
Definition SList.h:179
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.