Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

GraphCopy.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/DualGraph.h>
35 #include <ogdf/basic/Graph.h>
36 #include <ogdf/basic/GraphList.h>
37 #include <ogdf/basic/List.h>
38 #include <ogdf/basic/SList.h>
39 #include <ogdf/basic/basic.h>
42 
43 #include <functional>
44 
45 namespace ogdf {
46 
47 class CombinatorialEmbedding;
48 class FaceSet;
49 
51 protected:
52  const Graph* m_pGraph = nullptr;
56  bool m_linkCopiesOnInsert =
57  true;
58 
59 public:
61  GraphCopyBase() = default;
62 
63  GraphCopyBase(const GraphCopyBase& other) = delete;
64 
65  GraphCopyBase(GraphCopyBase&& other) noexcept = delete;
66 
67  GraphCopyBase& operator=(const GraphCopyBase& other) = delete;
68 
69  GraphCopyBase& operator=(GraphCopyBase&& other) noexcept = delete;
70 
72  void init(const Graph& G) {
73  Graph::clear();
74  setOriginalGraph(&G);
75  insert(G);
76  }
77 
79  void init(const Graph* G) {
80  Graph::clear();
81  setOriginalGraph(G);
82  if (G != nullptr) {
83  insert(*G);
84  }
85  }
86 
88  OGDF_DEPRECATED("setOriginalGraph() should be used instead.")
89 
90  void createEmpty(const Graph& G) { setOriginalGraph(&G); }
91 
93  virtual void setOriginalGraph(const Graph* G) = 0;
94 
96  void setOriginalGraph(const Graph& G) { setOriginalGraph(&G); };
97 
98  const Graph* getOriginalGraph() const { return m_pGraph; }
99 
101  void clear() override = 0;
102 
104  const Graph& original() const {
105  OGDF_ASSERT(m_pGraph != nullptr);
106  return *m_pGraph;
107  }
108 
115  node original(node v) const { return m_vOrig[v]; }
116 
123  edge original(edge e) const { return m_eOrig[e]; }
124 
136  edge f = m_eOrig[adj->theEdge()];
137  return adj->isSource() ? f->adjSource() : f->adjTarget();
138  }
139 
146  node copy(node v) const { return m_vCopy[v]; }
147 
156  virtual edge copy(edge e) const = 0;
157 
166  virtual adjEntry copy(adjEntry adj) const = 0;
167 
172  bool isDummy(node v) const { return m_vOrig[v] == nullptr; }
173 
178  bool isDummy(edge e) const { return m_eOrig[e] == nullptr; }
179 
184  bool isDummy(adjEntry adj) const { return isDummy(adj->theEdge()); }
185 
191  node newNode(node vOrig) {
192  OGDF_ASSERT(vOrig != nullptr);
193  OGDF_ASSERT(vOrig->graphOf() == m_pGraph);
194  node v = Graph::newNode();
195  m_vCopy[m_vOrig[v] = vOrig] = v;
196  return v;
197  }
198 
199  using Graph::newNode;
200 
206  void delNode(node v) override {
207  node vOrig = m_vOrig[v];
208  Graph::delNode(v);
209  if (vOrig != nullptr) {
210  m_vCopy[vOrig] = nullptr;
211  }
212  }
213 
215 
219  virtual void setOriginalEmbedding() = 0;
220 
221  bool getLinkCopiesOnInsert() const { return m_linkCopiesOnInsert; }
222 
224 
233  void setLinkCopiesOnInsert(bool linkCopiesOnInsert) {
234  m_linkCopiesOnInsert = linkCopiesOnInsert;
235  }
236 
237 protected:
238  void* preInsert(bool copyEmbedding, bool copyIDs, bool notifyObservers, bool edgeFilter,
239  NodeArray<node>& nodeMap, EdgeArray<edge>& edgeMap, int* newNodes,
240  int* newEdges) override;
241 
242  void nodeInserted(void* userData, node original, node copy) override;
243 };
244 
261 public:
263 
264  explicit GraphCopySimple() : GraphCopySimple(nullptr) { }
265 
266  explicit GraphCopySimple(const Graph& G) : GraphCopySimple(&G) { }
267 
268  explicit GraphCopySimple(const Graph* G) : GraphCopyBase() {
269  if (G) {
270  init(*G);
271  }
272  }
273 
274  GraphCopySimple(const GraphCopySimple& other) : GraphCopyBase() { *this = other; }
275 
276  GraphCopySimple& operator=(const GraphCopySimple& other);
277 
279 
281  void setOriginalGraph(const Graph* G) override;
282 
284  void clear() override;
285 
286  using GraphCopyBase::copy;
287 
294  edge copy(edge e) const override { return m_eCopy[e]; }
295 
307  adjEntry copy(adjEntry adj) const override {
308  edge f = m_eCopy[adj->theEdge()];
309  if (f == nullptr) {
310  return nullptr;
311  }
312  return adj->isSource() ? f->adjSource() : f->adjTarget();
313  }
314 
320  edge newEdge(edge eOrig) {
321  OGDF_ASSERT(eOrig != nullptr);
322  OGDF_ASSERT(eOrig->graphOf() == m_pGraph);
323 
324  edge e = Graph::newEdge(m_vCopy[eOrig->source()], m_vCopy[eOrig->target()]);
325  m_eCopy[m_eOrig[e] = eOrig] = e;
326 
327  return e;
328  }
329 
330  using Graph::newEdge;
331 
337  void delEdge(edge e) override;
338 
339  void setOriginalEmbedding() override;
340 
348  void copyEmbeddingToOriginal(Graph& orig) const;
349 
350 protected:
351  void edgeInserted(void* userData, edge original, edge copy) override;
352 };
353 
391 protected:
394 
395 public:
396  explicit GraphCopy() : GraphCopy(nullptr) { }
397 
398  explicit GraphCopy(const Graph& G) : GraphCopy(&G) { }
399 
400  explicit GraphCopy(const Graph* G) : GraphCopyBase() {
401  if (G) {
402  init(*G);
403  }
404  }
405 
406  GraphCopy(const GraphCopy& other) : GraphCopyBase() { *this = other; }
407 
408  GraphCopy& operator=(const GraphCopy& other);
409 
411 
413 
438  void setOriginalGraph(const Graph* G) override;
439 
441  void clear() override;
442 
446 
453  const List<edge>& chain(edge e) const { return m_eCopy[e]; }
454 
455  using GraphCopyBase::copy;
456 
463  edge copy(edge e) const override { return m_eCopy[e].empty() ? nullptr : m_eCopy[e].front(); }
464 
475  adjEntry copy(adjEntry adj) const override {
476  auto& el = m_eCopy[adj->theEdge()];
477  if (el.empty()) {
478  return nullptr;
479  } else if (adj->isSource()) {
480  return el.front()->adjSource();
481  } else {
482  return el.back()->adjTarget();
483  }
484  }
485 
490  bool isReversed(edge e) const { return e->source() != original(copy(e)->source()); }
491 
498  bool isReversedCopyEdge(edge e) const;
500 
504 
512  void delEdge(edge e) override;
513 
519  edge split(edge e) override;
520 
529  void unsplit(edge eIn, edge eOut) override;
530 
532  edge newEdge(edge eOrig);
533 
534  using Graph::newEdge;
535 
537 
541  void setEdge(edge eOrig, edge eCopy);
542 
543  void setOriginalEmbedding() override;
544 
546  void removePseudoCrossings();
547 
550  bool hasSameEdgesCrossings() const;
551 
554  bool hasAdjacentEdgesCrossings() const;
555 
558 
565  inline bool hasNonSimpleCrossings() const {
566  return hasAdjacentEdgesCrossings() || hasSameEdgesCrossings();
567  };
568 
580  void removeNonSimpleCrossings(SListPure<edge>& edgesToCheck,
581  DynamicDualGraph* dualGraph = nullptr);
582 
592  inline void removeNonSimpleCrossings(DynamicDualGraph* dualGraph = nullptr) {
593  SListPure<edge> edgesToCheck;
594  m_pGraph->allEdges(edgesToCheck);
595  removeNonSimpleCrossings(edgesToCheck, dualGraph);
596  };
597 
609  inline void removeNonSimpleCrossings(node origNode, DynamicDualGraph* dualGraph = nullptr) {
610  SListPure<edge> edgesToCheck;
611  for (adjEntry adj : origNode->adjEntries) {
612  edgesToCheck.pushBack(adj->theEdge());
613  }
614  removeNonSimpleCrossings(edgesToCheck, dualGraph);
615  }
616 
618 
627  void insertEdgePath(edge eOrig, const SList<adjEntry>& crossedEdges);
628 
630  void insertEdgePath(node srcOrig, node tgtOrig, const SList<adjEntry>& crossedEdges);
631 
633 
636  void removeEdgePath(edge eOrig);
637 
639 
655  edge insertCrossing(edge& crossingEdge, edge crossedEdge, bool rightToLeft);
657 
661 
664 
678  edge newEdge(node v, adjEntry adj, edge eOrig, CombinatorialEmbedding& E);
679 
681 
700  void insertEdgePathEmbedded(edge eOrig, CombinatorialEmbedding& E,
701  const SList<adjEntry>& crossedEdges);
702 
703  void insertEdgePathEmbedded(edge eOrig, CombinatorialEmbedding& E, DynamicDualGraph& dual,
704  const SList<adjEntry>& crossedEdges);
705 
707 
717  void removeEdgePathEmbedded(CombinatorialEmbedding& E, edge eOrig, FaceSet& newFaces);
718 
719  void removeEdgePathEmbedded(CombinatorialEmbedding& E, DynamicDualGraph& dual, edge eOrig);
720 
722 
725 
727 #ifdef OGDF_DEBUG
728  void consistencyCheck() const;
730 #endif
731 
733 
734 protected:
735  void edgeInserted(void* userData, edge original, edge copy) override;
736 
737 
738  void removeUnnecessaryCrossing(adjEntry adjA1, adjEntry adjA2, adjEntry adjB1, adjEntry adjB2);
739 
749  void removeUnnecessaryCrossing(adjEntry adj, DynamicDualGraph* dualGraph);
750 
758  void removeAdjacentEdgesCrossing(adjEntry adj1, adjEntry adj2, DynamicDualGraph* dualGraph);
759 
769  void removeSameEdgesCrossing(adjEntry adjFirstCrossing1, adjEntry adjFirstCrossing2,
770  adjEntry adjSecondCrossing1, adjEntry adjSecondCrossing2, DynamicDualGraph* dualGraph);
771 
780  void swapOriginalEdgesAtCrossing(adjEntry adjCopy1, adjEntry adjCopy2,
781  DynamicDualGraph* dual = nullptr);
782 
789  void swapOriginalEdgesBetweenCrossings(adjEntry adjFirstCrossing1, adjEntry adjFirstCrossing2,
790  adjEntry adjSecondCrossing1, adjEntry adjSecondCrossing2,
791  DynamicDualGraph* dual = nullptr);
792 
797  void setOriginalEdgeAlongCrossings(adjEntry adjCopy1, adjEntry adjCopy2, node vCopy,
798  edge eOrig1, edge eOrig2);
799 };
800 
801 OGDF_EXPORT void copyEmbedding(const Graph& from, Graph& to,
802  std::function<adjEntry(adjEntry)> adjMapFromTo);
803 
804 }
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:592
ogdf
The namespace for all OGDF objects.
Definition: multilevelmixer.cpp:39
ogdf::GraphCopyBase::original
node original(node v) const
Returns the node in the original graph corresponding to v.
Definition: GraphCopy.h:115
ogdf::GraphCopyBase::getOriginalGraph
const Graph * getOriginalGraph() const
Definition: GraphCopy.h:98
Graph.h
Includes declaration of graph class.
ogdf::GraphCopyBase::original
edge original(edge e) const
Returns the edge in the original graph corresponding to e.
Definition: GraphCopy.h:123
ogdf::GraphCopySimple::copy
edge copy(edge e) const override
Returns the edge in the graph copy corresponding to e.
Definition: GraphCopy.h:294
ogdf::GraphCopy::isReversed
bool isReversed(edge e) const
Returns true iff edge e has been reversed.
Definition: GraphCopy.h:490
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:66
ogdf::Graph::delNode
virtual void delNode(node v)
Removes node v and all incident edges from the graph.
ogdf::GraphCopyBase::m_vOrig
NodeArray< node > m_vOrig
The corresponding node in the original graph.
Definition: GraphCopy.h:53
OGDF_DEPRECATED
#define OGDF_DEPRECATED(reason)
Mark a class / member / function as deprecated.
Definition: config.h:206
ogdf::DualGraphBase
A dual graph including its combinatorial embedding of an embedded graph.
Definition: DualGraph.h:47
ogdf::GraphCopySimple::GraphCopySimple
GraphCopySimple(const Graph &G)
Definition: GraphCopy.h:266
ogdf::GraphCopy::hasNonSimpleCrossings
bool hasNonSimpleCrossings() const
Returns whether the GraphCopy contains crossings that will result in a non-simple drawing.
Definition: GraphCopy.h:565
ogdf::GraphCopyBase::isDummy
bool isDummy(node v) const
Returns true iff v has no corresponding node in the original graph.
Definition: GraphCopy.h:172
ogdf::sync_plan::split
std::pair< node, node > split(Graph &G, sync_plan::PipeBij &bij, const EdgeArray< edge > *new_edges=nullptr, const EdgeArray< bool > *reverse_edges=nullptr, node src=nullptr, node tgt=nullptr)
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:845
ogdf::GraphCopy
Copies of graphs supporting edge splitting.
Definition: GraphCopy.h:390
ogdf::GraphCopyBase::setOriginalGraph
virtual void setOriginalGraph(const Graph *G)=0
Re-initializes the copy using G (which might be null), but does not create any nodes or edges.
ogdf::GraphCopySimple
Copies of graphs with mapping between nodes and edges.
Definition: GraphCopy.h:260
ogdf::GraphCopyBase::isDummy
bool isDummy(adjEntry adj) const
Returns true iff adj->theEdge() has no corresponding edge in the original graph.
Definition: GraphCopy.h:184
ogdf::GraphCopySimple::copy
adjEntry copy(adjEntry adj) const override
Returns the adjacency entry in the graph copy corresponding to adj.
Definition: GraphCopy.h:307
ogdf::adjEntry
AdjElement * adjEntry
The type of adjacency entries.
Definition: Graph_d.h:79
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:143
ogdf::AdjElement::isSource
bool isSource() const
Returns true iff this is the source adjacency entry of the corresponding edge.
Definition: Graph_d.h:480
ogdf::GraphCopyBase::getLinkCopiesOnInsert
bool getLinkCopiesOnInsert() const
Definition: GraphCopy.h:221
ogdf::GraphCopy::copy
adjEntry copy(adjEntry adj) const override
Returns the adjacency entry in the copy graph corresponding to adj.
Definition: GraphCopy.h:475
ogdf::GraphCopyBase::m_vCopy
NodeArray< node > m_vCopy
The corresponding node in the graph copy.
Definition: GraphCopy.h:55
ogdf::GraphCopy::GraphCopy
GraphCopy(const GraphCopy &other)
Definition: GraphCopy.h:406
ogdf::GraphCopyBase::init
void init(const Graph &G)
Re-initializes the copy using G, creating copies for all nodes and edges in G.
Definition: GraphCopy.h:72
ogdf::GraphCopyBase::original
adjEntry original(adjEntry adj) const
Returns the adjacency entry in the original graph corresponding to adj.
Definition: GraphCopy.h:135
ogdf::AdjElement::theEdge
edge theEdge() const
Returns the edge associated with this adjacency entry.
Definition: Graph_d.h:161
ogdf::Graph::clear
virtual void clear()
Removes all nodes and all edges from the graph.
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:609
Minisat::Internal::copy
static void copy(const T &from, T &to)
Definition: Alg.h:62
ogdf::EdgeElement::graphOf
const Graph * graphOf() const
Returns the graph containing this node (debug only).
Definition: Graph_d.h:441
ogdf::GraphCopyBase::setLinkCopiesOnInsert
void setLinkCopiesOnInsert(bool linkCopiesOnInsert)
Whether insert(getOriginalGraph()) will automatically set copy and original.
Definition: GraphCopy.h:233
SList.h
Declaration of singly linked lists and iterators.
GraphList.h
Decralation of GraphElement and GraphList classes.
ogdf::GraphCopy::GraphCopy
GraphCopy(const Graph &G)
Definition: GraphCopy.h:398
ogdf::NodeElement::adjEntries
internal::GraphObjectContainer< AdjElement > adjEntries
The container containing all entries in the adjacency list of this node.
Definition: Graph_d.h:272
ogdf::GraphCopySimple::GraphCopySimple
GraphCopySimple()
Definition: GraphCopy.h:264
ogdf::GraphCopy::chain
const List< edge > & chain(edge e) const
Returns the list of edges coresponding to edge e.
Definition: GraphCopy.h:453
ogdf::FaceSet
Face sets.
Definition: FaceSet.h:51
DualGraph.h
Includes declaration of dual graph class.
ogdf::SListPure
Singly linked lists.
Definition: SList.h:52
config_autogen.h
ogdf::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:399
ogdf::GraphCopyBase::newNode
node newNode(node vOrig)
Creates a new node in the graph copy with original node vOrig.
Definition: GraphCopy.h:191
ogdf::List< edge >
ogdf::internal::GraphRegisteredArray
RegisteredArray for nodes, edges and adjEntries of a graph.
Definition: Graph_d.h:659
ogdf::GraphCopyBase::init
void init(const Graph *G)
Re-initializes the copy using G (which might be null), creating copies for all nodes and edges in G.
Definition: GraphCopy.h:79
ogdf::GraphCopy::m_eCopy
EdgeArray< List< edge > > m_eCopy
The corresponding list of edges in the graph copy.
Definition: GraphCopy.h:393
ogdf::EdgeElement::adjSource
adjEntry adjSource() const
Returns the corresponding adjacancy entry at source node.
Definition: Graph_d.h:408
ogdf::GraphCopyBase::delNode
void delNode(node v) override
Removes node v.
Definition: GraphCopy.h:206
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:866
ogdf::GraphCopyBase
Definition: GraphCopy.h:50
ogdf::GraphCopy::copy
edge copy(edge e) const override
Returns the first edge in the list of edges corresponding to edge e.
Definition: GraphCopy.h:463
graph_iterators.h
Decralation of graph iterators.
ogdf::GraphCopySimple::GraphCopySimple
GraphCopySimple(const Graph *G)
Definition: GraphCopy.h:268
ogdf::EdgeElement::adjTarget
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition: Graph_d.h:411
ogdf::graphics::init
void init()
Definition: graphics.h:450
basic.h
Basic declarations, included by all source files.
ogdf::GraphCopyBase::isDummy
bool isDummy(edge e) const
Returns true iff e has no corresponding edge in the original graph.
Definition: GraphCopy.h:178
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF dynamic library (shared object / DLL),...
Definition: config.h:117
ogdf::GraphCopyBase::setOriginalGraph
void setOriginalGraph(const Graph &G)
Re-initializes the copy using G, but does not create any nodes or edges.
Definition: GraphCopy.h:96
ogdf::Graph::newNode
node newNode(int index=-1)
Creates a new node and returns it.
Definition: Graph_d.h:1061
ogdf::CombinatorialEmbedding
Combinatorial embeddings of planar graphs with modification functionality.
Definition: CombinatorialEmbedding.h:406
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:364
List.h
Declaration of doubly linked lists and iterators.
ogdf::NodeElement::graphOf
const Graph * graphOf() const
Returns the graph containing this node (debug only).
Definition: Graph_d.h:345
ogdf::GraphCopySimple::m_eCopy
EdgeArray< edge > m_eCopy
The corresponding edge in the graph copy.
Definition: GraphCopy.h:262
ogdf::SListPure::pushBack
iterator pushBack(const E &x)
Adds element x at the end of the list.
Definition: SList.h:481
ogdf::GraphCopy::GraphCopy
GraphCopy()
Definition: GraphCopy.h:396
ogdf::GraphCopy::m_eIterator
EdgeArray< ListIterator< edge > > m_eIterator
The position of copy edge in the list.
Definition: GraphCopy.h:392
ogdf::EdgeElement::target
node target() const
Returns the target node of the edge.
Definition: Graph_d.h:402
ogdf::GraphCopySimple::GraphCopySimple
GraphCopySimple(const GraphCopySimple &other)
Definition: GraphCopy.h:274
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:1080
ogdf::copyEmbedding
void copyEmbedding(const Graph &from, Graph &to, std::function< adjEntry(adjEntry)> adjMapFromTo)
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:241
ogdf::GraphCopySimple::newEdge
edge newEdge(edge eOrig)
Creates a new edge in the graph copy with original edge eOrig.
Definition: GraphCopy.h:320
ogdf::GraphCopyBase::original
const Graph & original() const
Returns a reference to the original graph.
Definition: GraphCopy.h:104
ogdf::internal::EdgeArrayBase2
RegisteredArray for edges of a graph, specialized for EdgeArray<edge>.
Definition: Graph_d.h:717
ogdf::GraphCopy::GraphCopy
GraphCopy(const Graph *G)
Definition: GraphCopy.h:400
ogdf::GraphCopyBase::copy
node copy(node v) const
Returns the node in the graph copy corresponding to v.
Definition: GraphCopy.h:146
ogdf::GraphCopyBase::m_eOrig
EdgeArray< edge > m_eOrig
The corresponding edge in the original graph.
Definition: GraphCopy.h:54