Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

DualGraph.h
Go to the documentation of this file.
1 
32 #pragma once
33 
35 #include <ogdf/basic/NodeArray.h>
36 #include <ogdf/basic/EdgeArray.h>
37 #include <ogdf/basic/FaceArray.h>
38 
39 namespace ogdf {
40 
41 template<bool isConst> class DualGraphBase;
42 
44 
46 
54 template<bool isConst>
56 {
57 public:
58  using Embedding = typename std::conditional<isConst,
60 
62  explicit DualGraphBase(Embedding &CE) : m_primalEmbedding(CE)
63  {
64  const Graph &primalGraph = CE.getGraph();
65  init(*(new Graph));
66  Graph &dualGraph = getGraph();
67 
68  m_dualNode.init(CE);
69  m_dualEdge.init(primalGraph);
70  m_dualFace.init(primalGraph);
71 #ifdef OGDF_DEBUG
72  m_primalNode.init(*this, nullptr);
73 #else
74  m_primalNode.init(*this);
75 #endif
76  m_primalFace.init(dualGraph);
77  m_primalEdge.init(dualGraph);
78 
79  // create dual nodes
80  for(face f : CE.faces)
81  {
82  node vDual = dualGraph.newNode();
83  m_dualNode[f] = vDual;
84  m_primalFace[vDual] = f;
85  }
86 
87  // create dual edges
88  for(edge e : primalGraph.edges)
89  {
90  adjEntry aE = e->adjSource();
91  node vDualSource = m_dualNode[CE.rightFace(aE)];
92  node vDualTarget = m_dualNode[CE.leftFace(aE)];
93  edge eDual = dualGraph.newEdge(vDualSource, vDualTarget);
94  m_primalEdge[eDual] = e;
95  m_dualEdge[e] = eDual;
96  }
97 
98  // sort adjElements of every dual node corresponding to dual embedding
99  for(face f : CE.faces)
100  {
101  node vDual = m_dualNode[f];
102  List<adjEntry> newOrder;
103 
104  for(adjEntry adj : f->entries) {
105  edge e = adj->theEdge();
106  edge eDual = m_dualEdge[e];
107  bool isSource = adj == e->adjSource();
108  adjEntry adjDual = isSource ?
109  eDual->adjSource() : eDual->adjTarget();
110  newOrder.pushBack(adjDual);
111  }
112 
113  dualGraph.sort(vDual, newOrder);
114  }
115 
116  // calculate dual faces and links to corresponding primal nodes
117  computeFaces();
118 
119  for(node v : primalGraph.nodes)
120  {
121  edge ePrimal = v->firstAdj()->theEdge();
122  edge eDual = m_dualEdge[ePrimal];
123  face fDual = rightFace(eDual->adjSource());
124  if(ePrimal->source()==v)
125  fDual = leftFace(eDual->adjSource());
126 
127  OGDF_ASSERT(m_primalNode[fDual] == nullptr);
128 
129  m_dualFace[v] = fDual;
130  m_primalNode[fDual] = v;
131  }
132  }
133 
136  {
137  clear();
138  delete m_cpGraph;
139  }
140 
142  Embedding &getPrimalEmbedding() const { return m_primalEmbedding; }
143 
145  const Graph &getPrimalGraph() const { return m_primalEmbedding.getGraph(); }
146 
149 
151 
155  const node &primalNode(face f) const { return m_primalNode[f]; }
156 
158 
162  const edge &primalEdge(edge e) const { return m_primalEdge[e]; }
163 
165 
169  const face &primalFace(node v) const { return m_primalFace[v]; }
170 
172 
176  const node &dualNode(face f) const { return m_dualNode[f]; }
177 
179 
183  const edge &dualEdge(edge e) const { return m_dualEdge[e]; }
184 
186 
190  const face &dualFace(node v) const { return m_dualFace[v]; }
191 
195 
199  edge oldDualEdge {m_dualEdge[e]};
200 
201 #ifdef OGDF_DEBUG
202  node oldPrimalNode {e->target()};
203  face oldDualFace {rightFace(oldDualEdge->adjSource())};
204 #endif
205 
206  // Create new edge in the primal graph.
207  edge newPrimalEdge {m_primalEmbedding.split(e)};
208  node newPrimalNode {newPrimalEdge->source()};
209 
210  // Create new edge in the dual graph.
212  oldDualEdge->adjSource(),
213  oldDualEdge->adjSource()->faceCycleSucc())};
214  face newDualFace {leftFace(newDualEdge->adjSource())};
215 
216  // Update node and edge mappings.
217  m_dualEdge[newPrimalEdge] = newDualEdge;
218  m_primalEdge[newDualEdge] = newPrimalEdge;
219 
220  m_dualFace[newPrimalNode] = newDualFace;
221  m_primalNode[newDualFace] = newPrimalNode;
222 
223  OGDF_ASSERT(m_dualFace[oldPrimalNode] == oldDualFace);
224  OGDF_ASSERT(m_primalNode[oldDualFace] == oldPrimalNode);
225 
226 #ifdef OGDF_HEAVY_DEBUG
227  consistencyCheck();
228 #endif
229 
230  return newPrimalEdge;
231  }
232 
235  void unsplitPrimal(edge eIn, edge eOut) {
236  // Join faces in the dual graph, unsplit edge in the primal graph.
237  face oldDualFace {CombinatorialEmbedding::joinFaces(m_dualEdge[eOut])};
238  m_primalEmbedding.unsplit(eIn, eOut);
239  node oldPrimalNode {eIn->target()};
240 
241  // Update node and edge mappings.
242  m_dualFace[oldPrimalNode] = oldDualFace;
243  m_primalNode[oldDualFace] = oldPrimalNode;
244  OGDF_ASSERT(m_primalEdge[m_dualEdge[eIn]] == eIn);
245 
246 #ifdef OGDF_HEAVY_DEBUG
247  consistencyCheck();
248 #endif
249  }
250 
253  node splitNodePrimal(adjEntry adjStartLeft, adjEntry adjStartRight) {
254  node oldPrimalNode {adjStartLeft->theNode()};
255  face oldDualFace {m_dualFace[oldPrimalNode]};
256 
257  // Split node in the primal graph.
258  node newPrimalNode {m_primalEmbedding.splitNode(adjStartLeft, adjStartRight)};
259  edge newPrimalEdge {adjStartLeft->cyclicPred()->theEdge()};
260 
261  // Split face in the dual graph.
262  adjEntry dualAdjLeft {dualAdj(adjStartLeft, true)};
263  adjEntry dualAdjRight {dualAdj(adjStartRight, true)};
264  OGDF_ASSERT(dualAdjLeft->theNode() ==
265  m_dualNode[m_primalEmbedding.leftFace(adjStartLeft)]);
266  OGDF_ASSERT(dualAdjRight->theNode() ==
267  m_dualNode[m_primalEmbedding.leftFace(adjStartRight)]);
268  edge newDualEdge {CombinatorialEmbedding::splitFace(dualAdjLeft, dualAdjRight)};
269  face newDualFace {leftFace(newDualEdge->adjSource())};
270 
271  // Update node and edge mappings.
272  m_dualEdge[newPrimalEdge] = newDualEdge;
273  m_primalEdge[newDualEdge] = newPrimalEdge;
274 
275  m_dualFace[newPrimalNode] = oldDualFace;
276  m_primalNode[oldDualFace] = newPrimalNode;
277 
278  m_dualFace[oldPrimalNode] = newDualFace;
279  m_primalNode[newDualFace] = oldPrimalNode;
280 
281 #ifdef OGDF_HEAVY_DEBUG
282  consistencyCheck();
283 #endif
284 
285  return newPrimalNode;
286  }
287 
290  node contractPrimal(edge e, bool keepSelfLoops = false) {
291  edge dualEdge {m_dualEdge[e]};
292 
293  // Contract e in in the primal graph, join faces in the dual graph.
294  // TODO Joining faces in the dual graph currently always acts as if
295  // keepSelfLoops is true.
296  node newPrimalNode {m_primalEmbedding.contract(e, keepSelfLoops)};
297  face newDualFace {CombinatorialEmbedding::joinFaces(dualEdge)};
298 
299  // Update node and edge mappings.
300  m_dualFace[newPrimalNode] = newDualFace;
301  m_primalNode[newDualFace] = newPrimalNode;
302 
303 #ifdef OGDF_HEAVY_DEBUG
304  consistencyCheck();
305 #endif
306 
307  return newPrimalNode;
308  }
309 
312  edge splitFacePrimal(adjEntry adjSrc, adjEntry adjTgt, bool sourceAfter = false) {
313 #ifdef OGDF_DEBUG
314  face oldPrimalFace {m_primalEmbedding.rightFace(adjSrc)};
315  node oldDualNode {m_dualNode[oldPrimalFace]};
316 #endif
317 
318  // Create new edge in the primal graph.
319  edge newPrimalEdge {m_primalEmbedding.splitFace(adjSrc, adjTgt, sourceAfter)};
320  face newPrimalFace {m_primalEmbedding.leftFace(newPrimalEdge->adjSource())};
321 
322  // Create new edge in the dual graph.
323  adjEntry leftAdj {dualAdj(adjTgt)};
324  adjEntry rightAdj {dualAdj(adjSrc)};
325  OGDF_ASSERT(leftAdj->theNode() == oldDualNode);
326  OGDF_ASSERT(rightAdj->theNode() == oldDualNode);
327 
328  node newDualNode {CombinatorialEmbedding::splitNode(leftAdj, rightAdj)};
329  edge newDualEdge {leftAdj->cyclicPred()->theEdge()};
330 
331  // Update node and edge mappings.
332  m_dualEdge[newPrimalEdge] = newDualEdge;
333  m_primalEdge[newDualEdge] = newPrimalEdge;
334 
335  m_dualNode[newPrimalFace] = newDualNode;
336  m_primalFace[newDualNode] = newPrimalFace;
337 
338  OGDF_ASSERT(m_dualNode[oldPrimalFace] == oldDualNode);
339  OGDF_ASSERT(m_primalFace[oldDualNode] == oldPrimalFace);
340 
341 #ifdef OGDF_HEAVY_DEBUG
342  consistencyCheck();
343 #endif
344 
345  return newPrimalEdge;
346  }
347 
351  return addEdgeToIsolatedNodePrimal(adjTgt, v, false);
352  }
353 
357  return addEdgeToIsolatedNodePrimal(adjSrc, v, true);
358  }
359 
363  edge eDual {m_dualEdge[e]};
364 
365  // Join faces in the primal graph, contract edges in the dual graph.
366  face oldPrimalFace {m_primalEmbedding.joinFaces(e)};
367  node oldDualNode {CombinatorialEmbedding::contract(eDual, true)};
368 
369  m_primalFace[oldDualNode] = oldPrimalFace;
370  m_dualNode[oldPrimalFace] = oldDualNode;
371 
372 #ifdef OGDF_HEAVY_DEBUG
373  consistencyCheck();
374 #endif
375 
376  return oldPrimalFace;
377  }
378 
382  OGDF_ASSERT(v->degree() == 1);
383 
384  edge primalEdge {v->firstAdj()->theEdge()};
385  edge dualEdge {m_dualEdge[primalEdge]};
386 #ifdef OGDF_DEBUG
387  node otherPrimalNode {primalEdge->opposite(v)};
388 #endif
389 
390  m_primalEmbedding.removeDeg1(v);
391 #ifdef OGDF_DEBUG
392  face newDualFace =
393 #endif
395 
396  OGDF_ASSERT(m_dualFace[otherPrimalNode] == newDualFace);
397  OGDF_ASSERT(m_primalNode[newDualFace] == otherPrimalNode);
398 
399 #ifdef OGDF_HEAVY_DEBUG
400  consistencyCheck();
401 #endif
402  }
403 
407  m_primalEmbedding.reverseEdge(e);
409 
410 #ifdef OGDF_HEAVY_DEBUG
411  consistencyCheck();
412 #endif
413  }
414 
415 #ifdef OGDF_DEBUG
416  void consistencyCheck() const {
418  Embedding::consistencyCheck();
419 
420  const Graph &primalGraph {m_primalEmbedding.getGraph()};
421  const Graph &dualGraph {getGraph()};
422  OGDF_ASSERT(primalGraph.numberOfNodes() == numberOfFaces());
423  OGDF_ASSERT(primalGraph.numberOfEdges() == dualGraph.numberOfEdges());
424  OGDF_ASSERT(m_primalEmbedding.numberOfFaces() == dualGraph.numberOfNodes());
425 
426  for (node vDual : dualGraph.nodes) {
427  OGDF_ASSERT(m_dualNode[m_primalFace[vDual]] == vDual);
428  }
429  for (edge eDual : dualGraph.edges) {
430  OGDF_ASSERT(m_dualEdge[m_primalEdge[eDual]] == eDual);
431 
432  // A dual edge leads from the right to the left face of its primal edge.
433  OGDF_ASSERT(leftFace(eDual->adjSource()) ==
434  m_dualFace[m_primalEdge[eDual]->source()]);
435  OGDF_ASSERT(rightFace(eDual->adjSource()) ==
436  m_dualFace[m_primalEdge[eDual]->target()]);
437  }
438  for (face fDual : Embedding::faces) {
439  OGDF_ASSERT(m_dualFace[m_primalNode[fDual]] == fDual);
440  }
441  }
442 #endif
443 
444 protected:
452 
453 private:
457 #ifdef OGDF_DEBUG
458  face oldPrimalFace {m_primalEmbedding.rightFace(adj)};
459  node oldDualNode {m_dualNode[oldPrimalFace]};
460 #endif
461  node oldPrimalNode {adj->theNode()};
462  face oldDualFace {m_dualFace[oldPrimalNode]};
463 
464  adjEntry primalAdj {adj->faceCyclePred()};
465  edge newPrimalEdge {adjSrc ?
466  m_primalEmbedding.addEdgeToIsolatedNode(adj, v) :
467  m_primalEmbedding.addEdgeToIsolatedNode(v, adj)
468  };
469  // If the new primal edge goes from v to adj, the new dual self-loop has to
470  // go from its right to its left side. Hence, we pass !adjSrc to splitFace().
471  adjEntry dualAdjEntry {dualAdj(primalAdj)};
472  OGDF_ASSERT(dualAdjEntry->theNode() == oldDualNode);
473  edge newDualEdge {CombinatorialEmbedding::splitFace(dualAdjEntry, dualAdjEntry, !adjSrc)};
474  face newDualFace {leftFace(newDualEdge->adjSource())};
475 
476  // Update node and edge mappings.
477  m_dualEdge[newPrimalEdge] = newDualEdge;
478  m_primalEdge[newDualEdge] = newPrimalEdge;
479 
480  if (adjSrc) {
481  m_primalNode[oldDualFace] = v;
482  m_dualFace[v] = oldDualFace;
483 
484  m_primalNode[newDualFace] = oldPrimalNode;
485  m_dualFace[oldPrimalNode] = newDualFace;
486  } else {
487  m_primalNode[newDualFace] = v;
488  m_dualFace[v] = newDualFace;
489 
490  OGDF_ASSERT(m_primalNode[oldDualFace] == oldPrimalNode);
491  OGDF_ASSERT(m_dualFace[oldPrimalNode] == oldDualFace);
492  }
493 
494 #ifdef OGDF_HEAVY_DEBUG
495  consistencyCheck();
496 #endif
497 
498  return newPrimalEdge;
499  }
500 
503  inline adjEntry dualAdj(adjEntry primalAdj, bool reverse = false) {
504  return primalAdj->isSource() != reverse ?
505  m_dualEdge[primalAdj->theEdge()]->adjSource() :
506  m_dualEdge[primalAdj->theEdge()]->adjTarget();
507  }
508 };
509 
510 }
ogdf::DualGraphBase::addEdgeToIsolatedNodePrimal
edge addEdgeToIsolatedNodePrimal(node v, adjEntry adjTgt)
Inserts a new edge similarly to #splitFace without having to call #computeFaces again.
Definition: DualGraph.h:350
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::DualGraphBase::m_dualFace
NodeArray< face > m_dualFace
The corresponding face in embedding of the dual graph.
Definition: DualGraph.h:450
ogdf::DualGraphBase::removeDeg1Primal
void removeDeg1Primal(node v)
Removes degree-1 node v.
Definition: DualGraph.h:381
ogdf::DualGraphBase::primalNode
const node & primalNode(face f) const
Returns the node in the primal graph corresponding to f.
Definition: DualGraph.h:155
ogdf::Graph::sort
void sort(node v, const ADJ_ENTRY_LIST &newOrder)
Sorts the adjacency list of node v according to newOrder.
Definition: Graph_d.h:1061
ogdf::DualGraphBase::Embedding
typename std::conditional< isConst, const ConstCombinatorialEmbedding, CombinatorialEmbedding >::type Embedding
Definition: DualGraph.h:59
ogdf::DualGraphBase::reverseEdgePrimal
void reverseEdgePrimal(edge e)
Reverses edges e and updates embedding.
Definition: DualGraph.h:406
ogdf::DualGraphBase::primalFace
const face & primalFace(node v) const
Returns the face in the embedding of the primal graph corresponding to v.
Definition: DualGraph.h:169
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::Graph::newEdge
edge newEdge(node v, node w)
Creates a new edge (v,w) and returns it.
ogdf::DualGraphBase::m_primalEmbedding
Embedding & m_primalEmbedding
The embedding of the primal graph.
Definition: DualGraph.h:445
ogdf::AdjElement::theNode
node theNode() const
Returns the node whose adjacency list contains this element.
Definition: Graph_d.h:100
ogdf::DualGraphBase::m_primalEdge
EdgeArray< edge > m_primalEdge
The corresponding edge in the primal graph.
Definition: DualGraph.h:448
ogdf::DualGraphBase
A dual graph including its combinatorial embedding of an embedded graph.
Definition: DualGraph.h:41
ogdf::AdjElement::cyclicPred
adjEntry cyclicPred() const
Returns the cyclic predecessor in the adjacency list.
Definition: Graph_d.h:284
ogdf::DualGraphBase::m_primalFace
NodeArray< face > m_primalFace
The corresponding facee in the embedding of the primal graph.
Definition: DualGraph.h:447
ogdf::FaceElement::entries
internal::FaceAdjContainer entries
Container maintaining the adjacency entries in the face.
Definition: CombinatorialEmbedding.h:139
ogdf::DualGraphBase::unsplitPrimal
void unsplitPrimal(edge eIn, edge eOut)
Undoes a split operation.
Definition: DualGraph.h:235
ogdf::CombinatorialEmbedding::joinFaces
face joinFaces(edge e)
Removes edge e and joins the two faces adjacent to e.
ogdf::CombinatorialEmbedding::splitFace
edge splitFace(adjEntry adjSrc, adjEntry adjTgt, bool sourceAfter=false)
Splits a face by inserting a new edge.
FaceArray.h
declaration and implementation of FaceArray class
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::EdgeArray
Dynamic arrays indexed with edges.
Definition: EdgeArray.h:112
ogdf::CombinatorialEmbedding::splitNode
node splitNode(adjEntry adjStartLeft, adjEntry adjStartRight)
Splits a node while preserving the order of adjacency entries.
ogdf::AdjElement::faceCyclePred
adjEntry faceCyclePred() const
Returns the cyclic predecessor in face.
Definition: Graph_d.h:144
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::reverse
Reverse< T > reverse(T &container)
Provides iterators for container to make it easily iterable in reverse.
Definition: Reverse.h:75
ogdf::AdjElement::isSource
bool isSource() const
Returns true iff this is the source adjacency entry of the corresponding edge.
Definition: Graph_d.h:399
ogdf::edge
EdgeElement * edge
The type of edges.
Definition: Graph_d.h:67
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
ogdf::DualGraphBase::splitPrimal
edge splitPrimal(edge e)
Splits edge e=(v,w) into e=(v,u) and e'=(u,w) creating a new node u.
Definition: DualGraph.h:198
ogdf::Graph::nodes
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition: Graph_d.h:568
ogdf::NodeElement::degree
int degree() const
Returns the degree of the node (indegree + outdegree).
Definition: Graph_d.h:210
ogdf::DualGraphBase::dualAdj
adjEntry dualAdj(adjEntry primalAdj, bool reverse=false)
Returns the corresponding adjEntry of the dual edge of primalAdj (or the opposite adjEntry of the dua...
Definition: DualGraph.h:503
backward::Color::type
type
Definition: backward.hpp:1716
ogdf::FaceArray
Dynamic arrays indexed with faces of a combinatorial embedding.
Definition: CombinatorialEmbedding.h:174
EdgeArray.h
Declaration and implementation of EdgeArray class.
ogdf::DualGraphBase::m_dualEdge
EdgeArray< edge > m_dualEdge
The corresponding edge in the dual graph.
Definition: DualGraph.h:451
ogdf::DualGraphBase::addEdgeToIsolatedNodePrimal
edge addEdgeToIsolatedNodePrimal(adjEntry adj, node v, bool adjSrc)
Inserts a new edge similarly to #splitFace without having to call #computeFaces again.
Definition: DualGraph.h:456
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::node
NodeElement * node
The type of nodes.
Definition: Graph_d.h:63
ogdf::DualGraphBase::getPrimalGraph
const Graph & getPrimalGraph() const
Returns a reference to the primal graph.
Definition: DualGraph.h:145
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
ogdf::EdgeElement::adjSource
adjEntry adjSource() const
Returns the corresponding adjacancy entry at source node.
Definition: Graph_d.h:333
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::CombinatorialEmbedding::reverseEdge
void reverseEdge(edge e)
Reverses edges e and updates embedding.
ogdf::CombinatorialEmbedding::contract
node contract(edge e, bool keepSelfLoops=false)
Contracts edge e while preserving the order of adjacency entries.
ogdf::DualGraphBase::m_dualNode
FaceArray< node > m_dualNode
The corresponding node in the dual graph.
Definition: DualGraph.h:449
ogdf::DualGraphBase::joinFacesPrimal
face joinFacesPrimal(edge e)
Removes edge e and joins the two faces adjacent to e.
Definition: DualGraph.h:362
NodeArray.h
Declaration and implementation of NodeArray class.
ogdf::DualGraphBase::splitFacePrimal
edge splitFacePrimal(adjEntry adjSrc, adjEntry adjTgt, bool sourceAfter=false)
Splits a face by inserting a new edge.
Definition: DualGraph.h:312
ogdf::ConstCombinatorialEmbedding
Combinatorial embeddings of planar graphs.
Definition: CombinatorialEmbedding.h:198
ogdf::EdgeElement::adjTarget
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition: Graph_d.h:335
ogdf::DualGraphBase::getPrimalEmbedding
Embedding & getPrimalEmbedding() const
Returns a reference to the combinatorial embedding of the primal graph.
Definition: DualGraph.h:142
ogdf::DualGraphBase::contractPrimal
node contractPrimal(edge e, bool keepSelfLoops=false)
Contracts edge e while preserving the order of adjacency entries.
Definition: DualGraph.h:290
ogdf::DualGraphBase::dualEdge
const edge & dualEdge(edge e) const
Returns the edge in the dual graph corresponding to e.
Definition: DualGraph.h:183
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::DualGraphBase::m_primalNode
FaceArray< node > m_primalNode
The corresponding node in the primal graph.
Definition: DualGraph.h:446
ogdf::face
FaceElement * face
Definition: CombinatorialEmbedding.h:40
ogdf::Graph::edges
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition: Graph_d.h:571
ogdf::Graph::newNode
node newNode()
Creates a new node and returns it.
CombinatorialEmbedding.h
Declaration of CombinatorialEmbedding and face.
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::DualGraphBase::primalEdge
const edge & primalEdge(edge e) const
Returns the edge in the primal graph corresponding to e.
Definition: DualGraph.h:162
ogdf::CombinatorialEmbedding
Combinatorial embeddings of planar graphs with modification functionality.
Definition: CombinatorialEmbedding.h:409
ogdf::NodeElement::firstAdj
adjEntry firstAdj() const
Returns the first entry in the adjaceny list.
Definition: Graph_d.h:213
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::DualGraphBase::dualNode
const node & dualNode(face f) const
Returns the node in the dual graph corresponding to f.
Definition: DualGraph.h:176
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::DualGraphBase::addEdgeToIsolatedNodePrimal
edge addEdgeToIsolatedNodePrimal(adjEntry adjSrc, node v)
Inserts a new edge similarly to #splitFace without having to call #computeFaces again.
Definition: DualGraph.h:356
ogdf::DualGraphBase::splitNodePrimal
node splitNodePrimal(adjEntry adjStartLeft, adjEntry adjStartRight)
Splits a node while preserving the order of adjacency entries.
Definition: DualGraph.h:253
ogdf::DualGraphBase::dualFace
const face & dualFace(node v) const
Returns the face in the embedding of the dual graph corresponding to v.
Definition: DualGraph.h:190
ogdf::List::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: List.h:1374
ogdf::DualGraphBase::DualGraphBase
DualGraphBase(Embedding &CE)
Constructor; creates dual graph and its combinatorial embedding.
Definition: DualGraph.h:62
ogdf::FaceElement
Faces in a combinatorial embedding.
Definition: CombinatorialEmbedding.h:111