ext/OGDF/ogdf/upward/DominanceLayout.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 dominance 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 //***
  44 // Dominance Drawing Method. see "Graph Drawing" by Di Battista et al.
  45 //***
  46
  47
  48
  49 #ifdef _MSC_VER
  50 #pragma once
  51 #endif
  52
  53 #ifndef OGDF_DOMINANCE_LAYOUT_H
  54 #define OGDF_DOMINANCE_LAYOUT_H
  55
  56
  57 #include <ogdf/basic/GraphAttributes.h>
  58 #include <ogdf/basic/ModuleOption.h>
  59 #include <ogdf/basic/Math.h>
  60 #include <ogdf/module/LayoutModule.h>
  61 #include <ogdf/module/UpwardPlanarizerModule.h>
  62 #include <ogdf/upward/UpwardPlanRep.h>
  63 #include <ogdf/upward/SubgraphUpwardPlanarizer.h>
  64
  65 namespace ogdf {
  66
  67
  68 class OGDF_EXPORT DominanceLayout : public LayoutModule
  69 {
  70 public:
  71
  72         DominanceLayout() {
  73                 m_grid_dist = 1;
  74                 // set default module
  75                 m_upPlanarizer.set(new SubgraphUpwardPlanarizer());
  76
  77                 m_angle = 45.0 / 180.0 * Math::pi;
  78
  79         }
  80
  81         virtual void call(GraphAttributes &GA);
  82
  83         void layout(GraphAttributes &GA, const UpwardPlanRep &UPROrig);
  84
  85         void setUpwardPlanarizer(UpwardPlanarizerModule *upPlanarizer) {
  86                 m_upPlanarizer.set(upPlanarizer);
  87         }
  88
  89         void setMinGridDistance(int dist) {m_grid_dist = dist;}
  90
  91
  92
  93 private:
  94
  95         double m_angle; //rotate angle to obtain an upward drawing; default is 45°
  96
  97         NodeArray<edge> firstout;
  98         NodeArray<edge> lastout;
  99         NodeArray<edge> firstin;
 100         NodeArray<edge> lastin;
 101
 102         int m_R;
 103         int m_L;
 104
 105         // list of nodes sorted by their x and y coordinate.
 106         List<node> xNodes;
 107         List<node> yNodes;
 108
 109         //coordinate in preliminary layout
 110         NodeArray<int> xPreCoord;
 111         NodeArray<int> yPreCoord;
 112
 113         //final coordinate  of the nodes of the UPR
 114         NodeArray<int> xCoord;
 115         NodeArray<int> yCoord;
 116
 117
 118         //min grid distance
 119         int m_grid_dist;
 120
 121         ModuleOption<UpwardPlanarizerModule> m_upPlanarizer; // upward planarizer
 122
 123         void labelX(const UpwardPlanRep &UPR, node v, int &count);
 124
 125         void labelY(const UpwardPlanRep &UPR, node v, int &count);
 126
 127         void compact(const UpwardPlanRep &UPR, GraphAttributes &GA);
 128
 129         void findTransitiveEdges(const UpwardPlanRep &UPR, List<edge> &edges);
 130
 131 };
 132
 133
 134 }//namespace
 135
 136 #endif