1 /** \file
2 * \brief Declration of stress minimized layout based on majorization.
3 * It can be applied to connected as well as unconnected graphs. If
4 * the graph is disconnected either the infinite distances will be
5 * replaced by the average edge costs times sqrt(n) or the components
6 * will be processed separately.
7 *
8 * \author Mark Ortmann, University of Konstanz
9 *
10 * \par License:
11 * This file is part of the Open Graph Drawing Framework (OGDF).
12 *
13 * \par
14 * Copyright (C)<br>
15 * See README.md in the OGDF root directory for details.
16 *
17 * \par
18 * This program is free software; you can redistribute it and/or
19 * modify it under the terms of the GNU General Public License
20 * Version 2 or 3 as published by the Free Software Foundation;
21 * see the file LICENSE.txt included in the packaging of this file
22 * for details.
23 *
24 * \par
25 * This program is distributed in the hope that it will be useful,
26 * but WITHOUT ANY WARRANTY; without even the implied warranty of
27 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
28 * GNU General Public License for more details.
29 *
30 * \par
31 * You should have received a copy of the GNU General Public
32 * License along with this program; if not, see
33 * http://www.gnu.org/copyleft/gpl.html
34 */
35
36 #pragma once
37
38 #include <ogdf/basic/LayoutModule.h>
39 #include <ogdf/energybased/PivotMDS.h>
40 #include <ogdf/basic/simple_graph_alg.h>
41 #include <ogdf/graphalg/ShortestPathAlgorithms.h>
42 #include <ogdf/packing/ComponentSplitterLayout.h>
43
44 namespace ogdf {
45
46 //! Energy-based layout using stress minimization.
47 /**
48 * @ingroup gd-energy
49 */
50 class OGDF_EXPORT StressMinimization: public LayoutModule {
51
52 public:
53 enum class TerminationCriterion {
54 None, PositionDifference, Stress
55 };
56
57 //! Constructor: Constructs instance of stress majorization.
StressMinimization()58 StressMinimization() :
59 m_hasEdgeCostsAttribute(false), m_hasInitialLayout(false), m_numberOfIterations(
60 200), m_edgeCosts(100), m_avgEdgeCosts(-1), m_componentLayout(
61 false), m_terminationCriterion(TerminationCriterion::None), m_fixXCoords(false), m_fixYCoords(
62 false), m_fixZCoords(false) {
63 }
64
65 //! Destructor.
~StressMinimization()66 ~StressMinimization() {
67 }
68
69 //! Calls the layout algorithm with uniform edge costs.
70 virtual void call(GraphAttributes& GA) override;
71
72 //! Tells whether the current layout should be used or the initial layout
73 //! needs to be computed.
74 inline void hasInitialLayout(bool hasInitialLayout);
75
76 //! Tells whether the x coordinates are allowed to be modified or not.
77 inline void fixXCoordinates(bool fix);
78
79 //! Tells whether the y coordinates are allowed to be modified or not.
80 inline void fixYCoordinates(bool fix);
81
82 //! Tells whether the z coordinates are allowed to be modified or not.
83 inline void fixZCoordinates(bool fix);
84
85 //! Sets whether the graph's components should be layouted separately or a dummy
86 //! distance should be used for nodes within different components.
87 inline void layoutComponentsSeparately(bool separate);
88
89 //! Sets the desired distance between adjacent nodes. If the new value is smaller or equal
90 //! 0 the default value (100) is used.
91 inline void setEdgeCosts(double edgeCosts);
92
93 //! Sets a fixed number of iterations for stress majorization. If the new value is smaller or equal
94 //! 0 the default value (200) is used.
95 inline void setIterations(int numberOfIterations);
96
97 //! Tells which TerminationCriterion should be used
98 inline void convergenceCriterion(TerminationCriterion criterion);
99
100 //! Tells whether the edge costs are uniform or defined by some edge costs attribute.
101 inline void useEdgeCostsAttribute(bool useEdgeCostsAttribute);
102
103 private:
104
105 //! Convergence constant.
106 const static double EPSILON;
107
108 //! Default number of pivots used for the initial Pivot-MDS layout
109 const static int DEFAULT_NUMBER_OF_PIVOTS;
110
111 //! Tells whether the stress minimization is based on uniform edge costs or a
112 //! edge costs attribute
113 bool m_hasEdgeCostsAttribute;
114
115 //! Tells whether an initial layout has to be computed or not.
116 bool m_hasInitialLayout;
117
118 //! Number of iterations performed by the stress minimization.
119 int m_numberOfIterations;
120
121 //! The weight of an edge.
122 double m_edgeCosts;
123
124 //! The average edge costs. Needed to define distances of nodes belonging to
125 //! different graph components.
126 double m_avgEdgeCosts;
127
128 //! Indicates whether the components should be treated separately.
129 bool m_componentLayout;
130
131 //! Indicates whether epsilon convergence is used or not.
132 TerminationCriterion m_terminationCriterion;
133
134 //! Indicates whether the x coordinates will be modified or not.
135 bool m_fixXCoords;
136
137 //! Indicates whether the y coordinates will be modified or not.
138 bool m_fixYCoords;
139
140 //! Indicates whether the z coordinates will be modified or not.
141 bool m_fixZCoords;
142
143 //! Calculates the stress for the given layout
144 double calcStress(const GraphAttributes& GA,
145 NodeArray<NodeArray<double> >& shortestPathMatrix,
146 NodeArray<NodeArray<double> >& weightMatrix);
147
148 //! Runs the stress for a given Graph, shortest path and weight matrix.
149 void call(GraphAttributes& GA,
150 NodeArray<NodeArray<double> >& shortestPathMatrix,
151 NodeArray<NodeArray<double> >& weightMatrix);
152
153 //! Calculates the weight matrix of the shortest path matrix. This is done by w_ij = s_ij^{-2}
154 void calcWeights(const Graph& G,
155 NodeArray<NodeArray<double> >& shortestPathMatrix,
156 NodeArray<NodeArray<double> >& weightMatrix);
157
158 //! Calculates the intial layout of the graph if necessary.
159 void computeInitialLayout(GraphAttributes& GA);
160
161 //! Convenience method copying the layout of the graph in case of epsilon convergence.
162 void copyLayout(const GraphAttributes& GA, NodeArray<double>& newX,
163 NodeArray<double>& newY);
164
165 //! Convenience method copying the layout of the graph in case of epsilon convergence for 3D.
166 void copyLayout(const GraphAttributes& GA, NodeArray<double>& newX,
167 NodeArray<double>& newY, NodeArray<double>& newZ);
168
169 //! Checks for epsilon convergence and whether the performed number of iterations
170 //! exceed the predefined maximum number of iterations.
171 bool finished(GraphAttributes& GA, int numberOfPerformedIterations,
172 NodeArray<double>& prevXCoords, NodeArray<double>& prevYCoords,
173 const double prevStress, const double curStress);
174
175 //! Convenience method to initialize the matrices.
176 void initMatrices(const Graph& G,
177 NodeArray<NodeArray<double> >& shortestPathMatrix,
178 NodeArray<NodeArray<double> >& weightMatrix);
179
180 //! Minimizes the stress for each component separately given
181 //! the shortest path matrix and the weight matrix.
182 void minimizeStress(GraphAttributes& GA,
183 NodeArray<NodeArray<double> >& shortestPathMatrix,
184 NodeArray<NodeArray<double> >& weightMatrix);
185
186 //! Runs the next iteration of the stress minimization process. Note that serial update
187 //! is used.
188 void nextIteration(GraphAttributes& GA,
189 NodeArray<NodeArray<double> >& shortestPathMatrix,
190 NodeArray<NodeArray<double> >& weightMatrix);
191
192 //! Replaces infinite distances to the given value
193 void replaceInfinityDistances(
194 NodeArray<NodeArray<double> >& shortestPathMatrix, double newVal);
195
196 }
197 ;
198
fixXCoordinates(bool fix)199 void StressMinimization::fixXCoordinates(bool fix) {
200 m_fixXCoords = fix;
201 }
202
fixYCoordinates(bool fix)203 void StressMinimization::fixYCoordinates(bool fix) {
204 m_fixYCoords = fix;
205 }
206
hasInitialLayout(bool hasInitialLayout)207 void StressMinimization::hasInitialLayout(bool hasInitialLayout) {
208 m_hasInitialLayout = hasInitialLayout;
209 }
210
layoutComponentsSeparately(bool separate)211 void StressMinimization::layoutComponentsSeparately(bool separate) {
212 m_componentLayout = separate;
213 }
214
setEdgeCosts(double edgeCosts)215 void StressMinimization::setEdgeCosts(double edgeCosts) {
216 m_edgeCosts = (edgeCosts > 0) ? edgeCosts : 100;
217 }
218
setIterations(int numberOfIterations)219 void StressMinimization::setIterations(int numberOfIterations) {
220 m_numberOfIterations = (numberOfIterations > 0) ? numberOfIterations : 100;
221 }
222
convergenceCriterion(TerminationCriterion criterion)223 void StressMinimization::convergenceCriterion(TerminationCriterion criterion) {
224 m_terminationCriterion = criterion;
225 }
226
useEdgeCostsAttribute(bool useEdgeCostsAttribute)227 void StressMinimization::useEdgeCostsAttribute(bool useEdgeCostsAttribute) {
228 m_hasEdgeCostsAttribute = useEdgeCostsAttribute;
229 }
230
231 }
232