Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

SpringEmbedderFRExact.h
Go to the documentation of this file.
1 
32 #pragma once
33 
35 #include <ogdf/basic/SList.h>
37 
38 namespace ogdf {
39 
42 {
43 public:
44  enum class CoolingFunction { Factor, Logarithmic };
45 
48 
50  virtual void call(GraphAttributes &GA) override;
51 
53  int iterations() const {
54  return m_iterations;
55  }
56 
58  void iterations(int i) {
59  OGDF_ASSERT(i > 0);
60  m_iterations = i;
61  }
62 
64  bool noise() const {
65  return m_noise;
66  }
67 
69  void noise(bool on) {
70  m_noise = on;
71  }
72 
74  void nodeWeights(bool on) {
75  m_useNodeWeight = on;
76  }
79  return m_coolingFunction;
80  }
81 
84  m_coolingFunction = f;
85  }
86 
88  double idealEdgeLength() const { return m_idealEdgeLength; }
89 
91  void idealEdgeLength(double len) { m_idealEdgeLength = len; }
92 
94  double minDistCC() const { return m_minDistCC; }
95 
97  void minDistCC(double x) { m_minDistCC = x; }
98 
100  double pageRatio() { return m_pageRatio; }
101 
103  void pageRatio(double x) { m_pageRatio = x; }
104 
105  void checkConvergence(bool b) {m_checkConvergence = b;}
106  bool checkConvergence() {return m_checkConvergence;}
107  void convTolerance(double tol) {m_convTolerance = tol;}
108 
109 private:
111  {
114  int m_numCC;
115 
120 
121  public:
122  explicit ArrayGraph(GraphAttributes &ga);
123  ~ArrayGraph();
124 
125  void initCC(int i);
126 
127  int numberOfCCs() const { return m_numCC; }
128  int numberOfNodes() const { return m_numNodes; }
129  int numberOfEdges() const { return m_numEdges; }
130 
131  node original(int v) const { return m_orig[v]; }
132  const SList<node> &nodesInCC(int i) const { return m_nodesInCC[i]; }
133 
134  int *m_src;
135  int *m_tgt;
136  double *m_x;
137  double *m_y;
138  double *m_nodeWeight;
139  //this should be part of a multilevel layout interface class later on
140  bool m_useNodeWeight; //should given nodeweights be used or all set to 1.0?
141  };
142 
143  double log2(double x) { return log(x) / log(2.0); }
144  double mylog2(int x) {
145  double result = 0.0;
146  while(x > 0) {
147  result++;
148  x >>= 1;
149  }
150  return result/2;
151  }
152 
153  void initialize(ArrayGraph &component);
154  void mainStep(ArrayGraph &component);
155  void mainStep_sse3(ArrayGraph &component);
156 
157 #if 0
158  // Fruchterman, Reingold
159  double f_att(double d) { return d*d / m_idealEdgeLength; }
160  double f_rep(double d) { return m_idealEdgeLength*m_idealEdgeLength / d; }
161 
162  // Eades
163  double f_att(double d) { return 5.0 * d * log2(d/m_idealEdgeLength); }
164  double f_rep(double d) { return 20.0 / d; }
165 #endif
166 
167  // cooling function
168  void cool(double &tx, double &ty, int &cF);
169 
171  bool m_noise;
173 
174 #if 0
175  double m_tx;
176  double m_ty;
177 #endif
178 
181 
183  double m_minDistCC;
184  double m_pageRatio;
185 
186 #if 0
187  int m_cF;
188 #endif
189  double m_txNull;
190  double m_tyNull;
191  //see above at ArrayGraph
193  bool m_checkConvergence; //<! If set to true, computation is stopped if movement falls below threshold
194  double m_convTolerance; //<! Fraction of ideal edge length below which convergence is achieved
195 };
196 
197 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::GraphAttributes
Stores additional attributes of a graph (like layout information).
Definition: GraphAttributes.h:67
GraphAttributes.h
Declaration of class GraphAttributes which extends a Graph by additional attributes.
ogdf::SpringEmbedderFRExact::ArrayGraph::m_useNodeWeight
bool m_useNodeWeight
Definition: SpringEmbedderFRExact.h:140
ogdf::SpringEmbedderFRExact::m_minDistCC
double m_minDistCC
The minimal distance between connected components.
Definition: SpringEmbedderFRExact.h:183
ogdf::SpringEmbedderFRExact::log2
double log2(double x)
Definition: SpringEmbedderFRExact.h:143
ogdf::SpringEmbedderFRExact::m_idealEdgeLength
double m_idealEdgeLength
The ideal edge length.
Definition: SpringEmbedderFRExact.h:182
ogdf::SpringEmbedderFRExact::ArrayGraph
Definition: SpringEmbedderFRExact.h:110
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::SpringEmbedderFRExact::ArrayGraph::m_nodesInCC
Array< SList< node > > m_nodesInCC
Definition: SpringEmbedderFRExact.h:118
ogdf::SpringEmbedderFRExact::m_coolFactor_y
double m_coolFactor_y
Definition: SpringEmbedderFRExact.h:180
ogdf::SpringEmbedderFRExact::ArrayGraph::numberOfCCs
int numberOfCCs() const
Definition: SpringEmbedderFRExact.h:127
ogdf::SpringEmbedderFRExact
Fruchterman-Reingold algorithm with (exact) layout.
Definition: SpringEmbedderFRExact.h:41
ogdf::SpringEmbedderFRExact::ArrayGraph::m_nodeWeight
double * m_nodeWeight
Definition: SpringEmbedderFRExact.h:138
ogdf::SpringEmbedderFRExact::CoolingFunction
CoolingFunction
Definition: SpringEmbedderFRExact.h:44
ogdf::SpringEmbedderFRExact::ArrayGraph::m_tgt
int * m_tgt
Definition: SpringEmbedderFRExact.h:135
ogdf::SList
Singly linked lists (maintaining the length of the list).
Definition: SList.h:773
ogdf::ForceLayoutModule
Interface of general layout algorithms.
Definition: ForceLayoutModule.h:45
ogdf::SpringEmbedderFRExact::ArrayGraph::m_y
double * m_y
Definition: SpringEmbedderFRExact.h:137
ogdf::SpringEmbedderFRExact::ArrayGraph::m_ga
GraphAttributes * m_ga
Definition: SpringEmbedderFRExact.h:116
ogdf::SpringEmbedderFRExact::m_coolFactor_x
double m_coolFactor_x
Definition: SpringEmbedderFRExact.h:179
ogdf::SpringEmbedderFRExact::ArrayGraph::nodesInCC
const SList< node > & nodesInCC(int i) const
Definition: SpringEmbedderFRExact.h:132
ogdf::NodeArray< int >
ForceLayoutModule.h
Declaration of interface for energy-based layout algorithms (class ForceLayoutModule)
ogdf::SpringEmbedderFRExact::idealEdgeLength
void idealEdgeLength(double len)
Sets the ideal edge length to len.
Definition: SpringEmbedderFRExact.h:91
ogdf::SpringEmbedderFRExact::m_useNodeWeight
bool m_useNodeWeight
Definition: SpringEmbedderFRExact.h:192
ogdf::SpringEmbedderFRExact::iterations
void iterations(int i)
Sets the number of iterations to i.
Definition: SpringEmbedderFRExact.h:58
ogdf::SpringEmbedderFRExact::checkConvergence
bool checkConvergence()
Definition: SpringEmbedderFRExact.h:106
ogdf::SpringEmbedderFRExact::ArrayGraph::m_numNodes
int m_numNodes
Definition: SpringEmbedderFRExact.h:112
ogdf::SpringEmbedderFRExact::ArrayGraph::m_mapNode
NodeArray< int > m_mapNode
Definition: SpringEmbedderFRExact.h:119
ogdf::SpringEmbedderFRExact::idealEdgeLength
double idealEdgeLength() const
Returns the ideal edge length.
Definition: SpringEmbedderFRExact.h:88
ogdf::SpringEmbedderFRExact::ArrayGraph::m_x
double * m_x
Definition: SpringEmbedderFRExact.h:136
ogdf::SpringEmbedderFRExact::m_noise
bool m_noise
Perform random perturbations?
Definition: SpringEmbedderFRExact.h:171
ogdf::SpringEmbedderFRExact::m_tyNull
double m_tyNull
Definition: SpringEmbedderFRExact.h:190
SList.h
Declaration of singly linked lists and iterators.
ogdf::Array
The parameterized class Array implements dynamic arrays of type E.
Definition: Array.h:204
ogdf::SpringEmbedderFRExact::convTolerance
void convTolerance(double tol)
Definition: SpringEmbedderFRExact.h:107
ogdf::SpringEmbedderFRExact::m_iterations
int m_iterations
The number of iterations.
Definition: SpringEmbedderFRExact.h:170
ogdf::SpringEmbedderFRExact::coolingFunction
void coolingFunction(CoolingFunction f)
Sets the parameter coolingFunction to f.
Definition: SpringEmbedderFRExact.h:83
ogdf::SpringEmbedderFRExact::ArrayGraph::m_numCC
int m_numCC
Definition: SpringEmbedderFRExact.h:114
ogdf::SpringEmbedderFRExact::ArrayGraph::numberOfEdges
int numberOfEdges() const
Definition: SpringEmbedderFRExact.h:129
ogdf::SpringEmbedderFRExact::nodeWeights
void nodeWeights(bool on)
Switches use of node weights given in GraphAttributtes.
Definition: SpringEmbedderFRExact.h:74
ogdf::SpringEmbedderFRExact::mylog2
double mylog2(int x)
Definition: SpringEmbedderFRExact.h:144
ogdf::SpringEmbedderFRExact::checkConvergence
void checkConvergence(bool b)
Definition: SpringEmbedderFRExact.h:105
ogdf::SpringEmbedderFRExact::ArrayGraph::m_orig
node * m_orig
Definition: SpringEmbedderFRExact.h:117
ogdf::SpringEmbedderFRExact::pageRatio
double pageRatio()
Returns the page ratio.
Definition: SpringEmbedderFRExact.h:100
ogdf::SpringEmbedderFRExact::iterations
int iterations() const
Returns the current setting of iterations.
Definition: SpringEmbedderFRExact.h:53
ogdf::SpringEmbedderFRExact::minDistCC
void minDistCC(double x)
Sets the minimum distance between connected components to x.
Definition: SpringEmbedderFRExact.h:97
ogdf::SpringEmbedderFRExact::m_coolingFunction
CoolingFunction m_coolingFunction
The selected cooling function.
Definition: SpringEmbedderFRExact.h:172
ogdf::SpringEmbedderFRExact::ArrayGraph::original
node original(int v) const
Definition: SpringEmbedderFRExact.h:131
ogdf::SpringEmbedderFRExact::m_pageRatio
double m_pageRatio
The page ratio.
Definition: SpringEmbedderFRExact.h:184
OGDF_EXPORT
#define OGDF_EXPORT
Specifies that a function or class is exported by the OGDF DLL.
Definition: config.h:99
ogdf::SpringEmbedderFRExact::coolingFunction
CoolingFunction coolingFunction() const
Returns the current setting for the cooling function.
Definition: SpringEmbedderFRExact.h:78
ogdf::Math::log2
T log2(T x)
Returns the logarithm of x to the base 2.
Definition: Math.h:110
ogdf::SpringEmbedderFRExact::ArrayGraph::m_numEdges
int m_numEdges
Definition: SpringEmbedderFRExact.h:113
ogdf::SpringEmbedderFRExact::noise
void noise(bool on)
Sets the parameter noise to on.
Definition: SpringEmbedderFRExact.h:69
ogdf::SpringEmbedderFRExact::ArrayGraph::numberOfNodes
int numberOfNodes() const
Definition: SpringEmbedderFRExact.h:128
ogdf::SpringEmbedderFRExact::m_convTolerance
double m_convTolerance
Definition: SpringEmbedderFRExact.h:194
ogdf::SpringEmbedderFRExact::ArrayGraph::m_src
int * m_src
Definition: SpringEmbedderFRExact.h:134
ogdf::SpringEmbedderFRExact::minDistCC
double minDistCC() const
Returns the minimum distance between connected components.
Definition: SpringEmbedderFRExact.h:94
ogdf::SpringEmbedderFRExact::noise
bool noise() const
Returns the current setting of nodes.
Definition: SpringEmbedderFRExact.h:64
ogdf::SpringEmbedderFRExact::m_checkConvergence
bool m_checkConvergence
Definition: SpringEmbedderFRExact.h:193
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::SpringEmbedderFRExact::m_txNull
double m_txNull
Definition: SpringEmbedderFRExact.h:189
ogdf::SpringEmbedderFRExact::pageRatio
void pageRatio(double x)
Sets the page ration to x.
Definition: SpringEmbedderFRExact.h:103