Open
Graph Drawing
Framework

 v.2012.07
 

SpringEmbedderKK.h
Go to the documentation of this file.
1 /*
2  * $Revision: 2524 $
3  *
4  * last checkin:
5  * $Author: gutwenger $
6  * $Date: 2012-07-03 09:54:22 +0200 (Tue, 03 Jul 2012) $
7  ***************************************************************/
8 
44 #ifdef _MSC_VER
45 #pragma once
46 #endif
47 
48 #ifndef OGDF_SPRING_EMBEDDER_KK_H
49 #define OGDF_SPRING_EMBEDDER_KK_H
50 
51 
53 #include <ogdf/basic/Array2D.h>
54 #include <ogdf/basic/tuples.h>
55 
56 
57 namespace ogdf {
58 
59 
60  class OGDF_EXPORT GraphCopyAttributes;
61  class OGDF_EXPORT GraphCopy;
62 
63 
65 
96 {
97 public:
99 
102  enum Scaling {
106  scScaleAdaptive
107  };
108 
110  SpringEmbedderKK() : m_tolerance(0.001), m_ltolerance(0.0001), m_computeMaxIt(true),
111  m_K(5.0), m_desLength(0.0), m_distFactor(2.0), m_useLayout(true),
112  m_gItBaseVal(50), m_gItFactor(16)
113  {
114  m_maxLocalIt = m_maxGlobalIt = maxVal;
115  }
116 
119 
123  void call(GraphAttributes& GA);
127  void call(GraphAttributes& GA, const EdgeArray<double>& eLength);
128 
131  void setStopTolerance(double s) {m_tolerance = s;}
132 
134  void setUseLayout(bool b) {m_useLayout = b;}
135  bool useLayout() {return m_useLayout;}
136 
140  void setZeroLength(double d) {m_zeroLength = d;}
141  double zeroLength() {return m_zeroLength;}
142 
144  void setDesLength(double d) {m_desLength = d;}
145 
146 
150  int maxLocalIterations() const {
151  return m_maxLocalIt;
152  }
153  void setGlobalIterationFactor(int i) {if (i>0) m_gItFactor = i;}
154  int maxGlobalIterations() const {
155  return m_maxGlobalIt;
156  }
159  if (i>0)
160  m_maxGlobalIt = i;
161  }
163  void setMaxLocalIterations(int i) {
164  if (i>0)
165  m_maxLocalIt = i;
166  }
168  void computeMaxIterations(bool b)
169  {
170  m_computeMaxIt = b;
171  }
172  //We could add some noise to the computation
173  // Returns the current setting of nodes.
174  //bool noise() const {
175  // return m_noise;
176  //}
177  // Sets the parameter noise to \a on.
178  //void noise(bool on) {
179  // m_noise = on;
180  //}
181 
182 
183 protected:
185  void doCall(GraphAttributes& GA, const EdgeArray<double>& eLength, bool simpleBFS);
187  bool finished(double maxdelta)
188  {
189  if (m_prevEnergy == startVal) //first step
190  {
191  m_prevEnergy = maxdelta;
192  return false;
193  }
194 
195  double diff = m_prevEnergy - maxdelta; //energy difference
196  if (diff < 0.0) diff = -diff;
197  //#ifdef OGDF_DEBUG
198  // cout << "Finished(): maxdelta: "<< maxdelta<<" diff/prev: "<<diff / m_prevEnergy<<"\n";
199  //#endif
200  //check if we want to stop
201  bool done = (maxdelta < m_tolerance);// || (diff / m_prevEnergy) < m_tolerance);
202 
203  m_prevEnergy = maxdelta; //save previous energy level
204  m_prevLEnergy = startVal; //reset energy level for local node decision
205 
206  return done;
207  }//finished
209  bool finishedNode(double deltav)
210  {
211  if (m_prevLEnergy == startVal)
212  {
213  m_prevLEnergy = deltav;
214  return deltav == 0.0;//<m_ltolerance; //locally stable
215  }
216  //#ifdef OGDF_DEBUG
217  // cout << "Local delta: "<<deltav<<"\n";
218  //#endif
219  double diff = m_prevLEnergy - deltav;
220  //check if we want to stop
221  bool done = (deltav == 0.0 || (diff / m_prevLEnergy) < m_ltolerance);
222 
223  m_prevLEnergy = deltav; //save previous energy level
224 
225  return done;
226  }//finishedNode
229  void adaptLengths(const Graph& G,
230  const GraphAttributes& GA,
231  const EdgeArray<double>& eLengths,
232  EdgeArray<double>& adaptedLengths);
234  void shufflePositions(GraphAttributes& GA);
237  dpair computeParDer(node m,
238  node u,
239  GraphAttributes& GA,
241  NodeArray< NodeArray<double> >& dist);
243  dpair computeParDers(node v,
244  GraphAttributes& GA,
246  NodeArray< NodeArray<double> >& dist);
248  void initialize(GraphAttributes& GA,
249  NodeArray<dpair>& partialDer,
250  const EdgeArray<double>& eLength,
251  NodeArray< NodeArray<double> >& oLength,
252  NodeArray< NodeArray<double> >& sstrength,
253  double & maxDist,
254  bool simpleBFS);
256  void mainStep(GraphAttributes& GA,
257  NodeArray<dpair>& partialDer,
258  NodeArray< NodeArray<double> >& oLength,
259  NodeArray< NodeArray<double> >& sstrength,
260  const double maxDist);
263  void scale(GraphAttributes& GA);
264 
265 private:
268  double m_tolerance;
269  double m_ltolerance;
273 
274  double m_K;
275  double m_prevEnergy;
277  double m_zeroLength;
278 
279  double m_desLength;
280  double m_distFactor; //introduces some distance for scaling in case BFS is used
281 
282  bool m_useLayout;
283 
286 
287  static const double startVal;
288  static const double minVal;
289  static const double desMinLength;
290 
291  static const int maxVal = INT_MAX;
292 
293  double allpairsspBFS(const Graph& G, NodeArray< NodeArray<double> >& distance);
294  double allpairssp(const Graph& G, const EdgeArray<double>& eLengths,
295  NodeArray< NodeArray<double> >& distance, const double threshold = DBL_MAX);
296 };//SpringEmbedderKK
297 
298 //Things that potentially could be added
299 // //! Returns the page ratio.
300 // double pageRatio() { return m_pageRatio; }
301 //
302 // //! Sets the page ration to \a x.
303 // void pageRatio(double x) { m_pageRatio = x; }
304 //
305 // //! Returns the current scaling method.
306 // Scaling scaling() const {
307 // return m_scaling;
308 // }
309 //
310 // //! Sets the method for scaling the inital layout to \a sc.
311 // void scaling(Scaling sc) {
312 // m_scaling = sc;
313 // }
314 //
315 // //! Returns the current scale function factor.
316 // double scaleFunctionFactor() const {
317 // return m_scaleFactor;
318 // }
319 //
320 // //! Sets the scale function factor to \a f.
321 // void scaleFunctionFactor(double f) {
322 // m_scaleFactor = f;
323 // }
324 //
325 // //! Sets the user bounding box (used if scaling method is scUserBoundingBox).
326 // void userBoundingBox(double xmin, double ymin, double xmax, double ymax) {
327 // m_bbXmin = xmin;
328 // m_bbYmin = ymin;
329 // m_bbXmax = xmax;
330 // m_bbYmax = ymax;
331 // }
332 
333 
334 } // end namespace ogdf
335 
336 
337 #endif