1 /** \file 2 * \brief Declaration of ExtendedNestingGraph 3 * 4 * Manages access on copy of an attributed graph. 5 * 6 * \author Carsten Gutwenger 7 * 8 * \par License: 9 * This file is part of the Open Graph Drawing Framework (OGDF). 10 * 11 * \par 12 * Copyright (C)<br> 13 * See README.md in the OGDF root directory for details. 14 * 15 * \par 16 * This program is free software; you can redistribute it and/or 17 * modify it under the terms of the GNU General Public License 18 * Version 2 or 3 as published by the Free Software Foundation; 19 * see the file LICENSE.txt included in the packaging of this file 20 * for details. 21 * 22 * \par 23 * This program is distributed in the hope that it will be useful, 24 * but WITHOUT ANY WARRANTY; without even the implied warranty of 25 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 26 * GNU General Public License for more details. 27 * 28 * \par 29 * You should have received a copy of the GNU General Public 30 * License along with this program; if not, see 31 * http://www.gnu.org/copyleft/gpl.html 32 */ 33 34 #pragma once 35 36 #include <ogdf/cluster/ClusterGraph.h> 37 #include <ogdf/basic/EdgeArray.h> 38 #include <ogdf/cluster/ClusterArray.h> 39 40 namespace ogdf { 41 42 struct OGDF_EXPORT RCCrossings 43 { RCCrossingsRCCrossings44 RCCrossings() { 45 m_cnClusters = 0; 46 m_cnEdges = 0; 47 } 48 RCCrossingsRCCrossings49 RCCrossings(int cnClusters, int cnEdges) { 50 m_cnClusters = cnClusters; 51 m_cnEdges = cnEdges; 52 } 53 incEdgesRCCrossings54 void incEdges(int cn) { 55 m_cnEdges += cn; 56 } 57 incClustersRCCrossings58 void incClusters() { 59 ++m_cnClusters; 60 } 61 62 RCCrossings &operator+=(const RCCrossings &cr) { 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 isZeroRCCrossings90 bool isZero() const { 91 return m_cnClusters == 0 && m_cnEdges == 0; 92 } 93 setInfinityRCCrossings94 RCCrossings &setInfinity() { 95 m_cnClusters = m_cnEdges = std::numeric_limits<int>::max(); 96 return *this; 97 } 98 compareRCCrossings99 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 107 int m_cnClusters; 108 int m_cnEdges; 109 }; 110 111 OGDF_EXPORT std::ostream& operator<<(std::ostream &os, const RCCrossings &cr); 112 113 class OGDF_EXPORT LHTreeNode 114 { 115 public: 116 enum class Type { Compound, Node, AuxNode }; 117 118 struct Adjacency 119 { AdjacencyAdjacency120 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 127 node m_u; 128 LHTreeNode *m_v; 129 int m_weight; 130 131 OGDF_NEW_DELETE 132 }; 133 134 struct ClusterCrossing 135 { ClusterCrossingClusterCrossing136 ClusterCrossing() { m_uc = nullptr; m_u = nullptr; m_cNode = nullptr; m_uNode = nullptr; } ClusterCrossingClusterCrossing137 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 146 node m_uc; 147 node m_u; 148 LHTreeNode *m_cNode; 149 LHTreeNode *m_uNode; 150 151 edge m_edge; 152 }; 153 154 // Construction LHTreeNode(cluster c,LHTreeNode * up)155 LHTreeNode(cluster c, LHTreeNode *up) { 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 isCompound()177 bool isCompound() const { return m_type == Type::Compound; } 178 numberOfChildren()179 int numberOfChildren() const { return m_child.size(); } 180 parent()181 const LHTreeNode *parent() const { return m_parent; } child(int i)182 const LHTreeNode *child(int i) const { return m_child[i]; } 183 originalCluster()184 cluster originalCluster() const { return m_origCluster; } getNode()185 node getNode() const { return m_node; } 186 up()187 const LHTreeNode *up () const { return m_up; } down()188 const LHTreeNode *down() const { return m_down; } 189 pos()190 int pos() const { return m_pos; } 191 192 193 // Modification functions parent()194 LHTreeNode *parent() { return m_parent; } setParent(LHTreeNode * p)195 void setParent(LHTreeNode *p) { m_parent = p; } 196 child(int i)197 LHTreeNode *child(int i) { return m_child[i]; } initChild(int n)198 void initChild(int n) { m_child.init(n); } setChild(int i,LHTreeNode * p)199 void setChild(int i, LHTreeNode *p) { m_child[i] = p; } 200 201 void setPos(); 202 store()203 void store() { m_storedChild = m_child; } restore()204 void restore() { m_child = m_storedChild; } permute()205 void permute() { m_child.permute(); } 206 207 void removeAuxChildren(); 208 209 List<Adjacency> m_upperAdj; 210 List<Adjacency> m_lowerAdj; 211 List<ClusterCrossing> m_upperClusterCrossing; 212 List<ClusterCrossing> m_lowerClusterCrossing; 213 214 private: 215 LHTreeNode *m_parent; 216 217 cluster m_origCluster; 218 node m_node; 219 Type m_type; 220 221 Array<LHTreeNode*> m_child; 222 Array<LHTreeNode*> m_storedChild; 223 224 LHTreeNode *m_up; 225 LHTreeNode *m_down; 226 int m_pos; 227 228 OGDF_NEW_DELETE 229 }; 230 231 //! Represents layer in an extended nesting graph 232 class OGDF_EXPORT ENGLayer 233 { 234 public: ENGLayer()235 ENGLayer() { m_root = nullptr; } 236 ~ENGLayer(); 237 root()238 const LHTreeNode *root() const { return m_root; } root()239 LHTreeNode *root() { return m_root; } 240 setRoot(LHTreeNode * r)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 253 LHTreeNode *m_root; 254 }; 255 256 class OGDF_EXPORT ExtendedNestingGraph; 257 258 class OGDF_EXPORT ClusterGraphCopy : public ClusterGraph 259 { 260 public: 261 262 ClusterGraphCopy(); 263 ClusterGraphCopy(const ExtendedNestingGraph &H, const ClusterGraph &CG); 264 265 void init(const ExtendedNestingGraph &H, const ClusterGraph &CG); 266 getOriginalClusterGraph()267 const ClusterGraph &getOriginalClusterGraph() const { return *m_pCG; } 268 copy(cluster cOrig)269 cluster copy(cluster cOrig) const { return m_copy[cOrig]; } original(cluster cCopy)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 277 const ClusterGraph *m_pCG; 278 const ExtendedNestingGraph *m_pH; 279 280 ClusterArray<cluster> m_copy; 281 ClusterArray<cluster> m_original; 282 }; 283 284 class OGDF_EXPORT ExtendedNestingGraph : public Graph 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 getClusterGraph()292 const ClusterGraphCopy &getClusterGraph() const { return m_CGC; } getOriginalClusterGraph()293 const ClusterGraph &getOriginalClusterGraph() const { return m_CGC.getOriginalClusterGraph(); } 294 copy(node v)295 node copy (node v) const { return m_copy[v]; } top(cluster cOrig)296 node top (cluster cOrig) const { return m_topNode[cOrig]; } bottom(cluster cOrig)297 node bottom(cluster cOrig) const { return m_bottomNode[cOrig]; } 298 topRank(cluster c)299 int topRank (cluster c) const { return m_topRank[c]; } bottomRank(cluster c)300 int bottomRank(cluster c) const { return m_bottomRank[c]; } 301 302 type(node v)303 NodeType type(node v) const { return m_type[v]; } origNode(node v)304 node origNode (node v) const { return m_origNode[v]; } origEdge(edge e)305 edge origEdge (edge e) const { return m_origEdge[e]; } 306 originalCluster(node v)307 cluster originalCluster(node v) const { return m_CGC.original(m_CGC.clusterOf(v)); } parent(node v)308 cluster parent(node v) const { return m_CGC.clusterOf(v); } parent(cluster c)309 cluster parent(cluster c) const { return c->parent(); } isVirtual(cluster c)310 bool isVirtual(cluster c) const { return m_CGC.original(c) == nullptr; } 311 chain(edge e)312 const List<edge> &chain(edge e) const { return m_copyEdge[e]; } 313 314 // is edge e reversed ? isReversed(edge e)315 bool isReversed (edge e) const { 316 return e->source() != origNode(chain(e).front()->source()); 317 } 318 isLongEdgeDummy(node v)319 bool isLongEdgeDummy(node v) const { 320 return type(v) == NodeType::Dummy && v->outdeg() == 1; 321 } 322 verticalSegment(edge e)323 bool verticalSegment(edge e) const { return m_vertical[e]; } 324 numberOfLayers()325 int numberOfLayers() const { return m_numLayers; } rank(node v)326 int rank(node v) const { return m_rank[v]; } pos(node v)327 int pos(node v) const { return m_pos[v]; } layerHierarchyTree(int i)328 const LHTreeNode *layerHierarchyTree(int i) const { return m_layer[i].root(); } layer(int i)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 aeLevel(node v)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 //! original graph 370 const ClusterGraph &m_CG; 371 #else 372 //! copy of original cluster graph 373 ClusterGraphCopy m_CGC; 374 #endif 375 376 // mapping: nodes in CG <-> nodes in this copy 377 NodeArray<node> m_copy; 378 NodeArray<node> m_origNode; 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) 383 ClusterArray<int> m_topRank; 384 ClusterArray<int> m_bottomRank; 385 386 // the type of a node in this copy 387 NodeArray<NodeType> m_type; 388 389 // mapping: edges in CG <-> edges in this copy 390 EdgeArray<List<edge> > m_copyEdge; 391 EdgeArray<edge> m_origEdge; 392 393 // level of each node 394 NodeArray<int> m_rank; 395 int m_numLayers; 396 397 // the layers 398 Array<ENGLayer> m_layer; 399 // positions within a layer 400 NodeArray<int> m_pos; 401 402 // can an edge segment be drawn vertically? 403 EdgeArray<bool> m_vertical; 404 405 // temporary data for "addEdge()" 406 NodeArray<int> m_aeLevel; 407 NodeArray<bool> m_aeVisited; 408 NodeArray<int> m_auxDeg; 409 410 // temporary data for "lca()" 411 mutable ClusterArray<cluster> m_mark; 412 mutable SListPure<cluster> m_markedClusters; 413 mutable cluster m_secondPath; 414 mutable node m_secondPathTo; 415 mutable SListPure<cluster> m_markedClustersTree; 416 mutable ClusterArray<LHTreeNode*> m_markTree; 417 }; 418 419 } 420