1 /** \file 2 * \brief Declaration of the optimal third phase of the sugiyama 3 * algorithm for clusters. 4 * 5 * \author Carsten Gutwenger 6 * 7 * \par License: 8 * This file is part of the Open Graph Drawing Framework (OGDF). 9 * 10 * \par 11 * Copyright (C)<br> 12 * See README.md in the OGDF root directory for details. 13 * 14 * \par 15 * This program is free software; you can redistribute it and/or 16 * modify it under the terms of the GNU General Public License 17 * Version 2 or 3 as published by the Free Software Foundation; 18 * see the file LICENSE.txt included in the packaging of this file 19 * for details. 20 * 21 * \par 22 * This program is distributed in the hope that it will be useful, 23 * but WITHOUT ANY WARRANTY; without even the implied warranty of 24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 25 * GNU General Public License for more details. 26 * 27 * \par 28 * You should have received a copy of the GNU General Public 29 * License along with this program; if not, see 30 * http://www.gnu.org/copyleft/gpl.html 31 */ 32 33 #pragma once 34 35 #include <ogdf/layered/HierarchyClusterLayoutModule.h> 36 #include <ogdf/basic/tuples.h> 37 38 namespace ogdf { 39 40 41 //! The LP-based hierarchy cluster layout algorithm. 42 /** 43 * @ingroup gd-hlm 44 * 45 * OptimalHierarchyClusterLayout implements a hierarchy layout algorithm 46 * fpr cluster graphs that is based on an LP-formulation. It is only 47 * available if OGDF is compiled with LP-solver support (e.g., Coin). 48 * 49 * The used model avoids Spaghetti-effect like routing of edges by using 50 * long vertical segments as in FastHierarchyLayout. An additional balancing 51 * can be used which balances the successors below a node. 52 * 53 * <H3>Optional parameters</H3> 54 * 55 * <table> 56 * <tr> 57 * <th><i>Option</i><th><i>Type</i><th><i>Default</i><th><i>Description</i> 58 * </tr><tr> 59 * <td><i>nodeDistance</i><td>double<td>3.0 60 * <td>The minimal allowed x-distance between nodes on a layer. 61 * </tr><tr> 62 * <td><i>layerDistance</i><td>double<td>3.0 63 * <td>The minimal allowed y-distance between layers. 64 * </tr><tr> 65 * <td><i>fixedLayerDistance</i><td>bool<td>false 66 * <td>If set to true, the distance between neighboured layers is always 67 * layerDistance; otherwise the distance is adjusted (increased) to improve readability. 68 * </tr><tr> 69 * <td><i>weightSegments</i><td>double<td>2.0 70 * <td>The weight of edge segments connecting to vertical segments. 71 * </tr><tr> 72 * <td><i>weightBalancing</i><td>double<td>0.1 73 * <td>The weight for balancing successors below a node; 0.0 means no balancing. 74 * </tr><tr> 75 * <td><i>weightClusters</i><td>double<td>0.05 76 * <td>The weight for cluster boundary variables. 77 * </tr> 78 * </table> 79 */ 80 class OGDF_EXPORT OptimalHierarchyClusterLayout : public HierarchyClusterLayoutModule 81 { 82 public: 83 //! Creates an instance of optimal hierarchy layout for clusters. 84 OptimalHierarchyClusterLayout(); 85 86 //! Copy constructor. 87 OptimalHierarchyClusterLayout(const OptimalHierarchyClusterLayout &); 88 89 // destructor ~OptimalHierarchyClusterLayout()90 ~OptimalHierarchyClusterLayout() { } 91 92 93 //! Assignment operator. 94 OptimalHierarchyClusterLayout &operator=(const OptimalHierarchyClusterLayout &); 95 96 97 /** 98 * @name Optional parameters 99 * @{ 100 */ 101 102 //! Returns the minimal allowed x-distance between nodes on a layer. nodeDistance()103 double nodeDistance() const { 104 return m_nodeDistance; 105 } 106 107 //! Sets the minimal allowed x-distance between nodes on a layer to \p x. nodeDistance(double x)108 void nodeDistance(double x) { 109 if(x >= 0) 110 m_nodeDistance = x; 111 } 112 113 //! Returns the minimal allowed y-distance between layers. layerDistance()114 double layerDistance() const { 115 return m_layerDistance; 116 } 117 118 //! Sets the minimal allowed y-distance between layers to \p x. layerDistance(double x)119 void layerDistance(double x) { 120 if(x >= 0) 121 m_layerDistance = x; 122 } 123 124 //! Returns the current setting of option <i>fixedLayerDistance</i>. 125 /** 126 * If set to true, the distance is always layerDistance; otherwise 127 * the distance is adjusted (increased) to improve readability. 128 */ fixedLayerDistance()129 bool fixedLayerDistance() const { 130 return m_fixedLayerDistance; 131 } 132 133 //! Sets the option <i>fixedLayerDistance</i> to \p b. fixedLayerDistance(bool b)134 void fixedLayerDistance(bool b) { 135 m_fixedLayerDistance = b; 136 } 137 138 //! Returns the weight of edge segments connecting to vertical segments. weightSegments()139 double weightSegments() const { 140 return m_weightSegments; 141 } 142 143 //! Sets the weight of edge segments connecting to vertical segments to \p w. weightSegments(double w)144 void weightSegments(double w) { 145 if(w > 0.0 && w <= 100.0) 146 m_weightSegments = w; 147 } 148 149 //! Returns the weight for balancing successors below a node; 0.0 means no balancing. weightBalancing()150 double weightBalancing() const { 151 return m_weightBalancing; 152 } 153 154 //! Sets the weight for balancing successors below a node to \p w; 0.0 means no balancing. weightBalancing(double w)155 void weightBalancing(double w) { 156 if(w >= 0.0 && w <= 100.0) 157 m_weightBalancing = w; 158 } 159 160 //! Returns the weight for cluster boundary variables. weightClusters()161 double weightClusters() const { 162 return m_weightClusters; 163 } 164 165 //! Sets the weight for cluster boundary variables to \p w. weightClusters(double w)166 void weightClusters(double w) { 167 if(w > 0.0 && w <= 100.0) 168 m_weightClusters = w; 169 } 170 171 //! @} 172 173 protected: 174 //! Implements the algorithm call. 175 virtual void doCall(const ExtendedNestingGraph& H,ClusterGraphCopyAttributes &ACGC) override; 176 177 private: 178 void buildLayerList( 179 const LHTreeNode *vNode, 180 List<Tuple2<int,double> > &L); 181 182 void computeXCoordinates( 183 const ExtendedNestingGraph& H, 184 ClusterGraphCopyAttributes &AGC); 185 void computeYCoordinates( 186 const ExtendedNestingGraph& H, 187 ClusterGraphCopyAttributes &AGC); 188 189 // options 190 double m_nodeDistance; //!< The minimal distance between nodes. 191 double m_layerDistance; //!< The minimal distance between layers. 192 bool m_fixedLayerDistance; //!< Use fixed layer distances? 193 194 double m_weightSegments; //!< The weight of edge segments. 195 double m_weightBalancing; //!< The weight for balancing. 196 double m_weightClusters; //!< The weight for cluster boundary variables. 197 198 // auxiliary data 199 ClusterGraphCopyAttributes *m_pACGC; 200 const ExtendedNestingGraph *m_pH; 201 202 int m_vertexOffset; 203 int m_segmentOffset; 204 int m_clusterLeftOffset; 205 int m_clusterRightOffset; 206 207 NodeArray<bool> m_isVirtual; 208 NodeArray<int> m_vIndex; 209 ClusterArray<int> m_cIndex; 210 }; 211 212 } 213