# OpenGraph DrawingFramework

v. 2023.09 (Elderberry)

Searching...
No Matches
FMEKernel.h
Go to the documentation of this file.
1
32#pragma once
33
34#include <ogdf/basic/basic.h>
36
37
38
39#include <list>
40
41namespace ogdf {
42namespace fast_multipole_embedder {
43
44class FMEKernel {
45public:
47
48 inline void sync() { m_pThread->sync(); }
49
52
55
58
61
62private:
64};
65
66#define OGDF_FME_KERNEL_USE_OLD
67
68#define OGDF_FME_KERNEL_COMPUTE_FORCE_PROTECTION_FACTOR 0.25f
69// makro for force computation via SSE s / max(s*0.5, (dx*dx + dy*dy))
70#define OGDF_FME_KERNEL_MM_COMPUTE_FORCE(dx, dy, s) \
71 _mm_div_ps((s), \
72 _mm_max_ps(_mm_mul_ps((s), _mm_set1_ps(OGDF_FME_KERNEL_COMPUTE_FORCE_PROTECTION_FACTOR)), \
74#define OGDF_FME_KERNEL_COMPUTE_FORCE(dx, dy, s) \
75 (s / (max<float>(s * OGDF_FME_KERNEL_COMPUTE_FORCE_PROTECTION_FACTOR, (dx) * (dx) + (dy) * (dy))))
76
77inline double move_nodes(float* x, float* y, const uint32_t begin, const uint32_t end,
78 const float* fx, const float* fy, const float t) {
79 double dsq_max = 0.0;
80 for (uint32_t i = begin; i <= end; i++) {
81 double dsq = fx[i] * fx[i] + fy[i] * fy[i];
82 x[i] += fx[i] * t;
83 y[i] += fy[i] * t;
85 }
86 return dsq_max;
87}
88
89inline void eval_edges(const ArrayGraph& graph, const uint32_t begin, const uint32_t end, float* fx,
90 float* fy) {
91 const float* x = graph.nodeXPos();
92 const float* y = graph.nodeYPos();
93 const float* e = graph.desiredEdgeLength();
94 for (uint32_t i = begin; i <= end; i++) {
95 const auto& e_info = graph.edgeInfo(i);
96 const uint32_t a = e_info.a;
97 const uint32_t b = e_info.b;
98 const auto& a_info = graph.nodeInfo(a);
99 const auto& b_info = graph.nodeInfo(b);
100
101 float dx = x[a] - x[b];
102 float dy = y[a] - y[b];
103 float dsq = dx * dx + dy * dy;
104 float f = dsq == 0 ? 0 : (logf(dsq) * 0.5f - logf(e[i])) * 0.25f;
105 float fa = (float)(f / ((float)a_info.degree));
106 float fb = (float)(f / ((float)b_info.degree));
107 fx[a] -= dx * fa;
108 fy[a] -= dy * fa;
109 fx[b] += dx * fb;
110 fy[b] += dy * fb;
111 }
112}
113
115inline void eval_direct(float* x, float* y, float* s, float* fx, float* fy, size_t n) {
116 for (uint32_t i = 0; i < n; i++) {
117 for (uint32_t j = i + 1; j < n; j++) {
118 float dx = x[i] - x[j];
119 float dy = y[i] - y[j];
120#ifdef OGDF_FME_KERNEL_USE_OLD
121 float s_sum = s[i] + s[j];
122#else
123 float s_sum = s[i] * s[j];
124#endif
125 float f = OGDF_FME_KERNEL_COMPUTE_FORCE(dx, dy, s_sum);
126 fx[i] += dx * f;
127 fy[i] += dy * f;
128 fx[j] -= dx * f;
129 fy[j] -= dy * f;
130 }
131 }
132}
133
135inline void eval_direct(float* x1, float* y1, float* s1, float* fx1, float* fy1, size_t n1,
136 float* x2, float* y2, float* s2, float* fx2, float* fy2, size_t n2) {
137 for (uint32_t i = 0; i < n1; i++) {
138 for (uint32_t j = 0; j < n2; j++) {
139 float dx = x1[i] - x2[j];
140 float dy = y1[i] - y2[j];
141#ifdef OGDF_FME_KERNEL_USE_OLD
142 float s_sum = s1[i] + s2[j];
143#else
144 float s_sum = s1[i] * s2[j];
145#endif
146 float f = OGDF_FME_KERNEL_COMPUTE_FORCE(dx, dy, s_sum);
147 fx1[i] += dx * f;
148 fy1[i] += dy * f;
149 fx2[j] -= dx * f;
150 fy2[j] -= dy * f;
151 }
152 }
153}
154
155
156#ifndef OGDF_FME_KERNEL_USE_SSE_DIRECT
158inline void eval_direct_fast(float* x, float* y, float* s, float* fx, float* fy, size_t n) {
159 eval_direct(x, y, s, fx, fy, n);
160}
161
163inline void eval_direct_fast(float* x1, float* y1, float* s1, float* fx1, float* fy1, size_t n1,
164 float* x2, float* y2, float* s2, float* fx2, float* fy2, size_t n2) {
165 eval_direct(x1, y1, s1, fx1, fy1, n1, x2, y2, s2, fx2, fy2, n2);
166}
167
168#else
170void eval_direct_fast(float* x, float* y, float* s, float* fx, float* fy, size_t n);
172void eval_direct_fast(float* x1, float* y1, float* s1, float* fx1, float* fy1, size_t n1, float* x2,
173 float* y2, float* s2, float* fx2, float* fy2, size_t n2);
174#endif
175
178 double centerY, float x, float y, float q, float& fx, float& fy);
179
181 double centerY, float x, float y, float q);
182
184public:
185 inline void edgeForces(const ArrayGraph& graph, float* fx, float* fy) {
186 eval_edges(graph, 0, graph.numEdges() - 1, fx, fy);
187 }
188
189 inline void repForces(ArrayGraph& graph, float* fx, float* fy) {
190 eval_direct_fast(graph.nodeXPos(), graph.nodeYPos(), graph.nodeSize(), fx, fy,
191 graph.numNodes());
192 }
193
194 inline double moveNodes(ArrayGraph& graph, float* fx, float* fy, float timeStep) {
195 return move_nodes(graph.nodeXPos(), graph.nodeYPos(), 0, graph.numNodes() - 1, fx, fy,
196 timeStep);
197 }
198
199 inline double simpleIteration(ArrayGraph& graph, float* fx, float* fy, float timeStep) {
200 repForces(graph, fx, fy);
201 edgeForces(graph, fx, fy);
202 return moveNodes(graph, fx, fy, timeStep);
203 }
204
205 inline double simpleEdgeIteration(ArrayGraph& graph, float* fx, float* fy, float timeStep) {
206 edgeForces(graph, fx, fy);
207 return moveNodes(graph, fx, fy, timeStep);
208 }
209
210 inline void simpleForceDirected(ArrayGraph& graph, float timeStep, uint32_t minIt,
211 uint32_t maxIt, uint32_t preProcIt, double threshold) {
212 bool earlyExit = false;
213 float* fx = (float*)OGDF_MALLOC_16(sizeof(float) * graph.numNodes());
214 float* fy = (float*)OGDF_MALLOC_16(sizeof(float) * graph.numNodes());
215
216 for (uint32_t i = 0; i < preProcIt; i++) {
217 for (uint32_t j = 0; j < graph.numNodes(); j++) {
218 fx[j] = 0.0f;
219 fy[j] = 0.0f;
220 }
221 simpleEdgeIteration(graph, fx, fy, timeStep);
222 }
223 for (uint32_t i = 0; i < maxIt && !earlyExit; i++) {
224 for (uint32_t j = 0; j < graph.numNodes(); j++) {
225 fx[j] = 0.0f;
226 fy[j] = 0.0f;
227 }
228 double dsq = simpleIteration(graph, fx, fy, timeStep);
230 earlyExit = true;
231 }
232 }
233
234 OGDF_FREE_16(fx);
235 OGDF_FREE_16(fy);
236 }
237
238private:
239};
240
242public:
243#if 0
245#endif
246
247 void operator()(ArrayGraph& graph, float timeStep, uint32_t minIt, uint32_t maxIt,
248 double threshold) {
249 simpleForceDirected(graph, timeStep, minIt, maxIt, 20, threshold);
250 }
251};
252
253}
254}
Declaration of class ArrayGraph.
#define OGDF_FME_KERNEL_COMPUTE_FORCE(dx, dy, s)
Definition FMEKernel.h:74
Definition of utility functions for FME layout.
#define OGDF_MALLOC_16(s)
16-byte aligned memory allocation macro
Definition FastUtils.h:116
#define OGDF_FREE_16(ptr)
16-byte aligned memory deallocation macro
Definition FastUtils.h:119
Basic declarations, included by all source files.
float * nodeXPos()
Returns the x coord array for all nodes.
Definition ArrayGraph.h:162
uint32_t numEdges() const
Returns the number of edges.
Definition ArrayGraph.h:59
Returns the adjacency information for the edge at index i in m_edgeAdj.
Definition ArrayGraph.h:144
float * nodeYPos()
Returns the y coord array for all nodes.
Definition ArrayGraph.h:168
Returns the adjacency information for the node at index i in m_nodeAdj.
Definition ArrayGraph.h:138
float * nodeSize()
Returns the node size array for all nodes.
Definition ArrayGraph.h:174
uint32_t numNodes() const
Returns the number of nodes.
Definition ArrayGraph.h:56
float * desiredEdgeLength()
Returns the edge length array for all edges.
Definition ArrayGraph.h:183
uint32_t a
First node of the pair.
Definition EdgeChain.h:54
double simpleEdgeIteration(ArrayGraph &graph, float *fx, float *fy, float timeStep)
Definition FMEKernel.h:205
void edgeForces(const ArrayGraph &graph, float *fx, float *fy)
Definition FMEKernel.h:185
double moveNodes(ArrayGraph &graph, float *fx, float *fy, float timeStep)
Definition FMEKernel.h:194
double simpleIteration(ArrayGraph &graph, float *fx, float *fy, float timeStep)
Definition FMEKernel.h:199
void simpleForceDirected(ArrayGraph &graph, float timeStep, uint32_t minIt, uint32_t maxIt, uint32_t preProcIt, double threshold)
Definition FMEKernel.h:210
void repForces(ArrayGraph &graph, float *fx, float *fy)
Definition FMEKernel.h:189
returns true if this is the main thread ( the main thread is always the first thread )
Definition FMEKernel.h:57
Definition FMEKernel.h:51
returns true if this run only uses one thread )
Definition FMEKernel.h:60
returns the total number of threads in the pool
Definition FMEKernel.h:54
void operator()(ArrayGraph &graph, float timeStep, uint32_t minIt, uint32_t maxIt, double threshold)
Definition FMEKernel.h:247
The fast multipole embedder work thread class.
returns true if this is the main thread ( the main thread is always the first thread )
returns the total number of threads in the pool
void updateMax(T &max, const T &newValue)
Stores the maximum of max and newValue in max.
Definition Math.h:90
void fast_multipole_p2m(double *mulitCoeffiecients, uint32_t numCoeffiecients, double centerX, double centerY, float x, float y, float q)
void eval_direct_fast(float *x, float *y, float *s, float *fx, float *fy, size_t n)
kernel function to evaluate forces between n points with coords x, y directly. result is stored in fx...
Definition FMEKernel.h:158
double move_nodes(float *x, float *y, const uint32_t begin, const uint32_t end, const float *fx, const float *fy, const float t)
Definition FMEKernel.h:77
void fast_multipole_l2p(double *localCoeffiecients, uint32_t numCoeffiecients, double centerX, double centerY, float x, float y, float q, float &fx, float &fy)
kernel function to evalute a local expansion at point x,y result is added to fx, fy
void eval_direct(float *x, float *y, float *s, float *fx, float *fy, size_t n)
kernel function to evaluate forces between n points with coords x, y directly. result is stored in fx...
Definition FMEKernel.h:115
void eval_edges(const ArrayGraph &graph, const uint32_t begin, const uint32_t end, float *fx, float *fy)
Definition FMEKernel.h:89
The namespace for all OGDF objects.