Go to the documentation of this file.00001
00002
00003
00004
00005
00006
00007
00008
00042 #ifdef _MSC_VER
00043 #pragma once
00044 #endif
00045
00046 #ifndef OGDF_SPRING_EMBEDDER_KK_H
00047 #define OGDF_SPRING_EMBEDDER_KK_H
00048
00049
00050 #include <ogdf/module/LayoutModule.h>
00051 #include <ogdf/basic/Array2D.h>
00052 #include <ogdf/basic/tuples.h>
00053
00054
00055 namespace ogdf {
00056
00057
00058 class OGDF_EXPORT GraphCopyAttributes;
00059 class OGDF_EXPORT GraphCopy;
00060
00061
00063
00093 class OGDF_EXPORT SpringEmbedderKK : public LayoutModule
00094 {
00095 public:
00096 typedef Tuple2<double, double> dpair;
00097
00100 enum Scaling {
00101 scInput,
00102 scUserBoundingBox,
00103 scScaleFunction,
00104 scScaleAdaptive
00105 };
00106
00108 SpringEmbedderKK() : m_tolerance(0.001), m_ltolerance(0.0001), m_computeMaxIt(true),
00109 m_K(5.0), m_desLength(0.0), m_distFactor(2.0), m_useLayout(true),
00110 m_gItBaseVal(50), m_gItFactor(16)
00111 {
00112 m_maxLocalIt = m_maxGlobalIt = maxVal;
00113 }
00114
00116 ~SpringEmbedderKK() {}
00117
00121 void call(GraphAttributes& GA);
00125 void call(GraphAttributes& GA, const EdgeArray<double>& eLength);
00126
00129 void setStopTolerance(double s) {m_tolerance = s;}
00130
00132 void setUseLayout(bool b) {m_useLayout = b;}
00133 bool useLayout() {return m_useLayout;}
00134
00138 void setZeroLength(double d) {m_zeroLength = d;}
00139 double zeroLength() {return m_zeroLength;}
00140
00142 void setDesLength(double d) {m_desLength = d;}
00143
00144
00148 int maxLocalIterations() const {
00149 return m_maxLocalIt;
00150 }
00151 void setGlobalIterationFactor(int i) {if (i>0) m_gItFactor = i;}
00152 int maxGlobalIterations() const {
00153 return m_maxGlobalIt;
00154 }
00156 void setMaxGlobalIterations(int i) {
00157 if (i>0)
00158 m_maxGlobalIt = i;
00159 }
00161 void setMaxLocalIterations(int i) {
00162 if (i>0)
00163 m_maxLocalIt = i;
00164 }
00166 void computeMaxIterations(bool b)
00167 {
00168 m_computeMaxIt = b;
00169 }
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179
00180
00181 protected:
00183 void doCall(GraphAttributes& GA, const EdgeArray<double>& eLength, bool simpleBFS);
00185 bool finished(double maxdelta)
00186 {
00187 if (m_prevEnergy == startVal)
00188 {
00189 m_prevEnergy = maxdelta;
00190 return false;
00191 }
00192
00193 double diff = m_prevEnergy - maxdelta;
00194 if (diff < 0.0) diff = -diff;
00195 #ifdef OGDF_DEBUG
00196 cout << "Finished(): maxdelta: "<< maxdelta<<" diff/prev: "<<diff / m_prevEnergy<<"\n";
00197 #endif
00198
00199 bool done = (maxdelta < m_tolerance);
00200
00201 m_prevEnergy = maxdelta;
00202 m_prevLEnergy = startVal;
00203
00204 return done;
00205 }
00207 bool finishedNode(double deltav)
00208 {
00209 if (m_prevLEnergy == startVal)
00210 {
00211 m_prevLEnergy = deltav;
00212 return deltav == 0.0;
00213 }
00214 #ifdef OGDF_DEBUG
00215 cout << "Local delta: "<<deltav<<"\n";
00216 #endif
00217 double diff = m_prevLEnergy - deltav;
00218
00219 bool done = (deltav == 0.0 || (diff / m_prevLEnergy) < m_ltolerance);
00220
00221 m_prevLEnergy = deltav;
00222
00223 return done;
00224 }
00227 void adaptLengths(const Graph& G,
00228 const GraphAttributes& GA,
00229 const EdgeArray<double>& eLengths,
00230 EdgeArray<double>& adaptedLengths);
00232 void shufflePositions(GraphAttributes& GA);
00235 dpair computeParDer(node m,
00236 node u,
00237 GraphAttributes& GA,
00238 NodeArray< NodeArray<double> >& ss,
00239 NodeArray< NodeArray<double> >& dist);
00241 dpair computeParDers(node v,
00242 GraphAttributes& GA,
00243 NodeArray< NodeArray<double> >& ss,
00244 NodeArray< NodeArray<double> >& dist);
00246 void initialize(GraphAttributes& GA,
00247 NodeArray<dpair>& partialDer,
00248 const EdgeArray<double>& eLength,
00249 NodeArray< NodeArray<double> >& oLength,
00250 NodeArray< NodeArray<double> >& sstrength,
00251 double & maxDist,
00252 bool simpleBFS);
00254 void mainStep(GraphAttributes& GA,
00255 NodeArray<dpair>& partialDer,
00256 NodeArray< NodeArray<double> >& oLength,
00257 NodeArray< NodeArray<double> >& sstrength,
00258 const double maxDist);
00261 void scale(GraphAttributes& GA);
00262
00263 private:
00266 double m_tolerance;
00267 double m_ltolerance;
00268 int m_maxGlobalIt;
00269 int m_maxLocalIt;
00270 bool m_computeMaxIt;
00271
00272 double m_K;
00273 double m_prevEnergy;
00274 double m_prevLEnergy;
00275 double m_zeroLength;
00276
00277 double m_desLength;
00278 double m_distFactor;
00279
00280 bool m_useLayout;
00281
00282 int m_gItBaseVal;
00283 int m_gItFactor;
00284
00285 static const double startVal;
00286 static const double minVal;
00287 static const double desMinLength;
00288
00289 static const int maxVal = INT_MAX;
00290
00291 double allpairsspBFS(const Graph& G, NodeArray< NodeArray<double> >& distance);
00292 double allpairssp(const Graph& G, const EdgeArray<double>& eLengths,
00293 NodeArray< NodeArray<double> >& distance, const double threshold = DBL_MAX);
00294 };
00295
00296
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
00308
00309
00310
00311
00312
00313
00314
00315
00316
00317
00318
00319
00320
00321
00322
00323
00324
00325
00326
00327
00328
00329
00330
00331
00332 }
00333
00334
00335 #endif