ext/OGDF/ogdf/layered/Hierarchy.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 Hierarchy class.
  11  *
  12  * \author Carsten Gutwenger
  13  *
  14  * \par License:
  15  * This file is part of the Open Graph Drawing Framework (OGDF).
  16  *
  17  * \par
  18  * Copyright (C)<br>
  19  * See README.txt in the root directory of the OGDF installation for details.
  20  *
  21  * \par
  22  * This program is free software; you can redistribute it and/or
  23  * modify it under the terms of the GNU General Public License
  24  * Version 2 or 3 as published by the Free Software Foundation;
  25  * see the file LICENSE.txt included in the packaging of this file
  26  * for details.
  27  *
  28  * \par
  29  * This program is distributed in the hope that it will be useful,
  30  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  31  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  32  * GNU General Public License for more details.
  33  *
  34  * \par
  35  * You should have received a copy of the GNU General Public
  36  * License along with this program; if not, write to the Free
  37  * Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  38  * Boston, MA 02110-1301, USA.
  39  *
  40  * \see  http://www.gnu.org/copyleft/gpl.html
  41  ***************************************************************/
  42
  43
  44 #ifdef _MSC_VER
  45 #pragma once
  46 #endif
  47
  48 #ifndef OGDF_HIERARCHY_H
  49 #define OGDF_HIERARCHY_H
  50
  51
  52 #include <ogdf/basic/EdgeArray.h>
  53 #include <ogdf/layered/Level.h>
  54 #include <ogdf/basic/GraphCopy.h>
  55
  56
  57 namespace ogdf {
  58
  59
  60 //! Representation of proper hierarchies used by Sugiyama-layout.
  61 /**
  62  * \see Level, SugiyamaLayout
  63  */
  64 class OGDF_EXPORT Hierarchy {
  65 public:
  66         friend class Level;
  67
  68         friend class LayerBasedUPRLayout;
  69         friend class HierarchyLayoutModule;
  70
  71         //! The traversing direction of the layer-by-layer sweep.
  72         enum TraversingDir { downward, upward };
  73
  74 private:
  75         Array<Level *> m_pLevel; //!< The array of all levels.
  76         GraphCopy m_GC; //!< The graph copy representing the topology of the proper hierarchy.
  77         NodeArray<int> m_pos;  //!< The position of a node on its level.
  78         NodeArray<int> m_rank; //!< The rank (level) of a node.
  79         //! (Sorted) adjacent nodes on lower level.
  80         NodeArray<Array<node> > m_lowerAdjNodes;
  81         //! (Sorted) adjacent nodes on upper level.
  82         NodeArray<Array<node> > m_upperAdjNodes;
  83
  84         NodeArray<int> m_nSet; //!< (Only used by buildAdjNodes().)
  85
  86         //! (Only used by calculateCrossingsPlaneSweep().)
  87         NodeArray<ListIterator<node> > m_lastOcc;
  88
  89         TraversingDir m_direction; //!< The current direction of layer-by-layer sweep.
  90
  91         bool getMarkedNodes(NodeArray<bool> &markedNodes, int r, List<node> &result, List<int> &positions) {
  92                 result.clear();
  93                 positions.clear();
  94                 bool allDummies = true;
  95
  96                 if (r > high() || r < 0)
  97                         return false;
  98
  99                 Level &lvl = *m_pLevel[r];
 100
 101                 for(int i = 0; i <= lvl.high(); i++) {
 102                         node v = lvl[i];
 103                         if (markedNodes[v]) {
 104                                 result.pushBack(v);
 105                                 positions.pushBack(pos(v));
 106                                 if (!isLongEdgeDummy(v))
 107                                         allDummies = false;
 108                         }
 109                 }
 110                 positions.quicksort();
 111                 return allDummies;
 112         }
 113
 114
 115 public:
 116         //! Creates an empty hierarchy.
 117         Hierarchy() { }
 118         //! Creates an hierarchy of graph \a G with node ranks \a rank.
 119         Hierarchy(const Graph &G, const NodeArray<int> &rank);
 120
 121         // destruction
 122         ~Hierarchy();
 123
 124         void createEmpty(const Graph &G);
 125         void initByNodes(const List<node> &nodes,
 126                 EdgeArray<edge> &eCopy,
 127                 const NodeArray<int> &rank);
 128
 129         //! Conversion to const GraphCopy reference.
 130         operator const GraphCopy &() const { return m_GC; }
 131
 132         //! Returns the current direction of layer-by-layer sweep.
 133         TraversingDir direction() const {
 134                 return m_direction;
 135         }
 136
 137         //! Sets the current direction of layer-by-layer sweep.
 138         void direction (TraversingDir dir) {
 139                 m_direction = dir;
 140         }
 141
 142         //! Returns the number of levels.
 143         int size() const { return m_pLevel.size(); }
 144
 145         //! Returns the maximal array index of a level (= size()-1).
 146         int high() const { return m_pLevel.high(); }
 147
 148         //! Returns the rank (level) of node \a v.
 149         int rank(node v) const { return m_rank[v]; }
 150
 151         //! Returns the position of node \a v on its level.
 152         int pos(node v) const { return m_pos[v]; }
 153
 154         //! Returns the adjacent nodes of \a v (according to direction()).
 155         const Array<node> &adjNodes(node v) {
 156                 return (m_direction == downward) ? m_lowerAdjNodes[v] :
 157                 m_upperAdjNodes[v];
 158         }
 159
 160         //! Returns the adjacent nodes of \a v.
 161         const Array<node> &adjNodes(node v, TraversingDir dir) const {
 162                 return (dir == downward) ? m_lowerAdjNodes[v] :
 163                 m_upperAdjNodes[v];
 164         }
 165
 166         //! Returns the adjacent level of level \a i (according to direction()).
 167         const Level &adjLevel(int i) const {
 168                 return (m_direction == downward) ? *m_pLevel[i-1] : *m_pLevel[i+1];
 169
 170         }
 171
 172         bool isLongEdgeDummy(node v) const {
 173                 return (m_GC.isDummy(v) && v->outdeg() == 1);
 174         }
 175
 176         //! Returns the <i>i</i>-th level.
 177         const Level &operator[](int i) const { return *m_pLevel[i]; }
 178
 179         //! Returns the <i>i</i>-th level.
 180         Level &operator[](int i) { return *m_pLevel[i]; }
 181
 182
 183         //! Computes the number of crossings between level \a i and \a i+1.
 184         int calculateCrossings(int i);
 185         //! Computes the total number of crossings.
 186         int calculateCrossings();
 187
 188         //! Old version of counting crossings using plane-seep algorithm (only for testing purposes).
 189         int calculateCrossingsPlaneSweep(int i);
 190         //! Old version of counting crossings using plane-seep algorithm (only for testing purposes).
 191         int calculateCrossingsPlaneSweep();
 192
 193         //! Computes the number of crossings between level \a i and \a i+1 (for simultaneous drawing).
 194         int calculateCrossingsSimDraw(int i, const EdgeArray<unsigned int> *edgeSubGraph);
 195         //! Computes the total number of crossings (for simultaneous drawing).
 196         int calculateCrossingsSimDraw(const EdgeArray<unsigned int> *edgeSubGraph);
 197
 198
 199         //! Stores the position of nodes in \a oldPos.
 200         void storePos (NodeArray<int> &oldPos);
 201         //! Restores the position of nodes from \a newPos.
 202         void restorePos (const NodeArray<int> &newPos);
 203
 204         //! Permutes the order of nodes on each level.
 205         void permute();
 206
 207         //! Adjusts node positions such that nodes are ordered according to components numbers.
 208         void separateCCs(int numCC, NodeArray<int> &component);
 209
 210         bool transpose(node v);
 211
 212         void print(ostream &os);
 213
 214         void buildAdjNodes(int i);
 215         void buildAdjNodes();
 216
 217         void check();
 218
 219 private:
 220         void doInit(const NodeArray<int> &rank);
 221
 222         int transposePart(const Array<node> &adjV, const Array<node> &adjW);
 223
 224         OGDF_MALLOC_NEW_DELETE
 225 };
 226
 227
 228 } // end namespace ogdf
 229
 230
 231 #endif