All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
MaxentStress.h
Go to the documentation of this file.
1 /*
2  * MaxentStress.h
3  *
4  * Created on: 22.01.2014
5  * Author: Henning Meyerhenke and Michael Wegner
6  */
7 
8 #ifndef MAXENTSTRESS_H_
9 #define MAXENTSTRESS_H_
10 
11 #include "GraphLayoutAlgorithm.h"
12 #include "../numerics/LinearSolver.h"
13 #include "../algebraic/CSRMatrix.h"
14 #include "Octree.h"
15 
16 #include "../distance/BFS.h"
17 #include "../distance/Dijkstra.h"
18 #include "../distance/AlgebraicDistance.h"
19 
20 #include "FruchtermanReingold.h"
21 #include "../io/LineFileReader.h"
22 #include "../auxiliary/StringTools.h"
23 
24 #include <sys/time.h>
25 
26 #include <memory>
27 
28 namespace NetworKit {
29 
30  typedef std::vector<Vector> CoordinateVector; // more meaningful and shorter name for coordinates stored by dimension
31 
32  struct ForwardEdge {
35  };
36 
37 
46  class MaxentStress : public GraphLayoutAlgorithm<double> {
47  public:
51  };
52 
57  };
58 
59  struct ResultStats {
60  double rhsTime = 0.0;
61  double approxEntropyTerm = 0.0;
62  double solveTime = 0.0;
63  };
64 
65  MaxentStress(const Graph& G, const count dim, const count k, double tolerance, LinearSolverType linearSolverType = LAMG, bool fastComputation=false, GraphDistance graphDistance = EDGE_WEIGHT);
66 
67  MaxentStress(const Graph& G, const count dim, const std::vector<Point<double>>& coordinates, const count k, double tolerance, LinearSolverType linearSolverType = LAMG, bool fastComputation=false, GraphDistance graphDistance = EDGE_WEIGHT);
68 
69 
71  virtual ~MaxentStress() = default;
72 
74  virtual void run();
75 
79  void scaleLayout();
80 
84  double computeScalingFactor();
85 
90  double fullStressMeasure();
91 
96  double maxentMeasure();
97 
98  double meanDistanceError();
99 
100  double ldme();
101 
106  void setQ(double q) {
107  this->q = q;
108  }
109 
114  void setAlpha(double alpha) {
115  this->alpha = alpha;
116  }
117 
122  void setAlphaReduction(double alphaReduction) {
123  this->alphaReduction = alphaReduction;
124  }
125 
130  void setFinalAlpha(double finalAlpha) {
131  this->finalAlpha = finalAlpha;
132  }
133 
134  void setConvergenceThreshold(double convThreshold) {
135  this->convThreshold = convThreshold * convThreshold;
136  }
137 
138  double getRhs() {
139  return this->resultStats.rhsTime;
140  };
141 
143  return this->resultStats.approxEntropyTerm;
144  };
145 
146  double getSolveTime() {
147  return this->resultStats.solveTime;
148  };
149 
150  protected:
151 
156  ResultStats runAlgo();
157 
158  private:
162  LinearSolver<CSRMatrix>& solver;
163 
168  ResultStats resultStats;
169 
171  double q, alpha, alphaReduction, finalAlpha, convThreshold;
172 
174  bool coordinatesProvided;
175 
179  bool fastComputation;
180 
182  count maxSolvesPerAlpha;
183 
185  std::vector<std::vector<ForwardEdge>> knownDistances;
186 
188  count knownDistancesCardinality;
189 
191  count dim;
192 
196  bool hasRun;
197 
204  bool isConverged(const CoordinateVector& newCoords, const CoordinateVector& oldCoords);
205 
209  void setupWeightedLaplacianMatrix();
210 
216  void computeCoordinateLaplacianTerm(const CoordinateVector& coordinates, CoordinateVector& rhs);
217 
223  CoordinateVector computeRepulsiveForces(const CoordinateVector& coordinates, CoordinateVector& b) const;
224 
232  void approxRepulsiveForces(const CoordinateVector& coordinates, const Octree<double>& octree, const double theta, CoordinateVector& b) const;
233 
238  void randomInitCoordinates(CoordinateVector& coordinates) const;
239 
244  void randomSphereCoordinates(CoordinateVector& coordinates) const;
245 
252  double squaredDistance(const CoordinateVector& coordinates, const index i, const index j) const;
253 
254 
261  inline double distance(const CoordinateVector& coordinates, const index i, const index j) const {
262  return sqrt(squaredDistance(coordinates, i, j));
263  }
264 
272  double squaredDistance(const CoordinateVector& coordinates1, const CoordinateVector& coordinates2, const index i, const index j) const;
273 
281  inline double distance(const CoordinateVector& coordinates1, const CoordinateVector& coordinates2, const index i, const index j) const {
282  return sqrt(squaredDistance(coordinates1, coordinates2, i, j));
283  }
284 
290  double squaredLength(const CoordinateVector& coordinates, const index i) const;
291 
297  inline double length(const CoordinateVector& coordinates, const index i) const {
298  return sqrt(squaredLength(coordinates, i));
299  }
300 
301 
302 
308  inline double weightingFactor(double edgeWeight) const {
309  return 1.0/(edgeWeight * edgeWeight);
310  }
311 
316  inline double sign(const double value) const {
317  return (value >= 0.0) - (value < 0.0);
318  }
319 
325  inline Point<double> getPoint(const CoordinateVector& coordinates, index i) const {
326  Point<double> p(coordinates.size());
327  for (index d = 0; d < p.getDimensions(); ++d) {
328  assert(coordinates[d].getDimension() > i);
329  p[d] = coordinates[d][i];
330  }
331 
332  return p;
333  }
334 
341  void computeKnownDistances(const count k, const GraphDistance graphDistance);
342 
347  void addKNeighborhoodOfVertex(const node u, const count k);
348 
354  void computeAlgebraicDistances(const Graph& graph, const count k);
355  };
356 
357 } /* namespace NetworKit */
358 #endif /* MAXENTSTRESS_H_ */
Implementation of a k-dimensional octree for the purpose of Barnes-Hut approximation.
Definition: Octree.h:265
void setConvergenceThreshold(double convThreshold)
Definition: MaxentStress.h:134
virtual ~MaxentStress()=default
Default destructor.
double getRhs()
Definition: MaxentStress.h:138
double maxentMeasure()
Computes the maxent stress measure for the computed layout with run().
Definition: MaxentStress.cpp:260
LinearSolverType
Definition: MaxentStress.h:53
const Graph & G
Definition: GraphLayoutAlgorithm.h:144
Definition: MaxentStress.h:59
uint64_t index
Typedefs.
Definition: Globals.h:20
Definition: MaxentStress.h:32
ResultStats runAlgo()
Calls run() and returns the corresponding stats.
Definition: MaxentStress.cpp:51
double getSolveTime()
Definition: MaxentStress.h:146
double getApproxEntropyTerm()
Definition: MaxentStress.h:142
virtual void run()
Computes a graph drawing according to the Maxent-Stress model.
Definition: MaxentStress.cpp:56
Definition: MaxentStress.h:54
double computeScalingFactor()
Computes a scalar s s.t.
Definition: MaxentStress.cpp:185
Definition: MaxentStress.h:49
Abstract base class for algorithms that compute a layout of the Graph vertices in d-dimensional space...
Definition: GraphLayoutAlgorithm.h:26
double fullStressMeasure()
Computes the full stress measure of the computed layout with run().
Definition: MaxentStress.cpp:233
void setFinalAlpha(double finalAlpha)
Set parameter finalAlpha.
Definition: MaxentStress.h:130
uint64_t count
Definition: Globals.h:21
Abstract base class for solvers that solve linear systems.
Definition: LinearSolver.h:29
index node
Definition: Globals.h:23
Implementation of MaxentStress by Ganser et al.
Definition: MaxentStress.h:46
double approxEntropyTerm
Definition: MaxentStress.h:61
std::vector< Vector > CoordinateVector
Definition: MaxentStress.h:30
double ldme()
Definition: MaxentStress.cpp:310
float distance
Definition: PubWebGenerator.h:25
void setAlpha(double alpha)
Set parameter alpha.
Definition: MaxentStress.h:114
edgeweight weight
Definition: MaxentStress.h:34
double solveTime
Definition: MaxentStress.h:62
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
GraphDistance
Definition: MaxentStress.h:48
void scaleLayout()
Scale the layout computed by run() by a scalar s to minimize {u,v V} w_{uv} (s ||x_u - x_v|| - d_{uv...
Definition: MaxentStress.cpp:222
MaxentStress(const Graph &G, const count dim, const count k, double tolerance, LinearSolverType linearSolverType=LAMG, bool fastComputation=false, GraphDistance graphDistance=EDGE_WEIGHT)
Definition: MaxentStress.cpp:25
double meanDistanceError()
Definition: MaxentStress.cpp:299
double rhsTime
Definition: MaxentStress.h:60
void setAlphaReduction(double alphaReduction)
Set parameter alphaReduction.
Definition: MaxentStress.h:122
node head
Definition: MaxentStress.h:33
void setQ(double q)
Set parameter q.
Definition: MaxentStress.h:106
Definition: MaxentStress.h:50
double edgeweight
Definition: Globals.h:24