1/** \file
2 * \brief Declaration and implementation of the optimal third
3 * phase of the Sugiyama algorithm.
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/module/HierarchyLayoutModule.h>
36
37
38namespace ogdf {
39
40
41//! The LP-based hierarchy layout algorithm.
42/**
43 * @ingroup gd-hlm
44 *
45 * OptimalHierarchyLayout implements a hierarchy layout algorithm that is based
46 * on an LP-formulation. It is only available if OGDF is compiled with LP-solver
47 * 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>
75 * </table>
76 */
77class OGDF_EXPORT OptimalHierarchyLayout : public HierarchyLayoutModule
78{
79public:
80 //! Creates an instance of optimal hierarchy layout.
81 OptimalHierarchyLayout();
82
83 //! Copy constructor.
84 OptimalHierarchyLayout(const OptimalHierarchyLayout &);
85
86 // destructor
87 ~OptimalHierarchyLayout() { }
88
89
90 //! Assignment operator.
91 OptimalHierarchyLayout &operator=(const OptimalHierarchyLayout &);
92
93
94 /**
95 * @name Optional parameters
96 * @{
97 */
98
99 //! Returns the minimal allowed x-distance between nodes on a layer.
100 double nodeDistance() const {
101 return m_nodeDistance;
102 }
103
104 //! Sets the minimal allowed x-distance between nodes on a layer to \p x.
105 void nodeDistance(double x) {
106 if(x >= 0)
107 m_nodeDistance = x;
108 }
109
110 //! Returns the minimal allowed y-distance between layers.
111 double layerDistance() const {
112 return m_layerDistance;
113 }
114
115 //! Sets the minimal allowed y-distance between layers to \p x.
116 void layerDistance(double x) {
117 if(x >= 0)
118 m_layerDistance = x;
119 }
120
121 //! Returns the current setting of option <i>fixedLayerDistance</i>.
122 /**
123 * If set to true, the distance is always layerDistance; otherwise
124 * the distance is adjusted (increased) to improve readability.
125 */
126 bool fixedLayerDistance() const {
127 return m_fixedLayerDistance;
128 }
129
130 //! Sets the option <i>fixedLayerDistance</i> to \p b.
131 void fixedLayerDistance(bool b) {
132 m_fixedLayerDistance = b;
133 }
134
135 //! Returns the weight of edge segments connecting to vertical segments.
136 double weightSegments() const {
137 return m_weightSegments;
138 }
139
140 //! Sets the weight of edge segments connecting to vertical segments to \p w.
141 void weightSegments(double w) {
142 if(w > 0.0 && w <= 100.0)
143 m_weightSegments = w;
144 }
145
146 //! Returns the weight for balancing successors below a node; 0.0 means no balancing.
147 double weightBalancing() const {
148 return m_weightBalancing;
149 }
150
151 //! Sets the weight for balancing successors below a node to \p w; 0.0 means no balancing.
152 void weightBalancing(double w) {
153 if(w >= 0.0 && w <= 100.0)
154 m_weightBalancing = w;
155 }
156
157 //! @}
158
159protected:
160 //! Implements the algorithm call.
161 virtual void doCall(const HierarchyLevelsBase &levels,GraphCopyAttributes &AGC) override;
162
163private:
164 void computeXCoordinates(
165 const HierarchyLevelsBase &levels,
166 GraphCopyAttributes &AGC);
167 void computeYCoordinates(
168 const HierarchyLevelsBase &levels,
169 GraphCopyAttributes &AGC);
170
171 // options
172 double m_nodeDistance; //!< The minimal distance between nodes.
173 double m_layerDistance; //!< The minimal distance between layers.
174 bool m_fixedLayerDistance; //!< Use fixed layer distances?
175
176 double m_weightSegments; //!< The weight of edge segments.
177 double m_weightBalancing; //!< The weight for balancing.
178};
179
180}
181