Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

ExtendedNestingGraph.h
Go to the documentation of this file.
1 
34 #pragma once
35 
37 #include <ogdf/basic/EdgeArray.h>
39 
40 namespace ogdf {
41 
43 {
45  m_cnClusters = 0;
46  m_cnEdges = 0;
47  }
48 
49  RCCrossings(int cnClusters, int cnEdges) {
50  m_cnClusters = cnClusters;
51  m_cnEdges = cnEdges;
52  }
53 
54  void incEdges(int cn) {
55  m_cnEdges += cn;
56  }
57 
58  void incClusters() {
59  ++m_cnClusters;
60  }
61 
63  m_cnClusters += cr.m_cnClusters;
64  m_cnEdges += cr.m_cnEdges;
65  return *this;
66  }
67 
68  RCCrossings operator+(const RCCrossings &cr) const {
69  return RCCrossings(m_cnClusters+cr.m_cnClusters, m_cnEdges+cr.m_cnEdges);
70  }
71 
72  RCCrossings operator-(const RCCrossings &cr) const {
73  return RCCrossings(m_cnClusters-cr.m_cnClusters, m_cnEdges-cr.m_cnEdges);
74  }
75 
76  bool operator<=(const RCCrossings &cr) const {
77  if(m_cnClusters == cr.m_cnClusters)
78  return m_cnEdges <= cr.m_cnEdges;
79  else
80  return m_cnClusters <= cr.m_cnClusters;
81  }
82 
83  bool operator<(const RCCrossings &cr) const {
84  if(m_cnClusters == cr.m_cnClusters)
85  return m_cnEdges < cr.m_cnEdges;
86  else
87  return m_cnClusters < cr.m_cnClusters;
88  }
89 
90  bool isZero() const {
91  return m_cnClusters == 0 && m_cnEdges == 0;
92  }
93 
95  m_cnClusters = m_cnEdges = std::numeric_limits<int>::max();
96  return *this;
97  }
98 
99  static int compare(const RCCrossings &x, const RCCrossings &y)
100  {
101  int dc = y.m_cnClusters - x.m_cnClusters;
102  if(dc != 0)
103  return dc;
104  return y.m_cnEdges - x.m_cnEdges;
105  }
106 
109 };
110 
111 OGDF_EXPORT std::ostream& operator<<(std::ostream &os, const RCCrossings &cr);
112 
114 {
115 public:
116  enum class Type { Compound, Node, AuxNode };
117 
118  struct Adjacency
119  {
120  Adjacency() { m_u = nullptr; m_v = nullptr; m_weight = 0; }
121  Adjacency(node u, LHTreeNode *vNode, int weight = 1) {
122  m_u = u;
123  m_v = vNode;
124  m_weight = weight;
125  }
126 
129  int m_weight;
130 
132  };
133 
135  {
136  ClusterCrossing() { m_uc = nullptr; m_u = nullptr; m_cNode = nullptr; m_uNode = nullptr; }
137  ClusterCrossing(node uc, LHTreeNode *cNode, node u, LHTreeNode *uNode, edge e) {
138  m_uc = uc;
139  m_u = u;
140  m_cNode = cNode;
141  m_uNode = uNode;
142 
143  m_edge = e;
144  }
145 
150 
152  };
153 
154  // Construction
156  m_parent = nullptr;
157  m_origCluster = c;
158  m_node = nullptr;
159  m_type = Type::Compound;
160  m_down = nullptr;
161 
162  m_up = up;
163  if(up)
164  up->m_down = this;
165  }
166 
167  LHTreeNode(LHTreeNode *parent, node v, Type t = Type::Node) {
168  m_parent = parent;
169  m_origCluster = nullptr;
170  m_node = v;
171  m_type = t;
172  m_up = nullptr;
173  m_down = nullptr;
174  }
175 
176  // Access functions
177  bool isCompound() const { return m_type == Type::Compound; }
178 
179  int numberOfChildren() const { return m_child.size(); }
180 
181  const LHTreeNode *parent() const { return m_parent; }
182  const LHTreeNode *child(int i) const { return m_child[i]; }
183 
184  cluster originalCluster() const { return m_origCluster; }
185  node getNode() const { return m_node; }
186 
187  const LHTreeNode *up () const { return m_up; }
188  const LHTreeNode *down() const { return m_down; }
189 
190  int pos() const { return m_pos; }
191 
192 
193  // Modification functions
194  LHTreeNode *parent() { return m_parent; }
195  void setParent(LHTreeNode *p) { m_parent = p; }
196 
197  LHTreeNode *child(int i) { return m_child[i]; }
198  void initChild(int n) { m_child.init(n); }
199  void setChild(int i, LHTreeNode *p) { m_child[i] = p; }
200 
201  void setPos();
202 
203  void store() { m_storedChild = m_child; }
204  void restore() { m_child = m_storedChild; }
205  void permute() { m_child.permute(); }
206 
207  void removeAuxChildren();
208 
213 
214 private:
216 
220 
223 
226  int m_pos;
227 
229 };
230 
233 {
234 public:
235  ENGLayer() { m_root = nullptr; }
236  ~ENGLayer();
237 
238  const LHTreeNode *root() const { return m_root; }
239  LHTreeNode *root() { return m_root; }
240 
241  void setRoot(LHTreeNode *r) { m_root = r; }
242 
243  void store();
244  void restore();
245  void permute();
246 
247  void simplifyAdjacencies();
248  void removeAuxNodes();
249 
250 private:
251  void simplifyAdjacencies(List<LHTreeNode::Adjacency> &adjs);
252 
254 };
255 
257 
259 {
260 public:
261 
264 
265  void init(const ExtendedNestingGraph &H, const ClusterGraph &CG);
266 
267  const ClusterGraph &getOriginalClusterGraph() const { return *m_pCG; }
268 
269  cluster copy(cluster cOrig) const { return m_copy[cOrig]; }
270  cluster original(cluster cCopy) const { return m_original[cCopy]; }
271 
272  void setParent(node v, cluster c);
273 
274 private:
275  void createClusterTree(cluster cOrig);
276 
279 
282 };
283 
285 {
286 public:
287  // the type of a node in this copy
288  enum class NodeType { Node, ClusterTop, ClusterBottom, Dummy, ClusterTopBottom };
289 
290  explicit ExtendedNestingGraph(const ClusterGraph &CG);
291 
292  const ClusterGraphCopy &getClusterGraph() const { return m_CGC; }
293  const ClusterGraph &getOriginalClusterGraph() const { return m_CGC.getOriginalClusterGraph(); }
294 
295  node copy (node v) const { return m_copy[v]; }
296  node top (cluster cOrig) const { return m_topNode[cOrig]; }
297  node bottom(cluster cOrig) const { return m_bottomNode[cOrig]; }
298 
299  int topRank (cluster c) const { return m_topRank[c]; }
300  int bottomRank(cluster c) const { return m_bottomRank[c]; }
301 
302 
303  NodeType type(node v) const { return m_type[v]; }
304  node origNode (node v) const { return m_origNode[v]; }
305  edge origEdge (edge e) const { return m_origEdge[e]; }
306 
307  cluster originalCluster(node v) const { return m_CGC.original(m_CGC.clusterOf(v)); }
308  cluster parent(node v) const { return m_CGC.clusterOf(v); }
309  cluster parent(cluster c) const { return c->parent(); }
310  bool isVirtual(cluster c) const { return m_CGC.original(c) == nullptr; }
311 
312  const List<edge> &chain(edge e) const { return m_copyEdge[e]; }
313 
314  // is edge e reversed ?
315  bool isReversed (edge e) const {
316  return e->source() != origNode(chain(e).front()->source());
317  }
318 
319  bool isLongEdgeDummy(node v) const {
320  return type(v) == NodeType::Dummy && v->outdeg() == 1;
321  }
322 
323  bool verticalSegment(edge e) const { return m_vertical[e]; }
324 
325  int numberOfLayers() const { return m_numLayers; }
326  int rank(node v) const { return m_rank[v]; }
327  int pos(node v) const { return m_pos[v]; }
328  const LHTreeNode *layerHierarchyTree(int i) const { return m_layer[i].root(); }
329  const ENGLayer &layer(int i) const { return m_layer[i]; }
330 
331  RCCrossings reduceCrossings(int i, bool dirTopDown);
332  void storeCurrentPos();
333  void restorePos();
334  void permute();
335 
336  void removeTopBottomEdges();
337 
338  int aeLevel(node v) const { return m_aeLevel[v]; }
339 
340 protected:
341  cluster lca(node u, node v) const;
342  LHTreeNode *lca(
343  LHTreeNode *uNode,
344  LHTreeNode *vNode,
345  LHTreeNode **uChild,
346  LHTreeNode **vChild) const;
347 
348  edge addEdge(node u, node v, bool addAlways = false);
349  void assignAeLevel(cluster c, int &count);
350  bool reachable(node v, node u, SListPure<node> &successors);
351  void moveDown(node v, const SListPure<node> &successors, NodeArray<int> &level);
352  bool tryEdge(node u, node v, Graph &G, NodeArray<int> &level);
353 
354  RCCrossings reduceCrossings(LHTreeNode *cNode, bool dirTopDown);
355  void assignPos(const LHTreeNode *vNode, int &count);
356 
357 private:
358  void computeRanking();
359  void createDummyNodes();
360  void createVirtualClusters();
361  void createVirtualClusters(
362  cluster c,
363  NodeArray<node> &vCopy,
364  ClusterArray<node> &cCopy);
365  void buildLayers();
366  void removeAuxNodes();
367 
368 #if 0
369  const ClusterGraph &m_CG;
371 #else
372  ClusterGraphCopy m_CGC;
374 #endif
375 
376  // mapping: nodes in CG <-> nodes in this copy
379 
380  // mapping: clusters in CG <-> nodes in this copy
381  ClusterArray<node> m_topNode; // the node representing top-most part of cluster (min. rank)
382  ClusterArray<node> m_bottomNode; // the node representing bottom-most part of cluster (max. rank)
385 
386  // the type of a node in this copy
388 
389  // mapping: edges in CG <-> edges in this copy
392 
393  // level of each node
396 
397  // the layers
399  // positions within a layer
401 
402  // can an edge segment be drawn vertically?
404 
405  // temporary data for "addEdge()"
409 
410  // temporary data for "lca()"
417 };
418 
419 }
ogdf::RCCrossings::m_cnClusters
int m_cnClusters
Definition: ExtendedNestingGraph.h:107
ogdf::LHTreeNode::ClusterCrossing::m_uNode
LHTreeNode * m_uNode
Definition: ExtendedNestingGraph.h:149
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::LHTreeNode::m_origCluster
cluster m_origCluster
Definition: ExtendedNestingGraph.h:217
ogdf::LHTreeNode::Adjacency::m_weight
int m_weight
Definition: ExtendedNestingGraph.h:129
ogdf::ENGLayer::setRoot
void setRoot(LHTreeNode *r)
Definition: ExtendedNestingGraph.h:241
ogdf::RCCrossings::operator+=
RCCrossings & operator+=(const RCCrossings &cr)
Definition: ExtendedNestingGraph.h:62
ogdf::ClusterGraphCopy::m_pCG
const ClusterGraph * m_pCG
Definition: ExtendedNestingGraph.h:277
ogdf::ExtendedNestingGraph::bottom
node bottom(cluster cOrig) const
Definition: ExtendedNestingGraph.h:297
ogdf::RCCrossings::operator-
RCCrossings operator-(const RCCrossings &cr) const
Definition: ExtendedNestingGraph.h:72
ogdf::ExtendedNestingGraph::m_markedClustersTree
SListPure< cluster > m_markedClustersTree
Definition: ExtendedNestingGraph.h:415
ogdf::LHTreeNode::m_child
Array< LHTreeNode * > m_child
Definition: ExtendedNestingGraph.h:221
ogdf::ClusterGraphCopy::m_original
ClusterArray< cluster > m_original
Definition: ExtendedNestingGraph.h:281
ogdf::ClusterGraphCopy
Definition: ExtendedNestingGraph.h:258
ogdf::ExtendedNestingGraph::originalCluster
cluster originalCluster(node v) const
Definition: ExtendedNestingGraph.h:307
ogdf::RCCrossings::RCCrossings
RCCrossings()
Definition: ExtendedNestingGraph.h:44
ogdf::RCCrossings::m_cnEdges
int m_cnEdges
Definition: ExtendedNestingGraph.h:108
ogdf::ExtendedNestingGraph::m_layer
Array< ENGLayer > m_layer
Definition: ExtendedNestingGraph.h:398
ogdf::LHTreeNode::store
void store()
Definition: ExtendedNestingGraph.h:203
ogdf::LHTreeNode::isCompound
bool isCompound() const
Definition: ExtendedNestingGraph.h:177
ogdf::ExtendedNestingGraph::layer
const ENGLayer & layer(int i) const
Definition: ExtendedNestingGraph.h:329
ogdf::ClusterGraphCopy::getOriginalClusterGraph
const ClusterGraph & getOriginalClusterGraph() const
Definition: ExtendedNestingGraph.h:267
ogdf::ExtendedNestingGraph::copy
node copy(node v) const
Definition: ExtendedNestingGraph.h:295
ogdf::ENGLayer::m_root
LHTreeNode * m_root
Definition: ExtendedNestingGraph.h:253
ogdf::ClusterGraphCopy::m_copy
ClusterArray< cluster > m_copy
Definition: ExtendedNestingGraph.h:280
ogdf::RCCrossings::operator<=
bool operator<=(const RCCrossings &cr) const
Definition: ExtendedNestingGraph.h:76
ogdf::ExtendedNestingGraph::m_bottomNode
ClusterArray< node > m_bottomNode
Definition: ExtendedNestingGraph.h:382
ogdf::LHTreeNode::m_up
LHTreeNode * m_up
Definition: ExtendedNestingGraph.h:224
ogdf::ExtendedNestingGraph::topRank
int topRank(cluster c) const
Definition: ExtendedNestingGraph.h:299
ogdf::LHTreeNode::initChild
void initChild(int n)
Definition: ExtendedNestingGraph.h:198
ogdf::ExtendedNestingGraph::m_topRank
ClusterArray< int > m_topRank
Definition: ExtendedNestingGraph.h:383
ogdf::LHTreeNode::ClusterCrossing::m_edge
edge m_edge
Definition: ExtendedNestingGraph.h:151
ogdf::ENGLayer::root
const LHTreeNode * root() const
Definition: ExtendedNestingGraph.h:238
ogdf::LHTreeNode::m_lowerClusterCrossing
List< ClusterCrossing > m_lowerClusterCrossing
Definition: ExtendedNestingGraph.h:212
ogdf::ExtendedNestingGraph::getClusterGraph
const ClusterGraphCopy & getClusterGraph() const
Definition: ExtendedNestingGraph.h:292
ogdf::ExtendedNestingGraph::m_aeLevel
NodeArray< int > m_aeLevel
Definition: ExtendedNestingGraph.h:406
ogdf::ExtendedNestingGraph::m_origNode
NodeArray< node > m_origNode
Definition: ExtendedNestingGraph.h:378
ogdf::ExtendedNestingGraph::isVirtual
bool isVirtual(cluster c) const
Definition: ExtendedNestingGraph.h:310
ogdf::RCCrossings::compare
static int compare(const RCCrossings &x, const RCCrossings &y)
Definition: ExtendedNestingGraph.h:99
ogdf::LHTreeNode
Definition: ExtendedNestingGraph.h:113
ogdf::LHTreeNode::m_node
node m_node
Definition: ExtendedNestingGraph.h:218
ogdf::LHTreeNode::ClusterCrossing
Definition: ExtendedNestingGraph.h:134
ogdf::LHTreeNode::child
LHTreeNode * child(int i)
Definition: ExtendedNestingGraph.h:197
ogdf::LHTreeNode::LHTreeNode
LHTreeNode(LHTreeNode *parent, node v, Type t=Type::Node)
Definition: ExtendedNestingGraph.h:167
ogdf::LHTreeNode::m_parent
LHTreeNode * m_parent
Definition: ExtendedNestingGraph.h:215
ogdf::ExtendedNestingGraph::aeLevel
int aeLevel(node v) const
Definition: ExtendedNestingGraph.h:338
ogdf::ExtendedNestingGraph::m_origEdge
EdgeArray< edge > m_origEdge
Definition: ExtendedNestingGraph.h:391
ogdf::ExtendedNestingGraph::m_type
NodeArray< NodeType > m_type
Definition: ExtendedNestingGraph.h:387
ogdf::ExtendedNestingGraph::pos
int pos(node v) const
Definition: ExtendedNestingGraph.h:327
ogdf::ENGLayer::root
LHTreeNode * root()
Definition: ExtendedNestingGraph.h:239
ogdf::LHTreeNode::ClusterCrossing::m_cNode
LHTreeNode * m_cNode
Definition: ExtendedNestingGraph.h:148
ogdf::RCCrossings::incClusters
void incClusters()
Definition: ExtendedNestingGraph.h:58
ogdf::LHTreeNode::Adjacency::m_v
LHTreeNode * m_v
Definition: ExtendedNestingGraph.h:128
ogdf::LHTreeNode::Adjacency::Adjacency
Adjacency()
Definition: ExtendedNestingGraph.h:120
ogdf::ExtendedNestingGraph::m_markTree
ClusterArray< LHTreeNode * > m_markTree
Definition: ExtendedNestingGraph.h:416
ogdf::NodeArray< int >
ogdf::LHTreeNode::restore
void restore()
Definition: ExtendedNestingGraph.h:204
ogdf::ExtendedNestingGraph::layerHierarchyTree
const LHTreeNode * layerHierarchyTree(int i) const
Definition: ExtendedNestingGraph.h:328
OGDF_NEW_DELETE
#define OGDF_NEW_DELETE
Makes the class use OGDF's memory allocator.
Definition: memory.h:84
ogdf::LHTreeNode::down
const LHTreeNode * down() const
Definition: ExtendedNestingGraph.h:188
ogdf::EdgeArray
Dynamic arrays indexed with edges.
Definition: EdgeArray.h:112
ogdf::RCCrossings::RCCrossings
RCCrossings(int cnClusters, int cnEdges)
Definition: ExtendedNestingGraph.h:49
ogdf::ExtendedNestingGraph::NodeType
NodeType
Definition: ExtendedNestingGraph.h:288
ogdf::LHTreeNode::up
const LHTreeNode * up() const
Definition: ExtendedNestingGraph.h:187
ogdf::ExtendedNestingGraph::m_vertical
EdgeArray< bool > m_vertical
Definition: ExtendedNestingGraph.h:403
ogdf::ExtendedNestingGraph::m_topNode
ClusterArray< node > m_topNode
Definition: ExtendedNestingGraph.h:381
ogdf::ExtendedNestingGraph::getOriginalClusterGraph
const ClusterGraph & getOriginalClusterGraph() const
Definition: ExtendedNestingGraph.h:293
ogdf::LHTreeNode::setChild
void setChild(int i, LHTreeNode *p)
Definition: ExtendedNestingGraph.h:199
ogdf::LHTreeNode::m_upperAdj
List< Adjacency > m_upperAdj
Definition: ExtendedNestingGraph.h:209
ogdf::LHTreeNode::ClusterCrossing::m_uc
node m_uc
Definition: ExtendedNestingGraph.h:146
ogdf::ClusterElement
Representation of clusters in a clustered graph.
Definition: ClusterGraph.h:53
ogdf::ExtendedNestingGraph::isReversed
bool isReversed(edge e) const
Definition: ExtendedNestingGraph.h:315
ogdf::LHTreeNode::Adjacency
Definition: ExtendedNestingGraph.h:118
r
int r[]
Definition: hierarchical-ranking.cpp:8
ogdf::NodeElement::outdeg
int outdeg() const
Returns the outdegree of the node.
Definition: Graph_d.h:208
ogdf::LHTreeNode::setParent
void setParent(LHTreeNode *p)
Definition: ExtendedNestingGraph.h:195
ogdf::ExtendedNestingGraph::parent
cluster parent(node v) const
Definition: ExtendedNestingGraph.h:308
ogdf::ExtendedNestingGraph::m_copy
NodeArray< node > m_copy
Definition: ExtendedNestingGraph.h:377
ogdf::ClusterGraphCopy::m_pH
const ExtendedNestingGraph * m_pH
Definition: ExtendedNestingGraph.h:278
ogdf::ExtendedNestingGraph::origNode
node origNode(node v) const
Definition: ExtendedNestingGraph.h:304
backward::Color::type
type
Definition: backward.hpp:1716
ogdf::ExtendedNestingGraph::m_markedClusters
SListPure< cluster > m_markedClusters
Definition: ExtendedNestingGraph.h:412
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::LHTreeNode::permute
void permute()
Definition: ExtendedNestingGraph.h:205
ogdf::ClusterGraphCopy::original
cluster original(cluster cCopy) const
Definition: ExtendedNestingGraph.h:270
ogdf::ClusterArray
Dynamic arrays indexed with clusters.
Definition: ClusterArray.h:110
EdgeArray.h
Declaration and implementation of EdgeArray class.
ogdf::LHTreeNode::ClusterCrossing::ClusterCrossing
ClusterCrossing(node uc, LHTreeNode *cNode, node u, LHTreeNode *uNode, edge e)
Definition: ExtendedNestingGraph.h:137
ogdf::ExtendedNestingGraph::m_secondPath
cluster m_secondPath
Definition: ExtendedNestingGraph.h:413
ogdf::ExtendedNestingGraph::m_aeVisited
NodeArray< bool > m_aeVisited
Definition: ExtendedNestingGraph.h:407
ogdf::LHTreeNode::LHTreeNode
LHTreeNode(cluster c, LHTreeNode *up)
Definition: ExtendedNestingGraph.h:155
ogdf::SListPure
Singly linked lists.
Definition: SList.h:38
ogdf::ClusterGraphCopy::copy
cluster copy(cluster cOrig) const
Definition: ExtendedNestingGraph.h:269
ogdf::ExtendedNestingGraph::chain
const List< edge > & chain(edge e) const
Definition: ExtendedNestingGraph.h:312
ogdf::ExtendedNestingGraph::top
node top(cluster cOrig) const
Definition: ExtendedNestingGraph.h:296
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::EdgeElement::source
node source() const
Returns the source node of the edge.
Definition: Graph_d.h:326
ClusterArray.h
Declaration and implementation of ClusterArray class.
ogdf::ExtendedNestingGraph::m_copyEdge
EdgeArray< List< edge > > m_copyEdge
Definition: ExtendedNestingGraph.h:390
ogdf::List
Doubly linked lists (maintaining the length of the list).
Definition: List.h:40
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::ExtendedNestingGraph::numberOfLayers
int numberOfLayers() const
Definition: ExtendedNestingGraph.h:325
ogdf::RCCrossings::setInfinity
RCCrossings & setInfinity()
Definition: ExtendedNestingGraph.h:94
ogdf::LHTreeNode::m_lowerAdj
List< Adjacency > m_lowerAdj
Definition: ExtendedNestingGraph.h:210
ogdf::LHTreeNode::numberOfChildren
int numberOfChildren() const
Definition: ExtendedNestingGraph.h:179
ogdf::ExtendedNestingGraph::m_numLayers
int m_numLayers
Definition: ExtendedNestingGraph.h:395
ogdf::ExtendedNestingGraph::parent
cluster parent(cluster c) const
Definition: ExtendedNestingGraph.h:309
ogdf::ExtendedNestingGraph::type
NodeType type(node v) const
Definition: ExtendedNestingGraph.h:303
ogdf::RCCrossings::isZero
bool isZero() const
Definition: ExtendedNestingGraph.h:90
ogdf::ExtendedNestingGraph::bottomRank
int bottomRank(cluster c) const
Definition: ExtendedNestingGraph.h:300
ogdf::ExtendedNestingGraph::verticalSegment
bool verticalSegment(edge e) const
Definition: ExtendedNestingGraph.h:323
ogdf::LHTreeNode::m_type
Type m_type
Definition: ExtendedNestingGraph.h:219
ogdf::LHTreeNode::getNode
node getNode() const
Definition: ExtendedNestingGraph.h:185
ogdf::ExtendedNestingGraph::m_secondPathTo
node m_secondPathTo
Definition: ExtendedNestingGraph.h:414
ogdf::LHTreeNode::m_upperClusterCrossing
List< ClusterCrossing > m_upperClusterCrossing
Definition: ExtendedNestingGraph.h:211
ogdf::graphics::init
void init()
Definition: graphics.h:472
ogdf::ExtendedNestingGraph::m_mark
ClusterArray< cluster > m_mark
Definition: ExtendedNestingGraph.h:411
ogdf::LHTreeNode::child
const LHTreeNode * child(int i) const
Definition: ExtendedNestingGraph.h:182
ogdf::LHTreeNode::pos
int pos() const
Definition: ExtendedNestingGraph.h:190
ogdf::RCCrossings::operator+
RCCrossings operator+(const RCCrossings &cr) const
Definition: ExtendedNestingGraph.h:68
ogdf::ExtendedNestingGraph::m_pos
NodeArray< int > m_pos
Definition: ExtendedNestingGraph.h:400
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::ExtendedNestingGraph::rank
int rank(node v) const
Definition: ExtendedNestingGraph.h:326
ogdf::ExtendedNestingGraph::isLongEdgeDummy
bool isLongEdgeDummy(node v) const
Definition: ExtendedNestingGraph.h:319
ogdf::LHTreeNode::originalCluster
cluster originalCluster() const
Definition: ExtendedNestingGraph.h:184
ogdf::EdgeElement
Class for the representation of edges.
Definition: Graph_d.h:292
ClusterGraph.h
Derived class of GraphObserver providing additional functionality to handle clustered graphs.
ogdf::RCCrossings
Definition: ExtendedNestingGraph.h:42
ogdf::ENGLayer
Represents layer in an extended nesting graph.
Definition: ExtendedNestingGraph.h:232
ogdf::ExtendedNestingGraph::m_auxDeg
NodeArray< int > m_auxDeg
Definition: ExtendedNestingGraph.h:408
ogdf::ClusterElement::parent
cluster parent()
Returns the parent of the cluster.
Definition: ClusterGraph.h:150
ogdf::LHTreeNode::parent
LHTreeNode * parent()
Definition: ExtendedNestingGraph.h:194
ogdf::LHTreeNode::parent
const LHTreeNode * parent() const
Definition: ExtendedNestingGraph.h:181
ogdf::ENGLayer::ENGLayer
ENGLayer()
Definition: ExtendedNestingGraph.h:235
ogdf::LHTreeNode::m_down
LHTreeNode * m_down
Definition: ExtendedNestingGraph.h:225
ogdf::LHTreeNode::m_storedChild
Array< LHTreeNode * > m_storedChild
Definition: ExtendedNestingGraph.h:222
ogdf::LHTreeNode::m_pos
int m_pos
Definition: ExtendedNestingGraph.h:226
ogdf::LHTreeNode::ClusterCrossing::m_u
node m_u
Definition: ExtendedNestingGraph.h:147
ogdf::ExtendedNestingGraph
Definition: ExtendedNestingGraph.h:284
ogdf::ExtendedNestingGraph::m_rank
NodeArray< int > m_rank
Definition: ExtendedNestingGraph.h:394
ogdf::RCCrossings::incEdges
void incEdges(int cn)
Definition: ExtendedNestingGraph.h:54
ogdf::LHTreeNode::ClusterCrossing::ClusterCrossing
ClusterCrossing()
Definition: ExtendedNestingGraph.h:136
ogdf::LHTreeNode::Adjacency::Adjacency
Adjacency(node u, LHTreeNode *vNode, int weight=1)
Definition: ExtendedNestingGraph.h:121
ogdf::ClusterGraph
Representation of clustered graphs.
Definition: ClusterGraph.h:291
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::ExtendedNestingGraph::m_bottomRank
ClusterArray< int > m_bottomRank
Definition: ExtendedNestingGraph.h:384
ogdf::RCCrossings::operator<
bool operator<(const RCCrossings &cr) const
Definition: ExtendedNestingGraph.h:83
ogdf::ExtendedNestingGraph::origEdge
edge origEdge(edge e) const
Definition: ExtendedNestingGraph.h:305
ogdf::LHTreeNode::Type
Type
Definition: ExtendedNestingGraph.h:116
ogdf::LHTreeNode::Adjacency::m_u
node m_u
Definition: ExtendedNestingGraph.h:127