ext/OGDF/ogdf/layered/ExtendedNestingGraph.h

   1 /*
   2  * $Revision: 2523 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-02 20:59:27 +0200 (Mon, 02 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of ExtendedNestingGraph
  11  *
  12  * Manages access on copy of an attributed graph.
  13  *
  14  * \author Carsten Gutwenger
  15  *
  16  * \par License:
  17  * This file is part of the Open Graph Drawing Framework (OGDF).
  18  *
  19  * \par
  20  * Copyright (C)<br>
  21  * See README.txt in the root directory of the OGDF installation for details.
  22  *
  23  * \par
  24  * This program is free software; you can redistribute it and/or
  25  * modify it under the terms of the GNU General Public License
  26  * Version 2 or 3 as published by the Free Software Foundation;
  27  * see the file LICENSE.txt included in the packaging of this file
  28  * for details.
  29  *
  30  * \par
  31  * This program is distributed in the hope that it will be useful,
  32  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  33  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  34  * GNU General Public License for more details.
  35  *
  36  * \par
  37  * You should have received a copy of the GNU General Public
  38  * License along with this program; if not, write to the Free
  39  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  40  * Boston, MA 02110-1301, USA.
  41  *
  42  * \see  http://www.gnu.org/copyleft/gpl.html
  43  ***************************************************************/
  44
  45 #ifdef _MSC_VER
  46 #pragma once
  47 #endif
  48
  49 #ifndef OGDF_EXTENDED_NESTING_GRAPH_H
  50 #define OGDF_EXTENDED_NESTING_GRAPH_H
  51
  52
  53
  54 #include <ogdf/cluster/ClusterGraph.h>
  55 #include <ogdf/basic/EdgeArray.h>
  56 #include <ogdf/cluster/ClusterArray.h>
  57 #include <limits.h>
  58
  59
  60 namespace ogdf {
  61
  62
  63 //---------------------------------------------------------
  64 // RCCrossings
  65 //---------------------------------------------------------
  66 struct OGDF_EXPORT RCCrossings
  67 {
  68         RCCrossings() {
  69                 m_cnClusters = 0;
  70                 m_cnEdges    = 0;
  71         }
  72
  73         RCCrossings(int cnClusters, int cnEdges) {
  74                 m_cnClusters = cnClusters;
  75                 m_cnEdges    = cnEdges;
  76         }
  77
  78         void incEdges(int cn) {
  79                 m_cnEdges += cn;
  80         }
  81
  82         void incClusters() {
  83                 ++m_cnClusters;
  84         }
  85
  86         RCCrossings &operator+=(const RCCrossings &cr) {
  87                 m_cnClusters += cr.m_cnClusters;
  88                 m_cnEdges    += cr.m_cnEdges;
  89                 return *this;
  90         }
  91
  92         RCCrossings operator+(const RCCrossings &cr) const {
  93                 return RCCrossings(m_cnClusters+cr.m_cnClusters, m_cnEdges+cr.m_cnEdges);
  94         }
  95
  96         RCCrossings operator-(const RCCrossings &cr) const {
  97                 return RCCrossings(m_cnClusters-cr.m_cnClusters, m_cnEdges-cr.m_cnEdges);
  98         }
  99
 100         bool operator<=(const RCCrossings &cr) const {
 101                 if(m_cnClusters == cr.m_cnClusters)
 102                         return (m_cnEdges <= cr.m_cnEdges);
 103                 else
 104                         return (m_cnClusters <= cr.m_cnClusters);
 105         }
 106
 107         bool operator<(const RCCrossings &cr) const {
 108                 if(m_cnClusters == cr.m_cnClusters)
 109                         return (m_cnEdges < cr.m_cnEdges);
 110                 else
 111                         return (m_cnClusters < cr.m_cnClusters);
 112         }
 113
 114         bool isZero() const {
 115                 return m_cnClusters == 0 && m_cnEdges == 0;
 116         }
 117
 118         RCCrossings &setInfinity() {
 119                 m_cnClusters = m_cnEdges = INT_MAX;
 120                 return *this;
 121         }
 122
 123         static int compare(const RCCrossings &x, const RCCrossings &y)
 124         {
 125                 int dc = y.m_cnClusters - x.m_cnClusters;
 126                 if(dc != 0)
 127                         return dc;
 128                 return y.m_cnEdges - x.m_cnEdges;
 129         }
 130
 131         int m_cnClusters;
 132         int m_cnEdges;
 133 };
 134
 135 OGDF_EXPORT ostream& operator<<(ostream &os, const RCCrossings &cr);
 136
 137
 138 //---------------------------------------------------------
 139 // LHTreeNode
 140 //---------------------------------------------------------
 141 class OGDF_EXPORT LHTreeNode
 142 {
 143 public:
 144         enum Type { Compound, Node, AuxNode };
 145
 146         struct Adjacency
 147         {
 148                 Adjacency() { m_u = 0; m_v = 0; m_weight = 0; }
 149                 Adjacency(node u, LHTreeNode *vNode, int weight = 1) {
 150                         m_u      = u;
 151                         m_v      = vNode;
 152                         m_weight = weight;
 153                 }
 154
 155                 node          m_u;
 156                 LHTreeNode   *m_v;
 157                 int           m_weight;
 158
 159                 OGDF_NEW_DELETE
 160         };
 161
 162         struct ClusterCrossing
 163         {
 164                 ClusterCrossing() { m_uc = 0; m_u = 0; m_cNode = 0; m_uNode = 0; }
 165                 ClusterCrossing(node uc, LHTreeNode *cNode, node u, LHTreeNode *uNode, edge e) {
 166                         m_uc = uc;
 167                         m_u  = u;
 168                         m_cNode = cNode;
 169                         m_uNode = uNode;
 170
 171                         m_edge = e;
 172                 }
 173
 174                 node m_uc;
 175                 node m_u;
 176                 LHTreeNode *m_cNode;
 177                 LHTreeNode *m_uNode;
 178
 179                 edge m_edge;
 180         };
 181
 182         // Construction
 183         LHTreeNode(cluster c, LHTreeNode *up) {
 184                 m_parent      = 0;
 185                 m_origCluster = c;
 186                 m_node        = 0;
 187                 m_type        = Compound;
 188                 m_down        = 0;
 189
 190                 m_up = up;
 191                 if(up)
 192                         up->m_down = this;
 193         }
 194
 195         LHTreeNode(LHTreeNode *parent, node v, Type t = Node) {
 196                 m_parent      = parent;
 197                 m_origCluster = 0;
 198                 m_node        = v;
 199                 m_type        = t;
 200                 m_up          = 0;
 201                 m_down        = 0;
 202         }
 203
 204         // Access functions
 205         bool isCompound() const { return m_type == Compound; }
 206
 207         int numberOfChildren() const { return m_child.size(); }
 208
 209         const LHTreeNode *parent() const { return m_parent; }
 210         const LHTreeNode *child(int i) const { return m_child[i]; }
 211
 212         cluster originalCluster() const { return m_origCluster; }
 213         node    getNode()         const { return m_node; }
 214
 215         const LHTreeNode *up  () const { return m_up; }
 216         const LHTreeNode *down() const { return m_down; }
 217
 218         int pos() const { return m_pos; }
 219
 220
 221         // Modification functions
 222         LHTreeNode *parent() { return m_parent; }
 223         void setParent(LHTreeNode *p) { m_parent = p; }
 224
 225         LHTreeNode *child(int i) { return m_child[i]; }
 226         void initChild(int n) { m_child.init(n); }
 227         void setChild(int i, LHTreeNode *p) { m_child[i] = p; }
 228
 229         void setPos();
 230
 231         void store() { m_storedChild = m_child; }
 232         void restore() { m_child = m_storedChild; }
 233         void permute() { m_child.permute(); }
 234
 235         void removeAuxChildren();
 236
 237         List<Adjacency> m_upperAdj;
 238         List<Adjacency> m_lowerAdj;
 239         List<ClusterCrossing> m_upperClusterCrossing;
 240         List<ClusterCrossing> m_lowerClusterCrossing;
 241
 242 private:
 243         LHTreeNode        *m_parent;
 244
 245         cluster            m_origCluster;
 246         node               m_node;
 247         Type               m_type;
 248
 249         Array<LHTreeNode*> m_child;
 250         Array<LHTreeNode*> m_storedChild;
 251
 252         LHTreeNode        *m_up;
 253         LHTreeNode        *m_down;
 254         int                m_pos;
 255
 256         OGDF_NEW_DELETE
 257 };
 258
 259
 260 //---------------------------------------------------------
 261 // ENGLayer
 262 //---------------------------------------------------------
 263 class OGDF_EXPORT ENGLayer
 264 {
 265 public:
 266         ENGLayer() { m_root = 0; }
 267         ~ENGLayer();
 268
 269         const LHTreeNode *root() const { return m_root; }
 270         LHTreeNode *root() { return m_root; }
 271
 272         void setRoot(LHTreeNode *r) { m_root = r; }
 273
 274         void store();
 275         void restore();
 276         void permute();
 277
 278         void simplifyAdjacencies();
 279         void removeAuxNodes();
 280
 281 private:
 282         void simplifyAdjacencies(List<LHTreeNode::Adjacency> &adjs);
 283
 284         LHTreeNode *m_root;
 285 };
 286
 287
 288 //---------------------------------------------------------
 289 // ClusterGraphCopy
 290 //---------------------------------------------------------
 291 class OGDF_EXPORT ExtendedNestingGraph;
 292
 293 class OGDF_EXPORT ClusterGraphCopy : public ClusterGraph
 294 {
 295 public:
 296
 297         ClusterGraphCopy();
 298         ClusterGraphCopy(const ExtendedNestingGraph &H, const ClusterGraph &CG);
 299
 300         void init(const ExtendedNestingGraph &H, const ClusterGraph &CG);
 301
 302         const ClusterGraph &getOriginalClusterGraph() const { return *m_pCG; }
 303
 304         cluster copy(cluster cOrig) const { return m_copy[cOrig]; }
 305         cluster original(cluster cCopy) const { return m_original[cCopy]; }
 306
 307         void setParent(node v, cluster c);
 308
 309 private:
 310         void createClusterTree(cluster cOrig);
 311
 312         const ClusterGraph         *m_pCG;
 313         const ExtendedNestingGraph *m_pH;
 314
 315         ClusterArray<cluster> m_copy;
 316         ClusterArray<cluster> m_original;
 317 };
 318
 319
 320 //---------------------------------------------------------
 321 // ExtendedNestingGraph
 322 //---------------------------------------------------------
 323 class OGDF_EXPORT ExtendedNestingGraph : public Graph
 324 {
 325 public:
 326         // the type of a node in this copy
 327         enum NodeType { ntNode, ntClusterTop, ntClusterBottom, ntDummy, ntClusterTopBottom };
 328
 329         ExtendedNestingGraph(const ClusterGraph &CG);
 330
 331         const ClusterGraphCopy &getClusterGraph() const { return m_CGC; }
 332         const ClusterGraph &getOriginalClusterGraph() const { return m_CGC.getOriginalClusterGraph(); }
 333
 334         node copy  (node v)    const { return m_copy[v]; }
 335         node top   (cluster cOrig) const { return m_topNode[cOrig]; }
 336         node bottom(cluster cOrig) const { return m_bottomNode[cOrig]; }
 337
 338         int topRank   (cluster c) const { return m_topRank[c]; }
 339         int bottomRank(cluster c) const { return m_bottomRank[c]; }
 340
 341
 342         NodeType type(node v) const { return m_type[v]; }
 343         node    origNode   (node v) const { return m_origNode[v]; }
 344         edge    origEdge   (edge e) const { return m_origEdge[e]; }
 345
 346         cluster originalCluster(node v) const { return m_CGC.original(m_CGC.clusterOf(v)); }
 347         cluster parent(node v) const { return m_CGC.clusterOf(v); }
 348         cluster parent(cluster c) const { return c->parent(); }
 349         bool isVirtual(cluster c) const { return m_CGC.original(c) == 0; }
 350
 351         const List<edge> &chain(edge e) const { return m_copyEdge[e]; }
 352
 353         // is edge e reversed ?
 354         bool isReversed (edge e) const {
 355                 return e->source() != origNode(chain(e).front()->source());
 356         }
 357
 358         bool isLongEdgeDummy(node v) const {
 359                 return (type(v) == ntDummy && v->outdeg() == 1);
 360         }
 361
 362         bool verticalSegment(edge e) const { return m_vertical[e]; }
 363
 364         int numberOfLayers() const { return m_numLayers; }
 365         int rank(node v) const { return m_rank[v]; }
 366         int pos(node v) const { return m_pos[v]; }
 367         const LHTreeNode *layerHierarchyTree(int i) const { return m_layer[i].root(); }
 368         const ENGLayer &layer(int i) const { return m_layer[i]; }
 369
 370         RCCrossings reduceCrossings(int i, bool dirTopDown);
 371         void storeCurrentPos();
 372         void restorePos();
 373         void permute();
 374
 375         void removeTopBottomEdges();
 376
 377         int aeLevel(node v) const { return m_aeLevel[v]; }
 378
 379 protected:
 380         cluster lca(node u, node v) const;
 381         LHTreeNode *lca(
 382                 LHTreeNode *uNode,
 383                 LHTreeNode *vNode,
 384                 LHTreeNode **uChild,
 385                 LHTreeNode **vChild) const;
 386
 387         edge addEdge(node u, node v, bool addAlways = false);
 388         void assignAeLevel(cluster c, int &count);
 389         bool reachable(node v, node u, SListPure<node> &successors);
 390         void moveDown(node v, const SListPure<node> &successors, NodeArray<int> &level);
 391         bool tryEdge(node u, node v, Graph &G, NodeArray<int> &level);
 392
 393         RCCrossings reduceCrossings(LHTreeNode *cNode, bool dirTopDown);
 394         void assignPos(const LHTreeNode *vNode, int &count);
 395
 396 private:
 397         void computeRanking();
 398         void createDummyNodes();
 399         void createVirtualClusters();
 400         void createVirtualClusters(
 401                 cluster c,
 402                 NodeArray<node> &vCopy,
 403                 ClusterArray<node> &cCopy);
 404         void buildLayers();
 405         void removeAuxNodes();
 406
 407         // original graph
 408         //const ClusterGraph &m_CG;
 409         ClusterGraphCopy m_CGC;
 410
 411         // mapping: nodes in CG <-> nodes in this copy
 412         NodeArray<node>    m_copy;
 413         NodeArray<node>    m_origNode;
 414
 415         // mapping: clusters in CG <-> nodes in this copy
 416         ClusterArray<node> m_topNode;     // the node representing top-most part of cluster (min. rank)
 417         ClusterArray<node> m_bottomNode;  // the node representing bottom-most part of cluster (max. rank)
 418         ClusterArray<int> m_topRank;
 419         ClusterArray<int> m_bottomRank;
 420
 421         // the type of a node in this copy
 422         NodeArray<NodeType> m_type;
 423
 424         // mapping: edges in CG <-> edges in this copy
 425         EdgeArray<List<edge> > m_copyEdge;
 426         EdgeArray<edge>        m_origEdge;
 427
 428         // level of each node
 429         NodeArray<int>     m_rank;
 430         int                m_numLayers;
 431
 432         // the layers
 433         Array<ENGLayer> m_layer;
 434         // positions within a layer
 435         NodeArray<int>  m_pos;
 436
 437         // can an edge segment be drawn vertically?
 438         EdgeArray<bool> m_vertical;
 439
 440         // temporary data for "addEdge()"
 441         NodeArray<int>  m_aeLevel;
 442         NodeArray<bool> m_aeVisited;
 443         NodeArray<int>  m_auxDeg;
 444
 445         // temporary data for "lca()"
 446         mutable ClusterArray<cluster> m_mark;
 447         mutable SListPure<cluster>    m_markedClusters;
 448         mutable cluster               m_secondPath;
 449         mutable node                  m_secondPathTo;
 450         mutable SListPure<cluster>    m_markedClustersTree;
 451         mutable ClusterArray<LHTreeNode*> m_markTree;
 452 };
 453
 454
 455 } // end namespace ogdf
 456
 457
 458 #endif