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