Open
Graph Drawing
Framework

  v. 2023.09 (Elderberry)
 
Overview Class Hierarchy Class Index Class List Members Namespaces Source Files

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