ext/OGDF/ogdf/upward/LayerBasedUPRLayout.h

   1 /*
   2  * $Revision: 2524 $
   3  *
   4  * last checkin:
   5  *   $Author: gutwenger $
   6  *   $Date: 2012-07-03 09:54:22 +0200 (Tue, 03 Jul 2012) $
   7  ***************************************************************/
   8
   9 /** \file
  10  * \brief Declaration of upward planarization layout algorithm.
  11  *
  12  * \author Hoi-Ming Wong
  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 #ifdef _MSC_VER
  44 #pragma once
  45 #endif
  46
  47 #ifndef OGDF_LAYER_BASED_UPR_LAYOUT_H
  48 #define OGDF_LAYER_BASED_UPR_LAYOUT_H
  49
  50
  51
  52 #include <ogdf/basic/ModuleOption.h>
  53 #include <ogdf/upward/UpwardPlanRep.h>
  54 #include <ogdf/module/RankingModule.h>
  55 #include <ogdf/module/UPRLayoutModule.h>
  56 #include <ogdf/module/HierarchyLayoutModule.h>
  57 #include <ogdf/layered/OptimalHierarchyLayout.h>
  58 #include <ogdf/layered/FastHierarchyLayout.h>
  59 #include <ogdf/layered/OptimalRanking.h>
  60
  61
  62 namespace ogdf {
  63
  64 class OrderComparer
  65 {
  66 public:
  67         OrderComparer(const UpwardPlanRep &_UPR, Hierarchy &_H);
  68
  69         // if vH1 and vH2 are placed on the same layer and node vH1 has to drawn on the lefthand side of vH2 (according to UPR) then return true;
  70         bool less(node vH1, node vH2) const ;
  71
  72 private:
  73         const UpwardPlanRep &UPR;
  74         Hierarchy &H;
  75         NodeArray<int> dfsNum;
  76         //EdgeArray<int> outEdgeOrder;
  77         mutable NodeArray<bool> crossed;
  78
  79         //traverse with dfs using edge order from left to right and compute the dfs number.
  80         void dfs_LR( edge e,
  81                                  NodeArray<bool> &visited,
  82                                  NodeArray<int> &dfsNum,
  83                                  int &num);
  84
  85         //return true if vUPR1 is on the lefthand side of vUPR2 according to UPR.
  86         bool left(node vUPR1,
  87                         List<edge> chain1, //if vUPR1 is associated with a long edge dummy vH1, then chain1 contain vH1
  88                         node vUPR2 ,
  89                         List<edge> chain2 // if vUPR2 is associated with a long edge dummy vH2, then chain2 contain vH2
  90                         ) const;
  91
  92         //return true if vUPR1 is on the lefthand side of vUPR2 according to UPR.
  93         // pred.: source or target of both edge muss identical
  94         bool left(edge e1UPR, edge e2UPR) const;
  95
  96         //return true if vUPR1 is on the lefthand side of vUPR2 according to UPR.
  97         // use only by method less for the case when both node vH1 and vH2 are long-edge dummies.
  98         // level: the current level of the long-edge dummies
  99         bool left(List<edge> &chain1, List<edge> &chain2, int level) const;
 100
 101         //return true if there is a node above vUPR with rank level or lower
 102         bool checkUp(node vUPR, int level) const;
 103 };
 104
 105
 106 class OGDF_EXPORT LayerBasedUPRLayout : public UPRLayoutModule
 107 {
 108 public:
 109
 110         // constructor: sets options to default values
 111         LayerBasedUPRLayout()
 112         {
 113                 // set default value
 114                 FastHierarchyLayout *fhl = new FastHierarchyLayout();
 115                 fhl->nodeDistance(40.0);
 116                 fhl->layerDistance(40.0);
 117                 fhl->fixedLayerDistance(true);
 118                 m_layout.set(fhl);
 119                 OptimalRanking *opRank = new OptimalRanking();
 120                 opRank->separateMultiEdges(false);
 121                 m_ranking.set(opRank);
 122                 m_numLevels = 0;
 123                 m_maxLevelSize = 0;
 124         }
 125
 126         // destructor
 127         ~LayerBasedUPRLayout() { }
 128
 129         // returns the number of crossings in the layout after the algorithm
 130         // has been applied
 131         int numberOfCrossings() const { return m_crossings; }
 132
 133         // module option for the computation of the final layout
 134         void setLayout(HierarchyLayoutModule *pLayout) {
 135                 m_layout.set(pLayout);
 136         }
 137
 138
 139         void setRanking(RankingModule *pRanking) {
 140                 m_ranking.set(pRanking);
 141         }
 142
 143         //! Use only the 3. phase of Sugiyama' framework for layout.
 144         void UPRLayoutSimple(const UpwardPlanRep &UPR, GraphAttributes &AG);
 145
 146         //! Return the number of layers/levels. Not implemented if use methode callSimple(..).
 147         int numberOfLayers() { return m_numLevels; }
 148
 149         //! Return the max. number of elements on a layer. Not implemented if use methode callSimple(..).
 150         int maxLayerSize() { return m_maxLevelSize; }
 151
 152 protected :
 153
 154         /*
 155          * @param UPR is the upward planarized representation of the input graph.
 156          * @param AG has to be assigned the hierarchy layout.
 157          */
 158         virtual void doCall(const UpwardPlanRep &UPR, GraphAttributes &AG);
 159
 160         int m_crossings;
 161
 162         ModuleOption<RankingModule> m_ranking;
 163
 164         ModuleOption<HierarchyLayoutModule> m_layout;
 165
 166
 167         struct RankComparer {
 168                 Hierarchy *H;
 169                 bool less(node v1, node v2) const {
 170                         return (H->rank(v1) < H->rank(v2));
 171                 }
 172         };
 173
 174
 175 private:
 176
 177         // compute a ranking of the nodes of UPR.
 178         // Precond. a ranking module muss be set
 179         void computeRanking(const UpwardPlanRep &UPR, NodeArray<int> &rank);
 180
 181
 182         //! rearanging the position of the sources in order to reduce some crossings.
 183         void postProcessing_sourceReorder(Hierarchy &H, List<node> &sources);
 184
 185
 186         //! reduce the long edge dummies (LED)
 187         void postProcessing_reduceLED(Hierarchy &H, List<node> &sources) {
 188                 forall_listiterators(node, it, sources)
 189                         postProcessing_reduceLED(H, *it);
 190         }
 191
 192         void postProcessing_reduceLED(Hierarchy &H, node vH);
 193
 194         void post_processing_reduce(Hierarchy &H, int &i, node s, int minIdx, int maxIdx, NodeArray<bool> &markedNodes);
 195
 196         //! mark all the nodes dominated by sH. (Help method for postProcessing_reduceLED() )
 197         void postProcessing_markUp(Hierarchy &H, node sH, NodeArray<bool> &markedNodes);
 198
 199
 200         //! delete level i of H.
 201         void post_processing_deleteLvl(Hierarchy &H, int i);
 202
 203         //! delete the interval [beginIdx,endIdx] on the level j.
 204         void post_processing_deleteInterval(Hierarchy &H, int beginIdx, int endIdx, int &j);
 205
 206         //! insert the interval  [beginIdx,endIdx] of level i-1 to level i at position pos.
 207         void post_processing_CopyInterval(Hierarchy &H, int i, int beginIdx, int endIdx, int pos);
 208
 209         int m_numLevels;
 210         int m_maxLevelSize;
 211
 212
 213
 214         //------------------------ UPRLayoutSimple methods --------------------------------------------
 215         void callSimple(GraphAttributes &AG, adjEntry adj //left most edge of the source
 216                                         );
 217
 218         // needed for UPRLayoutSimple
 219         void dfsSortLevels(
 220                 adjEntry adj1,
 221                 const NodeArray<int> &rank,
 222                 Array<SListPure<node> > &nodes);
 223
 224         // needed for UPRLayoutSimple
 225         void longestPathRanking(const Graph &G, NodeArray<int> &rank);
 226
 227
 228 };
 229
 230 }
 231
 232 #endif