# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
StarInserter.h
Go to the documentation of this file.
1
32#pragma once
33
36#include <ogdf/basic/comparer.h>
37
38#include <memory>
39#include <unordered_map>
40
41namespace ogdf {
42
43using PredecessorMap = std::unordered_map<node, std::unique_ptr<NodeArray<edge>>>;
44
57private:
59
61
63
70
72
74
75public:
92
107
108 // Go backwards from root until predecessor path diverges.
111 edge edgeToChild {nullptr};
112 node lca {nullptr};
113 while (lastDualNode1 == lastDualNode2) {
114 // Remember current lca.
116 lca = lastDualNode1;
117
118 // Go further down.
120 if (preds1[lastDualNode1] == nullptr || preds2[lastDualNode2] == nullptr) {
121 // If either node has no child in the insertion path tree,
122 // the lca cannot be lower.
123 break;
124 } else {
127 }
128 }
129
130 return lca;
131 }
132
139 int compare(const edge& e1, const edge& e2) const {
140 node w1 {m_graphCopy.copy(e1->opposite(m_origNode))};
141 node w2 {m_graphCopy.copy(e2->opposite(m_origNode))};
142 if (w1 == w2) {
143 return 0;
144 }
145
146 // Find lowest common ancestor in predecessor tree.
147 edge parentOfLCA {nullptr};
149
150 // w1 and w2 must have a common ancestor.
152
153 // Get the adjEntry of the primal edge of parentOfLCA which is incident
154 // to the face corresponding to lcaDualNode.
155 // This adjEntry marks the start of the cyclic order around lcaDualNode.
158 if (parentOfLCA == nullptr) {
160 // The lca is the root of the insertion path tree, hence it has no
161 // predecessor. Just use any adjEntry to start the cyclic order.
163 } else {
164 // The lca is not the root of the insertion path tree.
165 // Determine the correct adjEntry of the primal of its parent-edge.
169
171 if (embedding.rightFace(sourceAdj) == lcaFace) {
173 } else {
176 }
177 }
178
180 // starting at parent edge of lcaDualNode in the insertion path tree.
184 };
185
191 // First, if lcaFace has no pred in the insertion path of w1/w2,
192 // w1/w2 is adjacent to lcaFace.
193 // Check whether the node of the current adj is w1/w2.
194 if (pred1 == nullptr && primalNode == w1) {
195 return -1;
196 }
197 if (pred2 == nullptr && primalNode == w2) {
198 return 1;
199 }
200
201 // If w1/w2 is not adjacent to lcaFace, check whether the insertion
202 // path from lcaFace to the face adjacent to w1/w2 crosses the
203 // current edge.
204 edge dualEdge = m_dualGraph->dualEdge(primalEdge);
205 if (dualEdge == pred1) {
206 OGDF_ASSERT(dualEdge != pred2);
207 return -1;
208 }
209 if (dualEdge == pred2) {
210 OGDF_ASSERT(dualEdge != pred1);
211 return 1;
212 }
213 }
214
215 // Something went terribly wrong: The LCA of the insertion paths of w1
216 // and w2 is not actually part of the insertion paths of w1 and w2?
217 OGDF_ASSERT(false);
218 return 0;
219 }
220
222};
223
231private:
233
235
237
241
246
250
253 inline face oldPrimalFace(node dualNode) {
254 return (*m_newToOldFace)[m_dual->primalFace(dualNode)];
255 }
256
274
286
298
321
341
363
382
390
399 void updateMemberData(edge origEdge, bool startAtSource);
400
401public:
403 StarInserter() : m_combEmbedding {nullptr}, m_dual {nullptr} { }
404
406
410
413
416
418
430};
431
432}
Includes declaration of dual graph class.
Declaration of graph copy classes.
Definition Graph_d.h:79
Returns the cyclic successor in face.
Definition Graph_d.h:149
Combinatorial embeddings of planar graphs with modification functionality.
Combinatorial embeddings of planar graphs.
Returns the face to the right of adj, i.e., the face containing adj.
A dual graph including its combinatorial embedding of an embedded graph.
Definition DualGraph.h:56
const face & primalFace(node v) const
Returns the face in the embedding of the primal graph corresponding to v.
Definition DualGraph.h:163
const edge & primalEdge(edge e) const
Returns the edge in the primal graph corresponding to e.
Definition DualGraph.h:156
Embedding & getPrimalEmbedding() const
Returns a reference to the combinatorial embedding of the primal graph.
Definition DualGraph.h:136
const edge & dualEdge(edge e) const
Returns the edge in the dual graph corresponding to e.
Definition DualGraph.h:177
Dynamic arrays indexed with edges.
Definition EdgeArray.h:125
Class for the representation of edges.
Definition Graph_d.h:300
Orders edges such that they do not cross each other when embeddded as insertion paths.
node findLCAInInsertionPathTree(node w1, node w2, edge &parentOfLCA) const
Returns the lowest common ancestor of w1 and w2 in the insertion path tree given by m_predecessors.
const PredecessorMap & m_predecessors
Insertion path tree, given by several insertion paths.
node m_origNode
Common (original) node of compared edges.
int compare(const edge &e1, const edge &e2) const
Compares two edges as described for EdgeOrderComparer.
const DynamicDualGraph * m_dualGraph
Dual graph of m_graphCopy.
EdgeOrderComparer(node origNode, node rootDualNode, const PredecessorMap &predecessors, const GraphCopy &graphCopy, const DynamicDualGraph *dualGraph)
Creates a new EdgeOrderComparer.
node m_rootDualNode
Dual node, root of the insertion path tree.
const GraphCopy & m_graphCopy
Planarization.
Dynamic arrays indexed with faces of a combinatorial embedding.
Definition FaceArray.h:126
Faces in a combinatorial embedding.
Copies of graphs supporting edge splitting.
Definition GraphCopy.h:254
node copy(node v) const
Returns the node in the graph copy corresponding to v.
Definition GraphCopy.h:338
Doubly linked lists (maintaining the length of the list).
Definition List.h:1435
Dynamic arrays indexed with nodes.
Definition NodeArray.h:125
Class for the representation of nodes.
Definition Graph_d.h:177
Singly linked lists (maintaining the length of the list).
Definition SList.h:833
Inserts a star (a vertex and its incident edges) optimally into an embedding.
EdgeArray< edge > * m_edgeInChainToSplit
Maps each edge e originally contained in m_graphCopy to the edge in the same chain which should be sp...
~StarInserter()
Destructor.
Returns the adjEntry of primalNode whose right face is incident to primalEdge.
void transferCrossedEdges(const List< adjEntry > &crossedEdges, SList< adjEntry > &finalCrossedEdges, bool startAtSource)
Transfers the adjEntries from the List crossedEdges to the SList finalCrossedEdges such that they can...
CombinatorialEmbedding * m_combEmbedding
Embedding of m_graphCopy.
virtual void call(GraphCopy &graphCopy, DynamicDualGraph &dualGraph, node origNode, const EdgeArray< int > *pCostOrig)
Inserts the node origNode and its incident edges into graphCopy.
StarInserter()
Creates a StarInserter instance with default settings.
void updateMemberData(edge origEdge, bool startAtSource)
Update member variables, in particular m_newToOldFace and m_edgeInChainToSplit, after an edge was ins...
FaceArray< face > * m_newToOldFace
Maps new faces (created after the insertion of edge paths) to old (non-split) faces....
GraphCopy * m_graphCopy
Planarization.
void makePredsConsistent(node origNode, node optimalDualNode, PredecessorMap &predecessors)
Modify the insertion paths predecessors such that they do not cross each other anymore,...
Returns the adjEntry of primalEdgeToSplit whose left face corresponds to leftDualNode.
node getOptimalDualNode(node origNode, const EdgeArray< int > *pCostOrig, PredecessorMap &predecessors)
Computes the optimal dual node to insert origNode and the insertion paths of its incident edges.
EdgeArray< edge > * m_originalEdge
Maps the parts of a chain in m_graphCopy to the respective copy edge contained in m_graphCopy before ...
edge collectAdjEntries(node w, node insertedNode, node optimalDualNode, const PredecessorMap &predecessors, List< adjEntry > &crossedEdges)
Collects adjEntries which can be passed to GraphCopy::insertEdgePathEmbedded to embed the edge insert...
DynamicDualGraph * m_dual
Dual graph of m_combEmbedding.
StarInserter & operator=(const StarInserter &inserter)
Assignment operator, copies option settings only.
Returns the adjEntry of primalNode whose right face corresponds to rightDualNode (if otherPrimaNode i...
void initMemberData(GraphCopy &graphCopy, DynamicDualGraph &dualGraph)
Initialize all member variables.
face oldPrimalFace(node dualNode)
Returns the primal face of dualNode which existed before any new edges were inserted.
StarInserter(const StarInserter &inserter)
Creates a StarInserter instance with the same settings as inserter.
Declarations for Comparer objects.
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition config.h:101
#define OGDF_AUGMENT_COMPARER(type)
Add this macro to your class to turn it into a full comparer.
Definition comparer.h:179
#define OGDF_ASSERT(expr)