Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

CombinatorialEmbedding.h
Go to the documentation of this file.
1 
34 #pragma once
35 
37 
38 namespace ogdf {
39 
40 using face = FaceElement*;
41 
43 OGDF_EXPORT std::ostream &operator<<(std::ostream &os, ogdf::face f);
44 
45 // Definition of iterator and container types for adjacency entries in a face
46 // These declarations are just internal representations
47 namespace internal {
48 
51 
54 
55 public:
56  FaceAdjIterator() : m_adj(nullptr), m_adjFirst(nullptr) { }
57  explicit FaceAdjIterator(adjEntry adj) : m_adj(adj), m_adjFirst(adj) { }
58  FaceAdjIterator(adjEntry adjFirst, adjEntry adj) : m_adj(adj), m_adjFirst(adjFirst) { }
59  FaceAdjIterator(const FaceAdjIterator&) = default;
60  FaceAdjIterator& operator=(const FaceAdjIterator&) = default;
61 
62  bool operator==(const FaceAdjIterator &other) const {
63  return m_adj == other.m_adj;
64  }
65 
66  bool operator!=(const FaceAdjIterator &other) const {
67  return m_adj != other.m_adj;
68  }
69 
70  adjEntry operator*() const { return m_adj; }
71 
73  OGDF_ASSERT(m_adj != nullptr);
75  if (m_adj == m_adjFirst)
76  m_adj = nullptr;
77  return *this;
78  }
79 };
80 
81 
83 
88 
89  friend class ogdf::FaceElement;
92 
94 
95  FaceAdjContainer() : m_adjFirst(nullptr) { }
96  explicit FaceAdjContainer(adjEntry adjFirst) : m_adjFirst(adjFirst) { }
97 
98 public:
100 
101  iterator begin() const { return iterator(m_adjFirst); }
102  iterator end() const { return iterator(); }
103 };
104 
105 }
106 
107 
112 {
116 
117  //adjEntry m_adjFirst; //!< The first adjacency element in the face.
118  int m_id;
119  int m_size;
120 
121 #ifdef OGDF_DEBUG
122  const ConstCombinatorialEmbedding *m_pEmbedding;
123 #endif
124 
125 #ifdef OGDF_DEBUG
126  FaceElement(const ConstCombinatorialEmbedding *pEmbedding,
128  adjEntry adjFirst,
129  int id) :
130  m_id(id), m_size(0), m_pEmbedding(pEmbedding), entries(adjFirst) { }
131 #else
132  FaceElement(adjEntry adjFirst, int id) :
134  m_id(id), m_size(0), entries(adjFirst) { }
135 #endif
136 
137 public:
140 
142  int index() const { return m_id; }
143 
145  adjEntry firstAdj() const { return entries.m_adjFirst; }
146 
148  int size() const { return m_size; }
149 
151  face succ() const { return static_cast<face>(m_next); }
152 
154  face pred() const { return static_cast<face>(m_prev); }
155 
158  adj = adj->faceCycleSucc();
159  return (adj != entries.m_adjFirst) ? adj : nullptr;
160  }
161 
162 #ifdef OGDF_DEBUG
163  const ConstCombinatorialEmbedding *embeddingOf() const { return m_pEmbedding; }
164 #endif
165 
167  static int compare(const FaceElement& x, const FaceElement& y) { return x.m_id - y.m_id; }
169 
171 };
172 
173 class FaceArrayBase;
174 template<class T>class FaceArray;
175 
176 
199 {
200 protected:
201  const Graph *m_cpGraph;
202 
205 
208 
210 
211 #ifndef OGDF_MEMORY_POOL_NTS
212  mutable std::mutex m_mutexRegArrays;
213 #endif
214 
215 public:
218 
221 
226 
233  explicit ConstCombinatorialEmbedding(const Graph &G);
234 
235 
238 
241 
243  virtual ~ConstCombinatorialEmbedding();
244 
246  bool valid() const { return m_cpGraph != nullptr; }
247 
253  const Graph &getGraph() const {
254  OGDF_ASSERT(valid());
255  return *m_cpGraph;
256  }
257 
259  operator const Graph &() const { return getGraph(); }
260 
264  face firstFace() const { return faces.head(); }
265 
267  face lastFace() const { return faces.tail(); }
268 
270  int numberOfFaces() const { return faces.size(); }
271 
276  face rightFace(adjEntry adj) const { return m_rightFace[adj]; }
277 
282  face leftFace(adjEntry adj) const { return m_rightFace[adj->twin()]; }
283 
287  int maxFaceIndex() const { return m_faceIdCount-1; }
288 
290  int faceArrayTableSize() const { return m_faceArrayTableSize; }
291 
298  face chooseFace(std::function<bool(face)> includeFace = [](face) { return true; }, bool isFastTest = true) const;
299 
301  face maximalFace() const;
302 
306  face externalFace() const {
307  return m_externalFace;
308  }
309 
315  OGDF_ASSERT(f->embeddingOf() == this);
316  m_externalFace = f;
317  }
318 
319  bool isBridge(edge e) const {
320  return m_rightFace[e->adjSource()] == m_rightFace[e->adjTarget()];
321  }
322 
329  void init(const Graph &G);
330 
331  void init();
332 
334  void computeFaces();
335 
336 #ifdef OGDF_DEBUG
337  void consistencyCheck() const;
340 #endif
341 
342 
348  ListIterator<FaceArrayBase*> registerArray(FaceArrayBase *pFaceArray) const;
349 
355  void unregisterArray(ListIterator<FaceArrayBase*> it) const;
356 
358  void moveRegisterArray(ListIterator<FaceArrayBase*> it, FaceArrayBase *pFaceArray) const;
359 
369  adjEntry findCommonFace(const node v, const node w, bool left = true) const {
370  adjEntry adj;
371  return findCommonFace(v, w, adj, left);
372  }
373 
384  adjEntry findCommonFace(const node v, const node w, adjEntry &adjW, bool left = true) const;
385 
388 protected:
390  face createFaceElement(adjEntry adjFirst);
391 
393  void reinitArrays();
394 };
395 
410 {
411  friend class GraphCopy;
412 
414 
415  // the following methods are explicitly deleted
416  // It is not clear which meaning copying of a comb. embedding should
417  // have since we only store a pointer to the topology (Graph)
419  CombinatorialEmbedding &operator=(const CombinatorialEmbedding &) = delete;
420 
421 public:
426  m_pGraph = nullptr;
427  }
428 
436  m_pGraph = &G;
437  }
438 
440 
444 
446  const Graph &getGraph() const
447  {
448  OGDF_ASSERT(valid());
449  return *m_cpGraph;
450  }
451 
453  {
454  OGDF_ASSERT(valid());
455  return *m_pGraph;
456  }
457 
458  operator const Graph &() const { return getGraph(); }
459 
460  operator Graph &() { return getGraph(); }
461 
462 
464 
468 
475  void init(Graph &G) {
477  m_pGraph = &G;
478  }
479 
483  void clear();
484 
485 
487 
491 
497  edge split(edge e);
498 
504  void unsplit(edge eIn, edge eOut);
505 
524  node splitNode(adjEntry adjStartLeft, adjEntry adjStartRight);
525 
529  node contract(edge e, bool keepSelfLoops = false);
530 
550  edge splitFace(adjEntry adjSrc, adjEntry adjTgt, bool sourceAfter = false);
551 
560  edge addEdgeToIsolatedNode(node v, adjEntry adjTgt);
561 
570  edge addEdgeToIsolatedNode(adjEntry adjSrc, node v);
571 
577  face joinFaces(edge e);
578 
580  void reverseEdge(edge e);
581 
583  void moveBridge(adjEntry adjBridge, adjEntry adjBefore);
584 
586  void removeDeg1(node v);
587 
589  void updateMerger(edge e, face fRight, face fLeft);
590 
591 
594 private:
603  edge addEdgeToIsolatedNode(adjEntry adj, node v, bool adjSrc);
604 };
605 
606 }
ogdf::ConstCombinatorialEmbedding::m_regFaceArrays
ListPure< FaceArrayBase * > m_regFaceArrays
The external face.
Definition: CombinatorialEmbedding.h:209
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::ConstCombinatorialEmbedding::valid
bool valid() const
Returns whether the embedding is associated with a graph.
Definition: CombinatorialEmbedding.h:246
ogdf::ConstCombinatorialEmbedding::m_faceArrayTableSize
int m_faceArrayTableSize
The current table size of face arrays.
Definition: CombinatorialEmbedding.h:204
ogdf::internal::GraphList< GraphObject >::size
int size() const
Returns the size of the list.
Definition: GraphList.h:291
ogdf::internal::FaceAdjIterator::m_adjFirst
adjEntry m_adjFirst
Definition: CombinatorialEmbedding.h:53
ogdf::internal::FaceAdjContainer::begin
iterator begin() const
Definition: CombinatorialEmbedding.h:101
ogdf::internal::FaceAdjIterator::FaceAdjIterator
FaceAdjIterator(adjEntry adjFirst, adjEntry adj)
Definition: CombinatorialEmbedding.h:58
ogdf::internal::FaceAdjContainer::FaceAdjContainer
FaceAdjContainer()
Definition: CombinatorialEmbedding.h:95
ogdf::internal::FaceAdjContainer
Container for the adjacency entries in a face.
Definition: CombinatorialEmbedding.h:87
ogdf::internal::GraphList< GraphObject >::tail
GraphObject * tail() const
Returns the last element in the list.
Definition: GraphList.h:297
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::internal::GraphIteratorBase
Definition: graph_iterators.h:42
ogdf::FaceElement::m_size
int m_size
The size of the face.
Definition: CombinatorialEmbedding.h:119
ogdf::ConstCombinatorialEmbedding::findCommonFace
adjEntry findCommonFace(const node v, const node w, bool left=true) const
Identifies a common face of two nodes and returns the respective adjacency entry.
Definition: CombinatorialEmbedding.h:369
ogdf::internal::FaceAdjContainer::end
iterator end() const
Definition: CombinatorialEmbedding.h:102
ogdf::internal::GraphElement
The base class for objects used by (hyper)graphs.
Definition: GraphList.h:55
ogdf::ConstCombinatorialEmbedding::leftFace
face leftFace(adjEntry adj) const
Returns the face to the left of adj, i.e., the face containing the twin of adj.
Definition: CombinatorialEmbedding.h:282
ogdf::ConstCombinatorialEmbedding::m_faceIdCount
int m_faceIdCount
The index assigned to the next created face.
Definition: CombinatorialEmbedding.h:203
OGDF_AUGMENT_COMPARER
#define OGDF_AUGMENT_COMPARER(type)
Add this macro to your class to turn it into a full comparer.
Definition: comparer.h:157
ogdf::ConstCombinatorialEmbedding::m_mutexRegArrays
std::mutex m_mutexRegArrays
The critical section for protecting shared acces to register/unregister methods.
Definition: CombinatorialEmbedding.h:212
ogdf::CombinatorialEmbedding::getGraph
Graph & getGraph()
Definition: CombinatorialEmbedding.h:452
ogdf::FaceElement::entries
internal::FaceAdjContainer entries
Container maintaining the adjacency entries in the face.
Definition: CombinatorialEmbedding.h:139
ogdf::ConstCombinatorialEmbedding::rightFace
face rightFace(adjEntry adj) const
Returns the face to the right of adj, i.e., the face containing adj.
Definition: CombinatorialEmbedding.h:276
ogdf::internal::FaceAdjIterator::operator++
FaceAdjIterator & operator++()
Definition: CombinatorialEmbedding.h:72
ogdf::ConstCombinatorialEmbedding::numberOfFaces
int numberOfFaces() const
Returns the number of faces.
Definition: CombinatorialEmbedding.h:270
ogdf::GraphCopy
Copies of graphs supporting edge splitting.
Definition: GraphCopy.h:255
ogdf::ConstCombinatorialEmbedding::lastFace
face lastFace() const
Returns the last face in the list of all faces.
Definition: CombinatorialEmbedding.h:267
ogdf::internal::FaceAdjIterator::FaceAdjIterator
FaceAdjIterator(adjEntry adj)
Definition: CombinatorialEmbedding.h:57
ogdf::internal::GraphObjectContainer
Definition: GraphList.h:390
ogdf::ConstCombinatorialEmbedding::maxFaceIndex
int maxFaceIndex() const
Returns the largest used face index.
Definition: CombinatorialEmbedding.h:287
ogdf::AdjElement::twin
adjEntry twin() const
Returns the corresponding adjacency element associated with the same edge.
Definition: Graph_d.h:105
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::FaceElement::firstAdj
adjEntry firstAdj() const
Returns the first adjacency element in the face.
Definition: CombinatorialEmbedding.h:145
ogdf::ConstCombinatorialEmbedding::setExternalFace
void setExternalFace(face f)
Sets the external face to f.
Definition: CombinatorialEmbedding.h:314
ogdf::ConstCombinatorialEmbedding::init
void init()
ogdf::FaceElement::compare
static int compare(const FaceElement &x, const FaceElement &y)
Standard Comparer.
Definition: CombinatorialEmbedding.h:167
ogdf::internal::FaceAdjIterator::operator*
adjEntry operator*() const
Definition: CombinatorialEmbedding.h:70
ogdf::ConstCombinatorialEmbedding::faces
internal::GraphObjectContainer< FaceElement > faces
The container containing all face objects.
Definition: CombinatorialEmbedding.h:220
ogdf::internal::FaceAdjIterator::m_adj
adjEntry m_adj
Definition: CombinatorialEmbedding.h:52
ogdf::CombinatorialEmbedding::init
void init(Graph &G)
Initializes the embedding for graph G.
Definition: CombinatorialEmbedding.h:475
ogdf::FaceArray
Dynamic arrays indexed with faces of a combinatorial embedding.
Definition: CombinatorialEmbedding.h:174
ogdf::ConstCombinatorialEmbedding::m_rightFace
AdjEntryArray< face > m_rightFace
The face to which an adjacency entry belongs.
Definition: CombinatorialEmbedding.h:206
ogdf::FaceElement::m_id
int m_id
The index of the face.
Definition: CombinatorialEmbedding.h:118
ogdf::operator<<
std::ostream & operator<<(std::ostream &os, const ogdf::Array< E, INDEX > &a)
Prints array a to output stream os.
Definition: Array.h:949
ogdf::ConstCombinatorialEmbedding::m_cpGraph
const Graph * m_cpGraph
The associated graph.
Definition: CombinatorialEmbedding.h:201
ogdf::ConstCombinatorialEmbedding::getGraph
const Graph & getGraph() const
Returns the associated graph of the combinatorial embedding.
Definition: CombinatorialEmbedding.h:253
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::FaceArrayBase
Abstract base class for face arrays.
Definition: FaceArray.h:47
ogdf::internal::GraphList
Lists of graph objects (like nodes, edges, etc.).
Definition: GraphList.h:277
ogdf::ConstCombinatorialEmbedding::firstFace
face firstFace() const
Returns the first face in the list of all faces.
Definition: CombinatorialEmbedding.h:264
ogdf::CombinatorialEmbedding::m_pGraph
Graph * m_pGraph
The associated graph.
Definition: CombinatorialEmbedding.h:413
ogdf::FaceElement::size
int size() const
Returns the size of the face, i.e., the number of edges in the face.
Definition: CombinatorialEmbedding.h:148
ogdf::internal::FaceAdjIterator
Forward iterator for adjacency entries in a face.
Definition: CombinatorialEmbedding.h:50
ogdf::ConstCombinatorialEmbedding::externalFace
face externalFace() const
Returns the external face.
Definition: CombinatorialEmbedding.h:306
ogdf::ListPure
Doubly linked lists.
Definition: List.h:41
ogdf::ConstCombinatorialEmbedding
Combinatorial embeddings of planar graphs.
Definition: CombinatorialEmbedding.h:198
ogdf::FaceElement::pred
face pred() const
Returns the predecessor in the list of all faces.
Definition: CombinatorialEmbedding.h:154
ogdf::FaceElement::index
int index() const
Returns the index of the face.
Definition: CombinatorialEmbedding.h:142
ogdf::EdgeElement::adjTarget
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition: Graph_d.h:335
ogdf::internal::FaceAdjContainer::iterator
FaceAdjIterator iterator
Definition: CombinatorialEmbedding.h:99
ogdf::ConstCombinatorialEmbedding::m_externalFace
face m_externalFace
Definition: CombinatorialEmbedding.h:207
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::internal::GraphList< GraphObject >::head
GraphObject * head() const
Returns the first element in the list.
Definition: GraphList.h:294
ogdf::face
FaceElement * face
Definition: CombinatorialEmbedding.h:40
ogdf::internal::FaceAdjContainer::FaceAdjContainer
FaceAdjContainer(adjEntry adjFirst)
Definition: CombinatorialEmbedding.h:96
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::internal::FaceAdjContainer::m_adjFirst
adjEntry m_adjFirst
Definition: CombinatorialEmbedding.h:93
ogdf::CombinatorialEmbedding
Combinatorial embeddings of planar graphs with modification functionality.
Definition: CombinatorialEmbedding.h:409
ogdf::ConstCombinatorialEmbedding::faceArrayTableSize
int faceArrayTableSize() const
Returns the table size of face arrays associated with this embedding.
Definition: CombinatorialEmbedding.h:290
ogdf::AdjElement::faceCycleSucc
adjEntry faceCycleSucc() const
Returns the cyclic successor in face.
Definition: Graph_d.h:142
AdjEntryArray.h
Declaration and implementation of AdjEntryArray class.
ogdf::internal::FaceAdjIterator::FaceAdjIterator
FaceAdjIterator()
Definition: CombinatorialEmbedding.h:56
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::CombinatorialEmbedding::getGraph
const Graph & getGraph() const
Returns the associated graph.
Definition: CombinatorialEmbedding.h:446
ogdf::ConstCombinatorialEmbedding::isBridge
bool isBridge(edge e) const
Definition: CombinatorialEmbedding.h:319
ogdf::internal::FaceAdjIterator::operator!=
bool operator!=(const FaceAdjIterator &other) const
Definition: CombinatorialEmbedding.h:66
ogdf::ListIteratorBase
Encapsulates a pointer to a list element.
Definition: List.h:42
ogdf::internal::FaceAdjIterator::operator=
FaceAdjIterator & operator=(const FaceAdjIterator &)=default
ogdf::FaceElement::nextFaceEdge
adjEntry nextFaceEdge(adjEntry adj) const
Returns the successor of adj in the list of all adjacency elements in the face.
Definition: CombinatorialEmbedding.h:157
ogdf::internal::FaceAdjIterator::operator==
bool operator==(const FaceAdjIterator &other) const
Definition: CombinatorialEmbedding.h:62
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::AdjEntryArray
Dynamic arrays indexed with adjacency entries.
Definition: AdjEntryArray.h:114
ogdf::CombinatorialEmbedding::CombinatorialEmbedding
CombinatorialEmbedding(Graph &G)
Creates a combinatorial embedding of graph G.
Definition: CombinatorialEmbedding.h:435
ogdf::FaceElement
Faces in a combinatorial embedding.
Definition: CombinatorialEmbedding.h:111
ogdf::FaceElement::succ
face succ() const
Returns the successor in the list of all faces.
Definition: CombinatorialEmbedding.h:151
ogdf::CombinatorialEmbedding::CombinatorialEmbedding
CombinatorialEmbedding()
Creates a combinatorial embedding associated with no graph.
Definition: CombinatorialEmbedding.h:425