1 /** \file
2 * \brief Declaration of the pivot MDS. By setting the number of pivots to
3 * infinity this algorithm behaves just like classical MDS.
4 * See Brandes and Pich: Eigensolver methods for progressive multidi-
5 * mensional scaling of large data.
6 *
7 * \author Mark Ortmann, University of Konstanz
8 *
9 * \par License:
10 * This file is part of the Open Graph Drawing Framework (OGDF).
11 *
12 * \par
13 * Copyright (C)<br>
14 * See README.md in the OGDF root directory for details.
15 *
16 * \par
17 * This program is free software; you can redistribute it and/or
18 * modify it under the terms of the GNU General Public License
19 * Version 2 or 3 as published by the Free Software Foundation;
20 * see the file LICENSE.txt included in the packaging of this file
21 * for details.
22 *
23 * \par
24 * This program is distributed in the hope that it will be useful,
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
27 * GNU General Public License for more details.
28 *
29 * \par
30 * You should have received a copy of the GNU General Public
31 * License along with this program; if not, see
32 * http://www.gnu.org/copyleft/gpl.html
33 */
34
35 #pragma once
36
37 #include <ogdf/basic/simple_graph_alg.h>
38 #include <ogdf/graphalg/ShortestPathAlgorithms.h>
39 #include <ogdf/basic/LayoutModule.h>
40
41 namespace ogdf {
42
43 template<typename T>
isinf(T value)44 inline bool isinf(T value)
45 {
46 return std::numeric_limits<T>::has_infinity &&
47 value == std::numeric_limits<T>::infinity();
48 }
49
50
51 //! The Pivot MDS (multi-dimensional scaling) layout algorithm.
52 /**
53 * @ingroup gd-energy
54 */
55 class OGDF_EXPORT PivotMDS : public LayoutModule {
56 public:
PivotMDS()57 PivotMDS() : m_numberOfPivots(250), m_edgeCosts(100), m_hasEdgeCostsAttribute(false) { }
58
~PivotMDS()59 virtual ~PivotMDS() { }
60
61 //! Sets the number of pivots. If the new value is smaller or equal 0
62 //! the default value (250) is used.
setNumberOfPivots(int numberOfPivots)63 void setNumberOfPivots(int numberOfPivots) {
64 m_numberOfPivots = (numberOfPivots < DIMENSION_COUNT) ? DIMENSION_COUNT : numberOfPivots;
65 }
66
67 //! Sets the desired distance between adjacent nodes. If the new value is smaller or equal
68 //! 0 the default value (100) is used.
setEdgeCosts(double edgeCosts)69 void setEdgeCosts(double edgeCosts){
70 m_edgeCosts = edgeCosts;
71 }
72
73 //! Calls the layout algorithm for graph attributes \p GA.
74 virtual void call(GraphAttributes& GA) override;
75
76
useEdgeCostsAttribute(bool useEdgeCostsAttribute)77 void useEdgeCostsAttribute(bool useEdgeCostsAttribute) {
78 m_hasEdgeCostsAttribute = useEdgeCostsAttribute;
79 }
80
useEdgeCostsAttribute()81 bool useEdgeCostsAttribute() const {
82 return m_hasEdgeCostsAttribute;
83 }
84
85 private:
86
87 //! The dimension count determines the number of evecs that
88 //! will be computed. Nevertheless PivotMDS only takes the first two
89 //! with the highest eigenwert into account.
90 const static int DIMENSION_COUNT = 2;
91
92 //! Convergence factor used for power iteration.
93 const static double EPSILON;
94
95 //! Factor used to center the pivot matrix.
96 const static double FACTOR;
97
98 //! Seed of the random number generator.
99 const static unsigned int SEED = 0;
100
101 //! The number of pivots.
102 int m_numberOfPivots;
103
104 //! The costs to traverse an edge.
105 double m_edgeCosts;
106
107 //! Tells whether the pivot mds is based on uniform edge costs or a
108 //! edge costs attribute
109 bool m_hasEdgeCostsAttribute;
110
111 //! Centers the pivot matrix.
112 void centerPivotmatrix(Array<Array<double> >& pivotMatrix);
113
114 //! Computes the pivot mds layout of the given connected graph of \p GA.
115 void pivotMDSLayout(GraphAttributes& GA);
116
117 void copySPSS(Array<double>& copyTo, NodeArray<double>& copyFrom);
118
119 //! Computes the layout of a path.
120 void doPathLayout(GraphAttributes& GA, const node& v);
121
122 //! Computes the eigen value decomposition based on power iteration.
123 void eigenValueDecomposition(
124 Array<Array<double> >& K,
125 Array<Array<double> >& eVecs,
126 Array<double>& eValues);
127
128 //! Computes the pivot distance matrix based on the maxmin strategy
129 void getPivotDistanceMatrix(const GraphAttributes& GA, Array<Array<double> >& pivDistMatrix);
130
131 //! Checks whether the given graph is a path or not.
132 node getRootedPath(const Graph& G);
133
134 //! Normalizes the vector \p x.
135 double normalize(Array<double>& x);
136
137 //! Computes the product of two vectors \p x and \p y.
138 double prod(const Array<double>& x, const Array<double>& y);
139
140 //! Fills the given \p matrix with random doubles d 0 <= d <= 1.
141 void randomize(Array<Array<double> >& matrix);
142
143 //! Computes the self product of \p d.
144 void selfProduct(const Array<Array<double> >&d, Array<Array<double> >& result);
145
146 //! Computes the singular value decomposition of matrix \p K.
147 void singularValueDecomposition(
148 Array<Array<double> >& K,
149 Array<Array<double> >& eVecs,
150 Array<double>& eVals);
151 };
152
153 }
154