Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

GraphCopy.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/NodeArray.h>
35 #include <ogdf/basic/EdgeArray.h>
36 #include <ogdf/basic/SList.h>
37 #include <ogdf/basic/DualGraph.h>
38 
39 
40 namespace ogdf {
41 
42 template<bool b> class FaceSet;
43 
44 
61 {
62  const Graph *m_pGraph;
67 
68 public:
71 
73  explicit GraphCopySimple(const Graph &G);
74 
77 
78  virtual ~GraphCopySimple() { }
79 
81  void init(const Graph &G);
82 
84  void createEmpty(const Graph &G);
85 
87  const Graph &original() const { return *m_pGraph; }
88 
95  node original(node v) const { return m_vOrig[v]; }
96 
103  edge original(edge e) const { return m_eOrig[e]; }
104 
116  edge f = m_eOrig[adj->theEdge()];
117  return adj->isSource() ? f->adjSource() : f->adjTarget();
118  }
119 
126  node copy(node v) const { return m_vCopy[v]; }
127 
134  edge copy(edge e) const { return m_eCopy[e]; }
135 
147  adjEntry copy(adjEntry adj) const {
148  edge f = m_eCopy[adj->theEdge()];
149  if (f == nullptr) { return nullptr; }
150  return adj->isSource() ? f->adjSource() : f->adjTarget();
151  }
152 
157  bool isDummy(node v) const { return m_vOrig[v] == nullptr; }
158 
163  bool isDummy(edge e) const { return m_eOrig[e] == nullptr; }
164 
166  GraphCopySimple &operator=(const GraphCopySimple &GC);
167 
173  node newNode(node vOrig) {
174  OGDF_ASSERT(vOrig != nullptr);
175  OGDF_ASSERT(vOrig->graphOf() == m_pGraph);
176  node v = Graph::newNode();
177  m_vCopy[m_vOrig[v] = vOrig] = v;
178  return v;
179  }
180 
181  using Graph::newNode;
182 
188  edge newEdge(edge eOrig) {
189  OGDF_ASSERT(eOrig != nullptr);
190  OGDF_ASSERT(eOrig->graphOf() == m_pGraph);
191 
192  edge e = Graph::newEdge(m_vCopy[eOrig->source()], m_vCopy[eOrig->target()]);
193  m_eCopy[m_eOrig[e] = eOrig] = e;
194 
195  return e;
196  }
197 
198  using Graph::newEdge;
199 
205  virtual void delEdge(edge e) override;
206 
212  virtual void delNode(node v) override;
213 
214 private:
215  void initGC(const GraphCopySimple &GC, NodeArray<node> &vCopy,
216  EdgeArray<edge> &eCopy);
217 };
218 
255 class OGDF_EXPORT GraphCopy : public Graph {
256 protected:
257 
258  const Graph *m_pGraph;
262 
265 
266 public:
268 
271  explicit GraphCopy(const Graph &G);
272 
274  GraphCopy() : Graph(), m_pGraph(nullptr) { }
275 
277 
281  GraphCopy(const GraphCopy &GC);
282 
283  virtual ~GraphCopy() { }
284 
285 
290 
292  const Graph &original() const { return *m_pGraph; }
293 
300  node original(node v) const { return m_vOrig[v]; }
301 
308  edge original(edge e) const { return m_eOrig[e]; }
309 
324  edge e = adj->theEdge();
325  edge f = m_eOrig[e];
326 
327  if (adj->isSource()) {
328  OGDF_ASSERT(m_eCopy[f].front() == e);
329  return f->adjSource();
330  } else {
331  OGDF_ASSERT(m_eCopy[f].back() == e);
332  return f->adjTarget();
333  }
334  }
335 
341  node copy(node v) const { return m_vCopy[v]; }
342 
348  const List<edge> &chain(edge e) const { return m_eCopy[e]; }
349 
350  // returns first edge in chain(e)
357  edge copy(edge e) const { return m_eCopy[e].empty() ? nullptr : m_eCopy[e].front(); }
358 
369  adjEntry copy(adjEntry adj) const {
370  edge e = adj->theEdge();
371 
372  if (adj->isSource()) {
373  return m_eCopy[e].front()->adjSource();
374  } else {
375  return m_eCopy[e].back()->adjTarget();
376  }
377  }
378 
383  bool isDummy(node v) const { return m_vOrig[v] == nullptr; }
384 
389  bool isDummy(edge e) const { return m_eOrig[e] == nullptr; }
390 
395  bool isReversed (edge e) const {
396  return e->source() != original(copy(e)->source());
397  }
398 
405  bool isReversedCopyEdge (edge e) const;
406 
407 
412 
418  node newNode(node vOrig) {
419  OGDF_ASSERT(vOrig != nullptr);
420  OGDF_ASSERT(vOrig->graphOf() == m_pGraph);
421  node v = Graph::newNode();
422  m_vCopy[m_vOrig[v] = vOrig] = v;
423  return v;
424  }
425 
426  using Graph::newNode;
427 
434  virtual void delNode(node v) override;
435 
442  virtual void delEdge(edge e) override;
443 
444 
445  virtual void clear() override;
446 
452  virtual edge split(edge e) override;
453 
454 
463  void unsplit(edge eIn, edge eOut) override;
464 
466  edge newEdge(edge eOrig);
467 
468  using Graph::newEdge;
469 
471 
475  void setEdge(edge eOrig, edge eCopy);
476 
478  OGDF_DEPRECATED("Use ogdf::planarEmbed() instead.")
479  bool embed();
480 
482  void removePseudoCrossings();
483 
486  bool hasSameEdgesCrossings() const;
487 
490  bool hasAdjacentEdgesCrossings() const;
491 
494 
501  inline bool hasNonSimpleCrossings() const {
502  return hasAdjacentEdgesCrossings() || hasSameEdgesCrossings();
503  };
504 
516  void removeNonSimpleCrossings(SListPure<edge> &edgesToCheck,
517  DynamicDualGraph *dualGraph = nullptr);
518 
528  inline void removeNonSimpleCrossings(DynamicDualGraph *dualGraph = nullptr) {
529  SListPure<edge> edgesToCheck;
530  m_pGraph->allEdges(edgesToCheck);
531  removeNonSimpleCrossings(edgesToCheck, dualGraph);
532  };
533 
545  inline void removeNonSimpleCrossings(node origNode, DynamicDualGraph *dualGraph = nullptr) {
546  SListPure<edge> edgesToCheck;
547  for (adjEntry adj : origNode->adjEntries) {
548  edgesToCheck.pushBack(adj->theEdge());
549  }
550  removeNonSimpleCrossings(edgesToCheck, dualGraph);
551  }
552 
553 
555 
564  void insertEdgePath(edge eOrig, const SList<adjEntry> &crossedEdges);
565 
567  void insertEdgePath(node srcOrig, node tgtOrig, const SList<adjEntry> &crossedEdges);
568 
569 
571 
574  void removeEdgePath(edge eOrig);
575 
577 
593  edge insertCrossing(
594  edge& crossingEdge,
595  edge crossedEdge,
596  bool rightToLeft);
597 
598 
603 
605 
619  edge newEdge(node v, adjEntry adj, edge eOrig, CombinatorialEmbedding &E);
620 
626  void setOriginalEmbedding();
627 
629 
648  void insertEdgePathEmbedded(
649  edge eOrig,
651  const SList<adjEntry> &crossedEdges);
652 
653  void insertEdgePathEmbedded(
654  edge eOrig,
656  DynamicDualGraph &dual,
657  const SList<adjEntry> &crossedEdges);
658 
660 
670  void removeEdgePathEmbedded(
672  edge eOrig,
673  FaceSet<false> &newFaces);
674 
675  void removeEdgePathEmbedded(
677  DynamicDualGraph &dual,
678  edge eOrig);
679 
680 
682 
686 
687 #ifdef OGDF_DEBUG
688  void consistencyCheck() const;
690 #endif
691 
693 
700  void init(const Graph &G);
701 
703 
732  void createEmpty(const Graph &G);
733 
735 
740  void initByCC(const CCsInfo &info, int cc, EdgeArray<edge> &eCopy);
741 
743 
759  void initByNodes(const List<node> &origNodes, EdgeArray<edge> &eCopy);
760 
762 
774  void initByActiveNodes(const List<node> &nodeList,
775  const NodeArray<bool> &activeNodes, EdgeArray<edge> &eCopy);
776 
778 
782 
784 
792  GraphCopy &operator=(const GraphCopy &GC);
793 
794 
796 
797 protected:
798  void removeUnnecessaryCrossing(
799  adjEntry adjA1,
800  adjEntry adjA2,
801  adjEntry adjB1,
802  adjEntry adjB2);
803 
813  void removeUnnecessaryCrossing(
814  adjEntry adj,
815  DynamicDualGraph *dualGraph);
816 
824  void removeAdjacentEdgesCrossing(
825  adjEntry adj1,
826  adjEntry adj2,
827  DynamicDualGraph *dualGraph);
828 
838  void removeSameEdgesCrossing(
839  adjEntry adjFirstCrossing1,
840  adjEntry adjFirstCrossing2,
841  adjEntry adjSecondCrossing1,
842  adjEntry adjSecondCrossing2,
843  DynamicDualGraph *dualGraph);
844 
853  void swapOriginalEdgesAtCrossing(adjEntry adjCopy1, adjEntry adjCopy2,
854  DynamicDualGraph *dual = nullptr);
855 
862  void swapOriginalEdgesBetweenCrossings(
863  adjEntry adjFirstCrossing1,
864  adjEntry adjFirstCrossing2,
865  adjEntry adjSecondCrossing1,
866  adjEntry adjSecondCrossing2,
867  DynamicDualGraph *dual = nullptr);
868 
873  void setOriginalEdgeAlongCrossings(
874  adjEntry adjCopy1,
875  adjEntry adjCopy2,
876  node vCopy,
877  edge eOrig1,
878  edge eOrig2);
879 
880 private:
881  void initGC(const GraphCopy &GC,
882  NodeArray<node> &vCopy, EdgeArray<edge> &eCopy);
883 };
884 
885 }
ogdf::GraphCopy::m_vOrig
NodeArray< node > m_vOrig
The corresponding node in the original graph.
Definition: GraphCopy.h:259
ogdf::GraphCopy::copy
adjEntry copy(adjEntry adj) const
Returns the adjacency entry in the copy graph corresponding to adj.
Definition: GraphCopy.h:369
ogdf::GraphCopy::removeNonSimpleCrossings
void removeNonSimpleCrossings(DynamicDualGraph *dualGraph=nullptr)
Removes all non-simple cossings (see hasNonSimpleCrossings() for a definition of non-simple crossings...
Definition: GraphCopy.h:528
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::GraphCopy::isDummy
bool isDummy(edge e) const
Returns true iff e has no corresponding edge in the original graph.
Definition: GraphCopy.h:389
ogdf::GraphCopySimple::original
adjEntry original(adjEntry adj) const
Returns the adjacency entry in the original graph corresponding to adj.
Definition: GraphCopy.h:115
ogdf::GraphCopy::isReversed
bool isReversed(edge e) const
Returns true iff edge e has been reversed.
Definition: GraphCopy.h:395
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::GraphCopy::original
const Graph & original() const
Returns a reference to the original graph.
Definition: GraphCopy.h:292
ogdf::Graph::newEdge
edge newEdge(node v, node w)
Creates a new edge (v,w) and returns it.
ogdf::GraphCopy::m_eOrig
EdgeArray< edge > m_eOrig
The corresponding edge in the original graph.
Definition: GraphCopy.h:260
OGDF_DEPRECATED
#define OGDF_DEPRECATED(reason)
Mark a class / member / function as deprecated.
Definition: config.h:118
ogdf::DualGraphBase
A dual graph including its combinatorial embedding of an embedded graph.
Definition: DualGraph.h:41
ogdf::GraphCopySimple::m_pGraph
const Graph * m_pGraph
The original graph.
Definition: GraphCopy.h:62
ogdf::GraphCopy::original
edge original(edge e) const
Returns the edge in the original graph corresponding to e.
Definition: GraphCopy.h:308
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
ogdf::GraphCopySimple::copy
adjEntry copy(adjEntry adj) const
Returns the adjacency entry in the graph copy corresponding to adj.
Definition: GraphCopy.h:147
ogdf::GraphCopySimple::copy
node copy(node v) const
Returns the node in the graph copy corresponding to v.
Definition: GraphCopy.h:126
ogdf::GraphCopy
Copies of graphs supporting edge splitting.
Definition: GraphCopy.h:255
ogdf::GraphCopySimple::m_eOrig
EdgeArray< edge > m_eOrig
The corresponding edge in the original graph.
Definition: GraphCopy.h:65
ogdf::GraphCopySimple::original
const Graph & original() const
Returns a reference to the original graph.
Definition: GraphCopy.h:87
ogdf::GraphCopy::isDummy
bool isDummy(node v) const
Returns true iff v has no corresponding node in the original graph.
Definition: GraphCopy.h:383
ogdf::GraphCopySimple
Copies of graphs with mapping between nodes and edges.
Definition: GraphCopy.h:60
ogdf::GraphCopy::m_pGraph
const Graph * m_pGraph
The original graph.
Definition: GraphCopy.h:258
ogdf::GraphCopySimple::isDummy
bool isDummy(edge e) const
Returns true iff e has no corresponding edge in the original graph.
Definition: GraphCopy.h:163
ogdf::Graph::allEdges
void allEdges(CONTAINER &edgeContainer) const
Returns a container with all edges of the graph.
Definition: Graph_d.h:664
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
ogdf::EdgeArray
Dynamic arrays indexed with edges.
Definition: EdgeArray.h:112
ogdf::GraphCopy::copy
node copy(node v) const
Returns the node in the graph copy corresponding to v.
Definition: GraphCopy.h:341
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
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::GraphCopy::m_vCopy
NodeArray< node > m_vCopy
The corresponding node in the graph copy.
Definition: GraphCopy.h:263
ogdf::GraphCopySimple::original
edge original(edge e) const
Returns the edge in the original graph corresponding to e.
Definition: GraphCopy.h:103
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:96
ogdf::GraphCopySimple::m_vOrig
NodeArray< node > m_vOrig
The corresponding node in the original graph.
Definition: GraphCopy.h:63
ogdf::GraphCopy::removeNonSimpleCrossings
void removeNonSimpleCrossings(node origNode, DynamicDualGraph *dualGraph=nullptr)
Removes all non-simple cossings involving edges incident to origNode (see hasNonSimpleCrossings() for...
Definition: GraphCopy.h:545
Minisat::Internal::copy
static void copy(const T &from, T &to)
Definition: Alg.h:61
ogdf::GraphCopy::~GraphCopy
virtual ~GraphCopy()
Definition: GraphCopy.h:283
SList.h
Declaration of singly linked lists and iterators.
ogdf::NodeElement::adjEntries
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition: Graph_d.h:200
EdgeArray.h
Declaration and implementation of EdgeArray class.
ogdf::GraphCopySimple::copy
edge copy(edge e) const
Returns the edge in the graph copy corresponding to e.
Definition: GraphCopy.h:134
ogdf::GraphCopy::chain
const List< edge > & chain(edge e) const
Returns the list of edges coresponding to edge e.
Definition: GraphCopy.h:348
ogdf::FaceSet< false >
DualGraph.h
Includes declaration of dual graph class.
ogdf::GraphCopy::copy
edge copy(edge e) const
Returns the first edge in the list of edges coresponding to edge e.
Definition: GraphCopy.h:357
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ogdf::List< edge >
ogdf::GraphCopy::m_eCopy
EdgeArray< List< edge > > m_eCopy
The corresponding list of edges in the graph copy.
Definition: GraphCopy.h:264
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::GraphCopy::original
node original(node v) const
Returns the node in the original graph corresponding to v.
Definition: GraphCopy.h:300
ogdf::GraphCopySimple::newNode
node newNode(node vOrig)
Creates a new node in the graph copy with original node vOrig.
Definition: GraphCopy.h:173
NodeArray.h
Declaration and implementation of NodeArray class.
ogdf::GraphCopySimple::original
node original(node v) const
Returns the node in the original graph corresponding to v.
Definition: GraphCopy.h:95
ogdf::EdgeElement::adjTarget
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition: Graph_d.h:335
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::Graph::newNode
node newNode()
Creates a new node and returns it.
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::CombinatorialEmbedding
Combinatorial embeddings of planar graphs with modification functionality.
Definition: CombinatorialEmbedding.h:409
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::GraphCopySimple::m_eCopy
EdgeArray< edge > m_eCopy
The corresponding edge in the graph copy.
Definition: GraphCopy.h:66
ogdf::GraphCopySimple::~GraphCopySimple
virtual ~GraphCopySimple()
Definition: GraphCopy.h:78
ogdf::SListPure::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: SList.h:451
ogdf::GraphCopy::GraphCopy
GraphCopy()
Default constructor (does nothing!).
Definition: GraphCopy.h:274
ogdf::GraphCopy::m_eIterator
EdgeArray< ListIterator< edge > > m_eIterator
The position of copy edge in the list.
Definition: GraphCopy.h:261
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:328
ogdf::GraphCopy::original
adjEntry original(adjEntry adj) const
Returns the adjacency entry in the original graph corresponding to adj.
Definition: GraphCopy.h:323
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::GraphCopy::newNode
node newNode(node vOrig)
Creates a new node in the graph copy with original node vOrig.
Definition: GraphCopy.h:418
ogdf::GraphCopySimple::newEdge
edge newEdge(edge eOrig)
Creates a new edge in the graph copy with original edge eOrig.
Definition: GraphCopy.h:188
ogdf::GraphCopySimple::isDummy
bool isDummy(node v) const
Returns true iff v has no corresponding node in the original graph.
Definition: GraphCopy.h:157
ogdf::Array< T >::empty
bool empty() const
Returns true iff there are no elements in the array.
Definition: Array.h:289
ogdf::GraphCopySimple::m_vCopy
NodeArray< node > m_vCopy
The corresponding node in the graph copy.
Definition: GraphCopy.h:64