Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

OrthoRep.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <ogdf/basic/GraphCopy.h>
35 #include <ogdf/basic/FaceArray.h>
36 #include <ogdf/basic/tuples.h>
37 
38 
39 namespace ogdf {
40 
41 class OGDF_EXPORT PlanRep;
42 class OGDF_EXPORT PlanRepUML;
43 
44 
45 // type for bends (convex or reflex)
46 enum class OrthoBendType : char { convexBend = '0', reflexBend = '1' };
47 
48 // type of (orthogonal) directions
49 // horizontal: East or West
50 // vertical: North or South
51 enum class OrthoDir {
52  North = 0,
53  East = 1,
54  South = 2,
55  West = 3,
56  Undefined = 4
57 };
58 
59 // Option bits for orthogonal layouts, UML alignment, compaction scaling, progressive shape computation
60 enum class UMLOpt {OpAlign = 0x0001, OpScale = 0x0002, OpProg = 0x0004};
61 
62 inline int operator | (int lhs, UMLOpt rhs) { return lhs | static_cast<int>(rhs); }
63 inline int operator ~ (UMLOpt rhs) { return ~static_cast<int>(rhs); }
64 inline int operator & (int lhs, UMLOpt rhs) { return lhs & static_cast<int>(rhs); }
65 inline int operator += (int &lhs, UMLOpt rhs) { lhs += static_cast<int>(rhs); return lhs; }
66 
69 {
70 public:
71  // constructs empty bend string
73  m_pBend = nullptr;
74  m_len = 0;
75  }
76 
77  // constructs bend string as given by str
78  // Precond.: str is a 0 terminated C++ string consisting of '0's and '1's
79  explicit BendString(const char *str) {
80  init(str);
81  }
82 
83  // constructs bend string consisting of n c's
84  // Precond.: c is '0' or '1'
85  BendString(char c, size_t n) {
86  init(c,n);
87  }
88 
89  // copy constructor
90  BendString(const BendString &bs) {
91  init(bs);
92  }
93 
94  // copy constructor (move semantics)
95  BendString(BendString &&bs) : m_pBend(bs.m_pBend), m_len(bs.m_len) {
96  bs.m_pBend = nullptr;
97  bs.m_len = 0;
98  }
99 
100 
101  // destructor
103  delete[] m_pBend;
104  }
105 
106 
107  // returns i'th character in bend string
108  char operator[](size_t i) const {
109  // range check
110  OGDF_ASSERT(i < m_len);
111  return m_pBend[i];
112  }
113 
114  char &operator[](size_t i) {
115  // range check
116  OGDF_ASSERT(i < m_len);
117  return m_pBend[i];
118  }
119 
120  // returns number of characters in bend string
121  size_t size() const {
122  return m_len;
123  }
124 
125  // returns a pointer to the 0 terminated string
126  // or a 0-pointer if empty
127  const char *toString() const {
128  return m_pBend;
129  }
130 
131  // sets bend string to the string given by str
132  // Precond.: str is a 0 terminated C++ string consisting of '0's and '1's
133  void set(const char *str) {
134  delete[] m_pBend;
135  init(str);
136  }
137 
138  // sets bend string to the string consisting of n c's
139  // Precond.: c is '0' or '1'
140  void set(char c, size_t n) {
141  delete[] m_pBend;
142  init(c,n);
143  }
144  void set(OrthoBendType obt, size_t n) {
145  delete[] m_pBend;
146  init(static_cast<int>(obt),n);
147  }
148 
149 
150  // sets bend string to the empty bend string
151  void set() {
152  delete[] m_pBend;
153  m_pBend = nullptr;
154  m_len = 0;
155  }
156 
157 
158  // assignment operator
160  delete[] m_pBend;
161  init(bs);
162  return *this;
163  }
164 
165  // assignment operator (move semantics)
167  if (&bs != this) {
168  delete[] m_pBend;
169  m_pBend = bs.m_pBend;
170  m_len = bs.m_len;
171  bs.m_pBend = nullptr;
172  bs.m_len = 0;
173  }
174  return *this;
175  }
176 
177  BendString &operator+=(const char *str) {
178  return this->operator+=(BendString(str));
179  }
180 
182  char* temp = new char[m_len+bs.m_len+1];
183 
184  m_len = m_len + bs.m_len;
185 
186  if (m_len == 0)
187  {
188  *temp = 0;//temp = 0;
189  }
190  else
191  {
192  char *p = temp;
193  if (m_pBend != nullptr)
194  {
195  const char *str = m_pBend;
196  while ((*p++ = *str++) != 0) ;
197  }
198  else {*p = '0'; p++;}
199  if (bs.m_len > 0)
200  {
201  p--;
202  const char *str1 = bs.m_pBend;
203  while ((*p++ = *str1++) != 0) ;
204  }
205  }
206 
207  delete[] m_pBend;
208  m_pBend = temp;
209 
210  return *this;
211  }
212 
213  // output operator
214  // example output: "001101001" or ""
215  friend std::ostream &operator<<(std::ostream &os, const BendString &bs) {
216  if (bs.size() == 0)
217  os << "\"\"";
218  else
219  os << "\"" << bs.m_pBend << "\"";
220  return os;
221  }
222 
223 private:
224  void init(const char *str);
225  void init(char c, size_t n);
226  void init(const BendString &bs);
227 
228 
229  // poiner to 0 terminated character string
230  char *m_pBend;
231  // length of string (number of characters without ending 0)
232  size_t m_len;
233 };
234 
237 {
238 public:
240  struct SideInfoUML {
241  // adjacency entry of generalization attached at the side
242  // (or 0 if none)
244  // number of attached edges which have corresponding edges in the
245  // original graph to the left (index 0) or right of the
246  // attached generalization. If no generalization is attached,
247  // m_nAttached[0] is the total number of attached edges.
248  int m_nAttached[2];
249 
250  // constructor
252  m_adjGen = nullptr;
253  m_nAttached[0] = m_nAttached[1] = 0;
254  }
255 
256  // returns the total number of edges attached at this side
257  int totalAttached() const {
258  int nGen = (m_adjGen == nullptr) ? 0 : 1;
259  return nGen + m_nAttached[0] + m_nAttached[1];
260  }
261 
262 
263  // output operator for debugging
264  friend std::ostream &operator<<(std::ostream &os, const SideInfoUML &si)
265  {
266  os << "{ " << si.m_nAttached[0] <<
267  ", " << si.m_adjGen <<
268  ", " << si.m_nAttached[1] << " }";
269  return os;
270  }
271  };
272 
273  //only for debugging purposes
274  adjEntry externalAdjEntry() const {return m_adjExternal;}
275  adjEntry alignAdjEntry() const {return m_adjAlign;}
276 
278  struct VertexInfoUML {
279  // side information (North, East, South, West corresponds to
280  // left, top, right, bottom)
281  SideInfoUML m_side[4];
282  // m_corner[dir] is adjacency entry in direction dir starting at
283  // a corner
284  adjEntry m_corner[4];
285 
286  // constructor
288 #ifdef OGDF_DEBUG
289  m_corner[0] = m_corner[1] = m_corner[2] = m_corner[3] = nullptr;
290 #endif
291  }
293  };
294 
295 
296  // construction
297 
298  // dummy
299  OrthoRep() { m_pE = nullptr; }
300  // associates orthogonal representation with embedding E
301  explicit OrthoRep(CombinatorialEmbedding &E);
302 
303  // destruction
305  freeCageInfoUML();
306  }
307 
308  // reinitialization: associates orthogonal representation with embedding E
309  void init(CombinatorialEmbedding &E);
310 
311 
312  //
313  // access functions
314  //
315 
316  // returns associated embedding
317  operator const CombinatorialEmbedding &() const {
318  return *m_pE;
319  }
320 
321  // returns associated graph
322  operator const Graph &() const {
323  return *m_pE;
324  }
325 
326  // returns angle between adj and its successor
327  // (return value is angle divided by 90 degree)
328  int angle(adjEntry adj) const {
329  return m_angle[adj];
330  }
331 
332  int &angle(adjEntry adj) {
333  return m_angle[adj];
334  }
335 
336 
337  // returns bend string of adjacency entry adj
338  const BendString &bend(adjEntry adj) const {
339  return m_bends[adj];
340  }
341 
343  return m_bends[adj];
344  }
345 
346  // returns direction of adjacency entry
348  return m_dir[adj];
349  }
350 
351 
352  // returns cage info
353  const VertexInfoUML *cageInfo(node v) const {
354  return m_umlCageInfo[v];
355  }
356 
357  // returns cage info
359  return m_umlCageInfo[v];
360  }
361 
362 
363 
364  //
365  // update functions
366  //
367 
368  // normalizes the orthogonal representation, i.e., sets an artficial
369  // vertex on each bend
370  void normalize();
371 
372  // checks if the orth. repr. is normalized, i.e., each bend string is empty
373  bool isNormalized() const;
374 
375  // removes rectangular ears (pattern "100") by splitting edges and faces.
376  // Afterwards, each internal face is a rectangle and the external face
377  // contains no rectangular ear (but is not necessarily the complement of
378  // a rectangle).
379  // Precond.: The orth. repr. is normalized and contains no 0-degree angles
380  void dissect();
381  // same as dissect, attempting to save artificial nodes and allow preprocessing
382  void dissect2(PlanRep* PG = nullptr);
383  // variant for use with simple PlanRep
384  void gridDissect(PlanRep* PG);
385  // undoes a previous dissect() by removing dissection edges and unsplitting
386  // vertices
387  void undissect(bool align = false);
388 
389 
390  // assigns consistent directions to adjacency entries
391  void orientate();
392 
393  // assigns consistent directions to adj. entries such that most
394  // generalizations are directed in preferedDir
395  void orientate(const PlanRep &PG, OrthoDir preferedDir);
396 
397  // assigns consistent directions to adjacency entries,
398  // assigning dir to adj (fixing all others)
399  void orientate(adjEntry adj, OrthoDir dir);
400 
401  // returns true iff orientate() has been called before.
402  // If not, direction() may not be called since adj. entry array is not
403  // initialized!
404  bool isOrientated() const {
405  return m_dir.valid();
406  }
407 
408 
409  // rotates all directions of adjacency entries by r
410  void rotate(int r);
411 
412 
413  // computes further information about cages
414  void computeCageInfoUML(const PlanRep &PG/*, double sep*/);
415 
416 
417  // checks if the orth. repr. is a legal shape description, i.e., if there
418  // is an orthogonal embedding realizing this shape (if 0-degree angles are
419  // present, the condition is necessary but not sufficient).
420  // If false is returned, error contains a description of the reason.
421  bool check(string &error) const;
422 
423 
424  //
425  // static members
426  //
427 
428  // exchanges '1'->'0' and vice versa
429  static char flip(char c) {
430  return (c == '0') ? '1' : '0';
431  }
432 
435  return static_cast<OrthoDir>((static_cast<int>(d) + 2) & 3);
436  }
437 
440  return static_cast<OrthoDir>((static_cast<int>(d) + 1) & 3);
441  }
442 
445  return static_cast<OrthoDir>((static_cast<int>(d) + 3) & 3);
446  }
447 
448  friend std::ostream &operator<<(std::ostream &os, const OrthoRep &op) {
449  const Graph& E = op;
450  for(edge e : E.edges)
451  {
452  os << e <<": src angle "<<op.angle(e->adjSource())<<" bend "<<op.bend(e->adjSource())
453  <<"\n"<<" tgt angle "<<op.angle(e->adjTarget())<<" bend "<<op.bend(e->adjTarget())
454 
455  <<"\n";
456  }
457  return os;
458  }
459 
460 
461 
462 private:
463  void orientateFace(adjEntry adj, OrthoDir dir);
464  void freeCageInfoUML();
465 
466  // associated combinatorial embedding
468 
469  // * 90 deg = angle between e and its successor
471  // bends on edge e
473  // direction of adjacency entries
475 
476  // information about cages of original vertices; used for orthogonal
477  // representations of PlanRep's
479 
480  // The following members are used for undoing dissection
481  EdgeArray<bool> m_dissectionEdge; // = true iff dissection edge
482  //check if special gener. sons alignment edge
483  EdgeArray<bool> m_alignmentEdge; // = true iff alignment edge
484  // contains all nodes created by splitting non-dissection edges while
485  // dissect()
487  // stores adjacency entry on external face for restoring in undissect()
489  // stores adjacency entry on preliminary external face in alignment case
491  //starts dissection phase for special pattern 1 replacement before standard dissection
493  //special pattern after pattern 1
495 };
496 
497 }
ogdf::ArrayBuffer
An array that keeps track of the number of inserted elements; also usable as an efficient stack.
Definition: Array.h:45
ogdf::OrthoRep::m_adjAlign
adjEntry m_adjAlign
Definition: OrthoRep.h:490
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::BendString::BendString
BendString(const BendString &bs)
Definition: OrthoRep.h:90
ogdf::OrthoRep::m_dir
AdjEntryArray< OrthoDir > m_dir
Definition: OrthoRep.h:474
ogdf::PlanRep
Planarized representations (of a connected component) of a graph.
Definition: PlanRep.h:59
ogdf::OrthoRep::angle
int & angle(adjEntry adj)
Definition: OrthoRep.h:332
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::BendString::BendString
BendString()
Definition: OrthoRep.h:72
ogdf::OrthoRep::VertexInfoUML
Further information about the cages of vertices in UML diagrams.
Definition: OrthoRep.h:278
ogdf::OrthoRep::angle
int angle(adjEntry adj) const
Definition: OrthoRep.h:328
ogdf::OrthoDir
OrthoDir
Definition: OrthoRep.h:51
ogdf::operator+=
int operator+=(int &lhs, UMLOpt rhs)
Definition: OrthoRep.h:65
ogdf::OrthoRep::cageInfo
VertexInfoUML * cageInfo(node v)
Definition: OrthoRep.h:358
ogdf::BendString::BendString
BendString(const char *str)
Definition: OrthoRep.h:79
ogdf::BendString::m_pBend
char * m_pBend
Definition: OrthoRep.h:230
ogdf::OrthoDir::West
@ West
ogdf::OrthoRep::SideInfoUML::m_adjGen
adjEntry m_adjGen
Definition: OrthoRep.h:243
ogdf::BendString
Represents the bends on an edge e consisting of vertical and horizontal segments.
Definition: OrthoRep.h:68
ogdf::BendString::operator=
BendString & operator=(const BendString &bs)
Definition: OrthoRep.h:159
ogdf::OrthoRep::m_alignmentEdge
EdgeArray< bool > m_alignmentEdge
Definition: OrthoRep.h:483
ogdf::OrthoRep::SideInfoUML
Information about a side of a vertex in UML diagrams.
Definition: OrthoRep.h:240
ogdf::BendString::size
size_t size() const
Definition: OrthoRep.h:121
ogdf::OrthoDir::South
@ South
ogdf::OrthoBendType::convexBend
@ convexBend
ogdf::OrthoRep::m_umlCageInfo
NodeArray< VertexInfoUML * > m_umlCageInfo
Definition: OrthoRep.h:478
ogdf::operator&
int operator&(int lhs, UMLOpt rhs)
Definition: OrthoRep.h:64
ogdf::OrthoRep::m_pE
CombinatorialEmbedding * m_pE
Definition: OrthoRep.h:467
ogdf::BendString::operator+=
BendString & operator+=(const char *str)
Definition: OrthoRep.h:177
ogdf::OrthoRep::m_dissectionEdge
EdgeArray< bool > m_dissectionEdge
Definition: OrthoRep.h:481
FaceArray.h
declaration and implementation of FaceArray class
ogdf::NodeArray
Dynamic arrays indexed with nodes.
Definition: Graph_d.h:441
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::EdgeArray< bool >
ogdf::OrthoDir::Undefined
@ Undefined
ogdf::operator~
int operator~(UMLOpt rhs)
Definition: OrthoRep.h:63
ogdf::AdjElement
Class for adjacency list elements.
Definition: Graph_d.h:79
ogdf::BendString::set
void set()
Definition: OrthoRep.h:151
ogdf::BendString::set
void set(const char *str)
Definition: OrthoRep.h:133
ogdf::BendString::operator+=
BendString & operator+=(const BendString &bs)
Definition: OrthoRep.h:181
ogdf::BendString::operator[]
char & operator[](size_t i)
Definition: OrthoRep.h:114
ogdf::BendString::set
void set(OrthoBendType obt, size_t n)
Definition: OrthoRep.h:144
ogdf::OrthoRep::flip
static char flip(char c)
Definition: OrthoRep.h:429
ogdf::BendString::~BendString
~BendString()
Definition: OrthoRep.h:102
r
int r[]
Definition: hierarchical-ranking.cpp:8
ogdf::OrthoBendType::reflexBend
@ reflexBend
ogdf::OrthoRep::m_splitNodes
ArrayBuffer< node > m_splitNodes
Definition: OrthoRep.h:486
ogdf::OrthoRep
Orthogonal representation of an embedded graph.
Definition: OrthoRep.h:236
ogdf::OrthoRep::SideInfoUML::SideInfoUML
SideInfoUML()
Definition: OrthoRep.h:251
ogdf::UMLOpt::OpAlign
@ OpAlign
ogdf::OrthoRep::m_bends
AdjEntryArray< BendString > m_bends
Definition: OrthoRep.h:472
ogdf::OrthoBendType
OrthoBendType
Definition: OrthoRep.h:46
ogdf::OrthoRep::nextDir
static OrthoDir nextDir(OrthoDir d)
Returns the next OrthoDir (in a clockwise manner)
Definition: OrthoRep.h:439
ogdf::OrthoRep::cageInfo
const VertexInfoUML * cageInfo(node v) const
Definition: OrthoRep.h:353
GraphCopy.h
Declaration of graph copy classes.
ogdf::OrthoRep::SideInfoUML::m_nAttached
int m_nAttached[2]
Definition: OrthoRep.h:248
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::OrthoRep::alignAdjEntry
adjEntry alignAdjEntry() const
Definition: OrthoRep.h:275
ogdf::BendString::BendString
BendString(char c, size_t n)
Definition: OrthoRep.h:85
ogdf::OrthoRep::m_pattern2
bool m_pattern2
Definition: OrthoRep.h:494
ogdf::OrthoRep::bend
BendString & bend(adjEntry adj)
Definition: OrthoRep.h:342
ogdf::OrthoRep::oppDir
static OrthoDir oppDir(OrthoDir d)
Returns the opposite OrthoDir.
Definition: OrthoRep.h:434
ogdf::BendString::operator[]
char operator[](size_t i) const
Definition: OrthoRep.h:108
ogdf::OrthoRep::~OrthoRep
~OrthoRep()
Definition: OrthoRep.h:304
ogdf::BendString::toString
const char * toString() const
Definition: OrthoRep.h:127
ogdf::EdgeElement::adjTarget
adjEntry adjTarget() const
Returns the corresponding adjacancy entry at target node.
Definition: Graph_d.h:335
ogdf::OrthoRep::VertexInfoUML::VertexInfoUML
VertexInfoUML()
Definition: OrthoRep.h:287
ogdf::OrthoRep::SideInfoUML::totalAttached
int totalAttached() const
Definition: OrthoRep.h:257
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::OrthoRep::m_angle
AdjEntryArray< int > m_angle
Definition: OrthoRep.h:470
ogdf::OrthoRep::SideInfoUML::operator<<
friend std::ostream & operator<<(std::ostream &os, const SideInfoUML &si)
Definition: OrthoRep.h:264
ogdf::Graph::edges
internal::GraphObjectContainer< EdgeElement > edges
The container containing all edge objects.
Definition: Graph_d.h:571
ogdf::OrthoRep::m_preprocess
bool m_preprocess
Definition: OrthoRep.h:492
ogdf::UMLOpt
UMLOpt
Definition: OrthoRep.h:60
ogdf::BendString::operator<<
friend std::ostream & operator<<(std::ostream &os, const BendString &bs)
Definition: OrthoRep.h:215
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::OrthoRep::externalAdjEntry
adjEntry externalAdjEntry() const
Definition: OrthoRep.h:274
ogdf::CombinatorialEmbedding
Combinatorial embeddings of planar graphs with modification functionality.
Definition: CombinatorialEmbedding.h:409
ogdf::OrthoDir::East
@ East
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ogdf::OrthoRep::operator<<
friend std::ostream & operator<<(std::ostream &os, const OrthoRep &op)
Definition: OrthoRep.h:448
ogdf::BendString::BendString
BendString(BendString &&bs)
Definition: OrthoRep.h:95
ogdf::OrthoRep::isOrientated
bool isOrientated() const
Definition: OrthoRep.h:404
ogdf::OrthoRep::bend
const BendString & bend(adjEntry adj) const
Definition: OrthoRep.h:338
ogdf::BendString::m_len
size_t m_len
Definition: OrthoRep.h:232
ogdf::OrthoRep::m_adjExternal
adjEntry m_adjExternal
Definition: OrthoRep.h:488
ogdf::UMLOpt::OpScale
@ OpScale
ogdf::OrthoDir::North
@ North
ogdf::OrthoRep::prevDir
static OrthoDir prevDir(OrthoDir d)
Returns the previous OrthoDir (in a clockwise manner)
Definition: OrthoRep.h:444
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
tuples.h
Declaration and implementation of class Tuple2, Tuple3 and Tuple4.
ogdf::UMLOpt::OpProg
@ OpProg
ogdf::operator|
int operator|(int lhs, UMLOpt rhs)
Definition: OrthoRep.h:62
ogdf::AdjEntryArray< int >
ogdf::OrthoRep::direction
OrthoDir direction(adjEntry adj) const
Definition: OrthoRep.h:347
ogdf::OrthoRep::OrthoRep
OrthoRep()
Definition: OrthoRep.h:299
ogdf::BendString::set
void set(char c, size_t n)
Definition: OrthoRep.h:140
ogdf::BendString::operator=
BendString & operator=(BendString &&bs)
Definition: OrthoRep.h:166