Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

FMEFunc.h
Go to the documentation of this file.
1 
32 #pragma once
33 
40 #include <list>
41 
42 namespace ogdf {
43 namespace fast_multipole_embedder {
44 
45 
48 {
49  std::list<LinearQuadtree::NodeID> nodes;
50  uint32_t pointCount;
51 
52  template<typename Func>
53  void for_loop(Func& func)
54  {
55  for (LinearQuadtree::NodeID id : nodes)
56  func(id);
57  }
58 };
59 
61 {
62  uint32_t begin;
63  uint32_t numNodes;
64 };
65 
66 
69 {
73 
74  float timeStep;
78  float normNodeSize;
79  uint32_t maxNumIterations;
80  uint32_t minNumIterations;
81 
84 
85  double stopCritForce;
87  double stopCritConstSq;
88 
90 };
91 
92 
94 struct FMELocalContext;
95 
98 {
100  uint32_t numThreads;
105  float* globalForceX;
106  float* globalForceY;
108  bool earlyExit;
109  float scaleFactor;
110  float coolDown;
111  float min_x;
112  float max_x;
113  float min_y;
114  float max_y;
116 };
117 
120 {
122  float* forceX;
123  float* forceY;
124  double maxForceSq;
125  double avgForce;
126  float min_x;
127  float max_x;
128  float min_y;
129  float max_y;
134 
137  uint32_t numInnerNodes;
138 
141  uint32_t numLeaves;
142 };
143 
146 {
147  return min_max_functor<float>(pLocalContext->pGlobalContext->pGraph->nodeXPos(), pLocalContext->min_x, pLocalContext->max_x);
148 }
149 
152 {
153  return min_max_functor<float>(pLocalContext->pGlobalContext->pGraph->nodeYPos(), pLocalContext->min_y, pLocalContext->max_y);
154 }
155 
157 {
158 public:
159  inline LQMortonFunctor ( FMELocalContext* pLocalContext )
160  {
161  x = pLocalContext->pGlobalContext->pGraph->nodeXPos();
162  y = pLocalContext->pGlobalContext->pGraph->nodeYPos();
163  s = pLocalContext->pGlobalContext->pGraph->nodeSize();
164  quadtree = pLocalContext->pGlobalContext->pQuadtree;
165  translate_x = -quadtree->minX();
166  translate_y = -quadtree->minY();
167  scale = quadtree->scaleInv();
168  }
169 
170  inline uint32_t operator()(void) const
171  {
172  return quadtree->numberOfPoints();
173  }
174 
175  inline void operator()(uint32_t i)
176  {
178  uint32_t ref = p.ref;
179  p.mortonNr = mortonNumber<uint64_t, uint32_t>((uint32_t)((x[ref] + translate_x)*scale), (uint32_t)((y[ref] + translate_y)*scale));
180  }
181 
182  inline void operator()(uint32_t begin, uint32_t end)
183  {
184  for (uint32_t i = begin; i <= end; i++)
185  {
186  this->operator()(i);
187  }
188  }
189 
190 private:
192  float translate_x;
193  float translate_y;
194  double scale;
195  float* x;
196  float* y;
197  float* s;
198 };
199 
200 
203 {
206 
208 
209  inline void operator()(LinearQuadtree::NodeID nodeIndex)
210  {
211  uint32_t numPointsInLeaf = tree.numberOfPoints(nodeIndex);
212  uint32_t firstPointOfLeaf = tree.firstPoint(nodeIndex);
213  for (uint32_t pointIndex=firstPointOfLeaf; pointIndex < (firstPointOfLeaf+numPointsInLeaf); pointIndex++)
214  {
215  expansions.P2M(pointIndex, nodeIndex);
216  }
217  }
218 };
219 
220 
222 static inline p2m_functor p2m_function(FMELocalContext* pLocalContext)
223 {
224  return p2m_functor(*pLocalContext->pGlobalContext->pQuadtree, *pLocalContext->pGlobalContext->pExpansion);
225 }
226 
227 
230 {
233 
235 
237  {
238  expansions.M2M(child, parent);
239  }
240 
241  inline void operator()(LinearQuadtree::NodeID nodeIndex)
242  {
243  tree.forall_children(pair_call(*this, nodeIndex))(nodeIndex);
244  }
245 };
246 
247 
249 static inline m2m_functor m2m_function(FMELocalContext* pLocalContext)
250 {
251  return m2m_functor(*pLocalContext->pGlobalContext->pQuadtree, *pLocalContext->pGlobalContext->pExpansion);
252 }
253 
254 
257 {
259 
261 
262  inline void operator()(LinearQuadtree::NodeID nodeIndexSource, LinearQuadtree::NodeID nodeIndexReceiver)
263  {
264  expansions.M2L(nodeIndexSource, nodeIndexReceiver);
265  }
266 };
267 
268 
270 static inline m2l_functor m2l_function(FMELocalContext* pLocalContext)
271 {
272  return m2l_functor(*pLocalContext->pGlobalContext->pExpansion);
273 }
274 
275 
278 {
281 
283 
285  {
286  expansions.L2L(parent, child);
287  }
288 
289  inline void operator()(LinearQuadtree::NodeID nodeIndex)
290  {
291  tree.forall_children(pair_call(*this, nodeIndex))(nodeIndex);
292  }
293 };
294 
295 
297 static inline l2l_functor l2l_function(FMELocalContext* pLocalContext)
298 {
299  return l2l_functor(*pLocalContext->pGlobalContext->pQuadtree, *pLocalContext->pGlobalContext->pExpansion);
300 }
301 
302 
305 {
308  float* fx;
309  float* fy;
310 
311  l2p_functor(const LinearQuadtree& t, LinearQuadtreeExpansion& e, float* x, float* y) : tree(t), expansions(e), fx(x), fy(y) { }
312 
313  inline void operator()(LinearQuadtree::NodeID nodeIndex, LinearQuadtree::PointID pointIndex)
314  {
315  expansions.L2P(nodeIndex, pointIndex, fx[pointIndex], fy[pointIndex]);
316  }
317 
318  inline void operator()(LinearQuadtree::PointID pointIndex)
319  {
320  LinearQuadtree::NodeID nodeIndex = tree.pointLeaf(pointIndex);
321  this->operator ()(nodeIndex, pointIndex);
322  }
323 };
324 
325 
327 static inline l2p_functor l2p_function(FMELocalContext* pLocalContext)
328 {
329  return l2p_functor(*pLocalContext->pGlobalContext->pQuadtree, *pLocalContext->pGlobalContext->pExpansion, pLocalContext->forceX, pLocalContext->forceY);
330 }
331 
332 
335 {
337  float* fx;
338  float* fy;
339 
340  p2p_functor(const LinearQuadtree& t, float* x, float* y) : tree(t), fx(x), fy(y) { }
341 
342  inline void operator()(LinearQuadtree::NodeID nodeIndexA, LinearQuadtree::NodeID nodeIndexB)
343  {
344  uint32_t offsetA = tree.firstPoint(nodeIndexA);
345  uint32_t offsetB = tree.firstPoint(nodeIndexB);
346  uint32_t numPointsA = tree.numberOfPoints(nodeIndexA);
347  uint32_t numPointsB = tree.numberOfPoints(nodeIndexB);
348  eval_direct_fast(tree.pointX() + offsetA, tree.pointY() + offsetA,
349  tree.pointSize() + offsetA,
350  fx + offsetA, fy + offsetA, numPointsA,
351  tree.pointX() + offsetB, tree.pointY() + offsetB,
352  tree.pointSize() + offsetB,
353  fx + offsetB, fy + offsetB, numPointsB);
354  }
355 
356  inline void operator()(LinearQuadtree::NodeID nodeIndex)
357  {
358  uint32_t offset = tree.firstPoint(nodeIndex);
359  uint32_t numPoints = tree.numberOfPoints(nodeIndex);
360  eval_direct_fast(tree.pointX() + offset, tree.pointY() + offset, tree.pointSize() + offset, fx + offset, fy + offset, numPoints);
361  }
362 };
363 
364 
366 static inline p2p_functor p2p_function(FMELocalContext* pLocalContext)
367 {
368  return p2p_functor(*pLocalContext->pGlobalContext->pQuadtree, pLocalContext->forceX, pLocalContext->forceY);
369 }
370 
371 
374 {
375 public:
376  explicit LQPartitioner( FMELocalContext* pLocalContext )
377  : numPointsPerThread(0)
378  , numThreads(pLocalContext->pGlobalContext->numThreads)
379  , currThread(0)
380  , tree(pLocalContext->pGlobalContext->pQuadtree)
381  , localContexts(pLocalContext->pGlobalContext->pLocalContext)
382  { }
383 
385  {
386  uint32_t numInnerNodesPerThread = tree->numberOfInnerNodes() / numThreads;
387  if (numInnerNodesPerThread < 25)
388  {
391  for (uint32_t i=1; i< numThreads; i++)
392  {
394  }
395  } else
396  {
397 
399  currThread = 0;
402  for (uint32_t i=0; i< tree->numberOfInnerNodes(); i++)
403  {
405  curr = tree->nextNode(curr);
406  if (currThread < numThreads - 1 && localContexts[currThread]->innerNodePartition.numNodes >= numInnerNodesPerThread)
407  {
408  currThread++;
411  }
412  }
413 
414  }
415 
416  uint32_t numLeavesPerThread = tree->numberOfLeaves() / numThreads;
417  if (numLeavesPerThread < 25)
418  {
421  for (uint32_t i=1; i< numThreads; i++)
422  {
424  }
425  } else
426  {
428  currThread = 0;
429  localContexts[0]->leafPartition.begin = curr;
431  for (uint32_t i=0; i< tree->numberOfLeaves(); i++)
432  {
434  curr = tree->nextNode(curr);
435  if (currThread < numThreads - 1 && localContexts[currThread]->leafPartition.numNodes >= numLeavesPerThread)
436  {
437  currThread++;
440  }
441  }
442  }
443  }
444 
445  void partition()
446  {
448  currThread = 0;
450  for (uint32_t i=0; i < numThreads; i++)
451  {
452  localContexts[i]->treePartition.nodes.clear();
454  }
455  if (numThreads>1)
456  newPartition();
457  }
458 
459  void newPartition(uint32_t nodeID)
460  {
461  uint32_t bound = tree->numberOfPoints() / (numThreads*numThreads);
462 
463  if (tree->isLeaf(nodeID) || tree->numberOfPoints(nodeID) < bound)
464  l_par.push_back(nodeID);
465  else
466  for (uint32_t i = 0; i < tree->numberOfChilds(nodeID); i++)
467  newPartition(tree->child(nodeID, i));
468  }
469 
471  {
472  l_par.clear();
473  newPartition(tree->root());
474  uint32_t bound = (tree->numberOfPoints() / (numThreads)) + (tree->numberOfPoints() / (numThreads*numThreads*2));
475  while (!l_par.empty())
476  {
478  uint32_t v = l_par.front();
479  if (((partition->pointCount + tree->numberOfPoints(v)) <= bound) ||
480  (currThread==numThreads-1))
481  {
482  partition->pointCount += tree->numberOfPoints(v);
483  partition->nodes.push_back(v);
484  tree->nodeFence(v);
485  l_par.pop_front();
486  } else
487  {
488  currThread++;
489  }
490  }
491  }
492 
494  {
496  }
497 
498 private:
500  uint32_t numThreads;
501  uint32_t currThread;
502  std::list<uint32_t> l_par;
505 };
506 
507 
509 {
510 public:
511  inline explicit LQPointUpdateFunctor ( FMELocalContext* pLocalContext )
512  {
513  x = pLocalContext->pGlobalContext->pGraph->nodeXPos();
514  y = pLocalContext->pGlobalContext->pGraph->nodeYPos();
515  s = pLocalContext->pGlobalContext->pGraph->nodeSize();
516  quadtree = pLocalContext->pGlobalContext->pQuadtree;
517  }
518 
519  inline uint32_t operator()(void) const
520  {
521  return quadtree->numberOfPoints();
522  }
523 
524  inline void operator()(uint32_t i)
525  {
527  uint32_t ref = p.ref;
528  quadtree->setPoint(i, x[ref], y[ref], s[ref]);
529  }
530 
531  inline void operator()(uint32_t begin, uint32_t end)
532  {
533  for (uint32_t i = begin; i <= end; i++)
534  {
535  this->operator()(i);
536  }
537  }
538 
539 private:
541  float* x;
542  float* y;
543  float* s;
544 };
545 
546 
551 {
552 public:
553  inline explicit LQCoordsFunctor( FMELocalContext* pLocalContext )
554  {
555  quadtree = pLocalContext->pGlobalContext->pQuadtree;
556  quadtreeExp = pLocalContext->pGlobalContext->pExpansion;
557  }
558 
559  inline uint32_t operator()(void) const
560  {
561  return quadtree->numberOfNodes();
562  }
563 
564  inline void operator()( uint32_t i )
565  {
567  }
568 
569  inline void operator()(uint32_t begin, uint32_t end)
570  {
571  for (uint32_t i = begin; i <= end; i++)
572  {
573  this->operator()(i);
574  }
575  }
576 
577 private:
580 };
581 
582 
588 {
589 public:
590  inline explicit M2LFunctor( FMELocalContext* pLocalContext )
591  {
592  quadtree = pLocalContext->pGlobalContext->pQuadtree;
593  quadtreeExp = pLocalContext->pGlobalContext->pExpansion;
594  wspd = pLocalContext->pGlobalContext->pWSPD;
595  }
596 
597  inline uint32_t operator()(void) const
598  {
599  return quadtree->numberOfNodes();
600  }
601 
602  inline void operator()(uint32_t i)
603  {
604  uint32_t currEntryIndex = wspd->firstPairEntry(i);
605  for (uint32_t k = 0; k < wspd->numWSNodes(i); k++)
606  {
607  uint32_t j = wspd->wsNodeOfPair(currEntryIndex, i);
608  quadtreeExp->M2L(j, i);
609  currEntryIndex = wspd->nextPair(currEntryIndex, i);
610  }
611  }
612 
613  inline void operator()(uint32_t begin, uint32_t end)
614  {
615  for (uint32_t i = begin; i <= end; i++)
616  {
617  this->operator()(i);
618  }
619  }
620 
621 private:
625 };
626 
627 
632 {
633 public:
634  inline explicit NDFunctor( FMELocalContext* pLocalContext )
635  {
636  quadtree = pLocalContext->pGlobalContext->pQuadtree;
637  quadtreeExp = pLocalContext->pGlobalContext->pExpansion;
638  forceArrayX = pLocalContext->forceX;
639  forceArrayY = pLocalContext->forceY;
640  }
641 
642  inline uint32_t operator()(void) const
643  {
644  return quadtree->numberOfDirectNodes();
645  }
646 
647  inline void operator()(uint32_t i)
648  {
649  uint32_t nodeI = quadtree->directNode(i);
650  uint32_t offset = quadtree->firstPoint(nodeI);
651  uint32_t numPoints = quadtree->numberOfPoints(nodeI);
652  eval_direct_fast(quadtree->pointX() + offset, quadtree->pointY() + offset, quadtree->pointSize() + offset, forceArrayX + offset, forceArrayY + offset, numPoints);
653  }
654 
655  inline void operator()(uint32_t begin, uint32_t end)
656  {
657  for (uint32_t i = begin; i <= end; i++)
658  {
659  this->operator()(i);
660  }
661  }
662 
663 private:
666  float* forceArrayX;
667  float* forceArrayY;
668 };
669 
670 
675 {
676 public:
677  inline explicit D2DFunctor( FMELocalContext* pLocalContext )
678  {
679  quadtree = pLocalContext->pGlobalContext->pQuadtree;
680  quadtreeExp = pLocalContext->pGlobalContext->pExpansion;
681  forceArrayX = pLocalContext->forceX;
682  forceArrayY = pLocalContext->forceY;
683  }
684 
685  inline uint32_t operator()(void) const
686  {
687  return quadtree->numberOfDirectPairs();
688  }
689 
690  inline void operator()(uint32_t i)
691  {
692  uint32_t nodeA = quadtree->directNodeA(i);
693  uint32_t nodeB = quadtree->directNodeB(i);
694  uint32_t offsetA = quadtree->firstPoint(nodeA);
695  uint32_t offsetB = quadtree->firstPoint(nodeB);
696  uint32_t numPointsA = quadtree->numberOfPoints(nodeA);
697  uint32_t numPointsB = quadtree->numberOfPoints(nodeB);
698  eval_direct_fast(quadtree->pointX() + offsetA, quadtree->pointY() + offsetA,
699  quadtree->pointSize() + offsetA,
700  forceArrayX + offsetA, forceArrayY + offsetA, numPointsA,
701  quadtree->pointX() + offsetB, quadtree->pointY() + offsetB,
702  quadtree->pointSize() + offsetB,
703  forceArrayX + offsetB, forceArrayY + offsetB, numPointsB);
704  }
705 
706  inline void operator()(uint32_t begin, uint32_t end)
707  {
708  for (uint32_t i = begin; i <= end; i++)
709  {
710  this->operator()(i);
711  }
712  }
713 
714 private:
717  float* forceArrayX;
718  float* forceArrayY;
719 };
720 
721 enum class FMEEdgeForce {
722  SubRep = 0x2,
723  DivDegree = 0x8
724 };
725 
726 inline int operator & (int lhs, FMEEdgeForce rhs) {
727  return lhs & static_cast<int>(rhs);
728 }
729 
730 template<unsigned int FLAGS>
732 {
733 public:
734  inline explicit EdgeForceFunctor( FMELocalContext* pLocalContext )
735  {
736  pGraph = pLocalContext->pGlobalContext->pGraph;
737  x = pGraph->nodeXPos();
738  y = pGraph->nodeYPos();
739  edgeInfo = pGraph->edgeInfo();
740  nodeInfo = pGraph->nodeInfo();
742  nodeSize = pGraph->nodeSize();
743  forceArrayX = pLocalContext->forceX;
744  forceArrayY = pLocalContext->forceY;
745  }
746 
747  inline uint32_t operator()(void) const
748  {
749  return pGraph->numEdges();
750  }
751 
752  inline void operator()(uint32_t i)
753  {
754  const EdgeAdjInfo& e_info = edgeInfo[i];
755  const NodeAdjInfo& a_info = nodeInfo[e_info.a];
756  const NodeAdjInfo& b_info = nodeInfo[e_info.b];
757 
758  float d_x = x[e_info.a] - x[e_info.b];
759  float d_y = y[e_info.a] - y[e_info.b];
760  float d_sq = d_x*d_x + d_y*d_y;
761 
762  float f = (float)(logf(d_sq)*0.5f-logf(desiredEdgeLength[i]));
763 
764  float fa = f*0.25f;
765  float fb = f*0.25f;
766 
767  if (FLAGS & FMEEdgeForce::DivDegree)
768  {
769  fa = (float)(fa/((float)a_info.degree));
770  fb = (float)(fb/((float)b_info.degree));
771  }
772 
773  if (FLAGS & FMEEdgeForce::SubRep)
774  {
775  fa += (nodeSize[e_info.b] / d_sq);
776  fb += (nodeSize[e_info.a] / d_sq);
777  }
778  forceArrayX[e_info.a] -= fa*d_x;
779  forceArrayY[e_info.a] -= fa*d_y;
780  forceArrayX[e_info.b] += fb*d_x;
781  forceArrayY[e_info.b] += fb*d_y;
782  }
783 
784  inline void operator()(uint32_t begin, uint32_t end)
785  {
786  for (uint32_t i = begin; i <= end; i++)
787  {
788  this->operator()(i);
789  }
790  }
791 
792 private:
793  float* x;
794  float* y;
797 
800  float* nodeSize;
801  float* forceArrayX;
802  float* forceArrayY;
803 };
804 
805 
806 template<unsigned int FLAGS>
808 {
809  return EdgeForceFunctor<FLAGS>( pLocalContext );
810 }
811 
812 
813 enum class FMECollect
814 {
815  NoFactor = 0x00,
816  EdgeFactor = 0x01,
817  RepulsiveFactor = 0x02,
818  EdgeFactorRep = 0x04,
819  Tree2GraphOrder = 0x08,
820  ZeroThreadArray = 0x10
821 };
822 
823 inline int operator & (int lhs, FMECollect rhs) {
824  return lhs & static_cast<int>(rhs);
825 }
826 
827 inline constexpr int operator | (int lhs, FMECollect rhs) {
828  return lhs | static_cast<int>(rhs);
829 }
830 
831 inline constexpr int operator | (FMECollect lhs, FMECollect rhs) {
832  return static_cast<int>(lhs) | static_cast<int>(rhs);
833 }
834 
835 template<unsigned int FLAGS>
837 {
838 public:
839 
840  inline explicit CollectForceFunctor( FMELocalContext* pLocalContext )
841  {
842  numContexts = pLocalContext->pGlobalContext->numThreads;
843  globalContext = pLocalContext->pGlobalContext;
844  localContexts = pLocalContext->pGlobalContext->pLocalContext;
847  pGraph = pLocalContext->pGlobalContext->pGraph;
848  if (FLAGS & FMECollect::EdgeFactor)
849  factor = pLocalContext->pGlobalContext->pOptions->edgeForceFactor;
850  else
851  if (FLAGS & FMECollect::RepulsiveFactor)
852  factor = pLocalContext->pGlobalContext->pOptions->repForceFactor;
853  else
854  if (FLAGS & FMECollect::EdgeFactorRep)
856  else
857  factor = 1.0;
858  }
859 
860  inline uint32_t operator()(void) const
861  {
862  return pGraph->numNodes();
863  }
864 
865 
866  inline void operator()(uint32_t i)
867  {
868  float sumX = 0.0f;
869  float sumY = 0.0f;
870  for (uint32_t j=0; j < numContexts; j++)
871  {
872  float* localArrayX = localContexts[j]->forceX;
873  float* localArrayY = localContexts[j]->forceY;
874  sumX += localArrayX[i];
875  sumY += localArrayY[i];
876  if (FLAGS & FMECollect::ZeroThreadArray)
877  {
878  localArrayX[i] = 0.0f;
879  localArrayY[i] = 0.0f;
880  }
881  }
882 
883  if (FLAGS & FMECollect::Tree2GraphOrder) {
885  }
886  if (FLAGS & FMECollect::RepulsiveFactor
887  && pGraph->nodeInfo(i).degree > 100) {
888  // prevent some evil effects
889  sumX /= (float)pGraph->nodeInfo(i).degree;
890  sumY /= (float)pGraph->nodeInfo(i).degree;
891  }
892  globalArrayX[i] += sumX*factor;
893  globalArrayY[i] += sumY*factor;
894  }
895 
896  inline void operator()(uint32_t begin, uint32_t end)
897  {
898  for (uint32_t i = begin; i <= end; i++)
899  {
900  this->operator()(i);
901  }
902  }
903 
904 private:
908  float* globalArrayX;
909  float* globalArrayY;
910  uint32_t numContexts;
911  float factor;
912 };
913 
914 
915 template<unsigned int FLAGS>
917 {
918  return CollectForceFunctor<FLAGS>( pLocalContext );
919 }
920 
921 
922 static constexpr int TIME_STEP_NORMAL = 0x1;
923 static constexpr int TIME_STEP_PREP = 0x2;
924 static constexpr int ZERO_GLOBAL_ARRAY = 0x4;
925 static constexpr int USE_NODE_MOVE_RAD = 0x8;
926 
927 template<unsigned int FLAGS>
929 {
930 public:
931 #if 1
932  inline explicit NodeMoveFunctor(FMELocalContext* pLocalContext)
933 #else
934  inline NodeMoveFunctor(FMELocalContext* pLocalContext,
935  float* xCoords, float* yCoords,
936  float ftimeStep,
937  float* globalForceArray)
938  : x(xCoords), y(yCoords), timeStep(ftimeStep), forceArray(globalForceArray)
939 #endif
940  {
941  if (FLAGS & TIME_STEP_NORMAL)
942  timeStep = pLocalContext->pGlobalContext->pOptions->timeStep * pLocalContext->pGlobalContext->coolDown;
943  else
944  if (FLAGS & TIME_STEP_PREP)
945  timeStep = pLocalContext->pGlobalContext->pOptions->preProcTimeStep;
946  else
947  timeStep = 1.0;
948  pGraph = pLocalContext->pGlobalContext->pGraph;
949  x = pGraph->nodeXPos();
950  y = pGraph->nodeYPos();
952  forceArrayX = pLocalContext->pGlobalContext->globalForceX;
953  forceArrayY = pLocalContext->pGlobalContext->globalForceY;
954  localContext = pLocalContext;
956  }
957 
958 #if 0
959  inline void operator()(void) const
960  {
961  return pGraph->numNodes();
962  };
963 #endif
964 
965  inline void operator()(uint32_t i)
966  {
967  float d_x = forceArrayX[i]* timeStep;
968  float d_y = forceArrayY[i]* timeStep;
969  double dsq = (d_x*d_x + d_y*d_y);
970  double d = sqrt(dsq);
971 
972  localContext->maxForceSq = max<double>(localContext->maxForceSq, (double)dsq );
973  localContext->avgForce += d;
974  if (d < FLT_MAX)
975  {
976  x[i] += d_x;
977  y[i] += d_y;
978  if (FLAGS & ZERO_GLOBAL_ARRAY)
979  {
980  forceArrayX[i] = 0.0;
981  forceArrayY[i] = 0.0;
982  } else
983  {
984  forceArrayX[i] = d_x;
985  forceArrayY[i] = d_y;
986  }
987  } else
988  {
989  forceArrayX[i] = 0.0;
990  forceArrayY[i] = 0.0;
991  }
992  }
993 
994  inline void operator()(uint32_t begin, uint32_t end)
995  {
996  for (uint32_t i = begin; i <= end; i++)
997  {
998  this->operator()(i);
999  }
1000  }
1001 
1002 private:
1003  float timeStep;
1004  float* x;
1005  float* y;
1006  float* forceArrayX;
1007  float* forceArrayY;
1012 };
1013 
1014 
1015 template<unsigned int FLAGS>
1017 {
1018  return NodeMoveFunctor<FLAGS>( pLocalContext );
1019 }
1020 
1021 
1022 template<typename TYP>
1023 inline void for_loop_array_set(uint32_t threadNr, uint32_t numThreads, TYP* a, uint32_t n, TYP value)
1024 {
1025  uint32_t s = n/numThreads;
1026  uint32_t o = s*threadNr;
1027  if (threadNr == numThreads-1)
1028  s = s + (n % numThreads);
1029 
1030  for (uint32_t i = 0; i < s; i++ ) { a[o+i] = value; }
1031 }
1032 
1033 }
1034 }
ogdf::fast_multipole_embedder::p2p_functor::fx
float * fx
Definition: FMEFunc.h:337
ogdf::fast_multipole_embedder::LinearQuadtree::minX
float minX() const
Definition: LinearQuadtree.h:617
ogdf::fast_multipole_embedder::l2l_functor::operator()
void operator()(LinearQuadtree::NodeID nodeIndex)
Definition: FMEFunc.h:289
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::fast_multipole_embedder::CollectForceFunctor::localContexts
FMELocalContext ** localContexts
Definition: FMEFunc.h:907
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfNodes
uint32_t numberOfNodes() const
returns the number of nodes in this tree
Definition: LinearQuadtree.h:477
ogdf::fast_multipole_embedder::FMENodeChainPartition::numNodes
uint32_t numNodes
Definition: FMEFunc.h:63
ogdf::fast_multipole_embedder::min_max_y_function
static min_max_functor< float > min_max_y_function(FMELocalContext *pLocalContext)
creates a min max functor for the y coords of the node
Definition: FMEFunc.h:151
ogdf::fast_multipole_embedder::l2p_functor::fy
float * fy
Definition: FMEFunc.h:309
ogdf::fast_multipole_embedder::LQPartitioner::newPartition
void newPartition()
Definition: FMEFunc.h:470
ogdf::fast_multipole_embedder::LinearQuadtree::NodeID
unsigned int NodeID
Definition: LinearQuadtree.h:52
ogdf::fast_multipole_embedder::EdgeForceFunctor::nodeInfo
NodeAdjInfo * nodeInfo
Definition: FMEFunc.h:796
ogdf::fast_multipole_embedder::LQMortonFunctor::s
float * s
Definition: FMEFunc.h:197
ogdf::fast_multipole_embedder::FMEGlobalOptions::edgeForceFactor
float edgeForceFactor
edge force factor for the main step
Definition: FMEFunc.h:75
ogdf::fast_multipole_embedder::FMEGlobalContext::pOptions
FMEGlobalOptions * pOptions
pointer to the global options
Definition: FMEFunc.h:107
ogdf::fast_multipole_embedder::EdgeForceFunctor::operator()
uint32_t operator()(void) const
Definition: FMEFunc.h:747
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfDirectNodes
uint32_t numberOfDirectNodes() const
Definition: LinearQuadtree.h:605
ogdf::fast_multipole_embedder::FMEGlobalContext::pExpansion
LinearQuadtreeExpansion * pExpansion
pointer to the coeefficients
Definition: FMEFunc.h:103
ogdf::fast_multipole_embedder::operator&
int operator&(int lhs, FMEEdgeForce rhs)
Definition: FMEFunc.h:726
ogdf::fast_multipole_embedder::D2DFunctor::quadtree
LinearQuadtree * quadtree
Definition: FMEFunc.h:715
ogdf::fast_multipole_embedder::m2l_functor::expansions
LinearQuadtreeExpansion & expansions
Definition: FMEFunc.h:258
ogdf::fast_multipole_embedder::FMEGlobalOptions::stopCritForce
double stopCritForce
stopping criteria
Definition: FMEFunc.h:85
LinearQuadtree.h
Declaration of class LinearQuadtree.
ogdf::fast_multipole_embedder::FMELocalContext::maxForceSq
double maxForceSq
local maximum force
Definition: FMEFunc.h:124
ogdf::fast_multipole_embedder::p2p_function
static p2p_functor p2p_function(FMELocalContext *pLocalContext)
creates Local-to-Point functor
Definition: FMEFunc.h:366
ogdf::fast_multipole_embedder::NDFunctor::operator()
void operator()(uint32_t i)
Definition: FMEFunc.h:647
ogdf::fast_multipole_embedder::EdgeForceFunctor::forceArrayY
float * forceArrayY
Definition: FMEFunc.h:802
ogdf::fast_multipole_embedder::FMEGlobalOptions::normNodeSize
float normNodeSize
average node size when node sizes are normalized
Definition: FMEFunc.h:78
ogdf::fast_multipole_embedder::LQCoordsFunctor
Computes the coords and size of the i-th node in the LinearQuadtree.
Definition: FMEFunc.h:550
ogdf::fast_multipole_embedder::LinearQuadtree::directNode
NodeID directNode(uint32_t i) const
Definition: LinearQuadtree.h:607
ogdf::fast_multipole_embedder::CollectForceFunctor::operator()
uint32_t operator()(void) const
Definition: FMEFunc.h:860
ogdf::fast_multipole_embedder::ArrayGraph
Definition: ArrayGraph.h:40
ogdf::fast_multipole_embedder::LQCoordsFunctor::operator()
void operator()(uint32_t i)
Definition: FMEFunc.h:564
ogdf::fast_multipole_embedder::D2DFunctor::D2DFunctor
D2DFunctor(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:677
ogdf::fast_multipole_embedder::LinearQuadtree::forall_children
forall_children_functor< F > forall_children(F f) const
creator
Definition: LinearQuadtree.h:149
ogdf::fast_multipole_embedder::l2l_functor::expansions
LinearQuadtreeExpansion & expansions
Definition: FMEFunc.h:280
ogdf::fast_multipole_embedder::LQMortonFunctor::translate_y
float translate_y
Definition: FMEFunc.h:193
ogdf::fast_multipole_embedder::D2DFunctor::operator()
void operator()(uint32_t i)
Definition: FMEFunc.h:690
ogdf::fast_multipole_embedder::LinearQuadtree::firstInnerNode
NodeID firstInnerNode() const
Definition: LinearQuadtree.h:592
ogdf::fast_multipole_embedder::FMEGlobalOptions::doPostProcessing
bool doPostProcessing
enable postprocessing
Definition: FMEFunc.h:83
ogdf::fast_multipole_embedder::D2DFunctor::forceArrayX
float * forceArrayX
Definition: FMEFunc.h:717
ogdf::fast_multipole_embedder::l2p_functor::l2p_functor
l2p_functor(const LinearQuadtree &t, LinearQuadtreeExpansion &e, float *x, float *y)
Definition: FMEFunc.h:311
ogdf::fast_multipole_embedder::LQCoordsFunctor::quadtree
LinearQuadtree * quadtree
Definition: FMEFunc.h:578
ogdf::fast_multipole_embedder::NDFunctor::operator()
uint32_t operator()(void) const
Definition: FMEFunc.h:642
ogdf::fast_multipole_embedder::NodeAdjInfo
Information about incident edges (16 bytes).
Definition: EdgeChain.h:42
ogdf::fast_multipole_embedder::FMETreePartition::pointCount
uint32_t pointCount
Definition: FMEFunc.h:50
ogdf::fast_multipole_embedder::WSPD
Class for the Well-Separated-Pairs-Decomposition (WSPD)
Definition: WSPD.h:41
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfInnerNodes
uint32_t numberOfInnerNodes() const
Definition: LinearQuadtree.h:594
ogdf::fast_multipole_embedder::LQPointUpdateFunctor::y
float * y
Definition: FMEFunc.h:542
ogdf::fast_multipole_embedder::l2p_functor::fx
float * fx
Definition: FMEFunc.h:308
ogdf::fast_multipole_embedder::LQPointUpdateFunctor::quadtree
LinearQuadtree * quadtree
Definition: FMEFunc.h:540
ogdf::fast_multipole_embedder::FMENodeChainPartition
Definition: FMEFunc.h:60
ogdf::fast_multipole_embedder::WSPD::wsNodeOfPair
uint32_t wsNodeOfPair(uint32_t currPairIndex, NodeID a) const
Returns the other node (not a) of the pair with index currPairIndex.
Definition: WSPD.h:101
ogdf::fast_multipole_embedder::EdgeAdjInfo::a
uint32_t a
First node of the pair.
Definition: EdgeChain.h:53
ogdf::fast_multipole_embedder::FMELocalContext::pGlobalContext
FMEGlobalContext * pGlobalContext
pointer to the global context
Definition: FMEFunc.h:121
ogdf::fast_multipole_embedder::l2l_functor::tree
const LinearQuadtree & tree
Definition: FMEFunc.h:279
ogdf::fast_multipole_embedder::LinearQuadtree::scaleInv
double scaleInv() const
Definition: LinearQuadtree.h:621
ogdf::fast_multipole_embedder::LQPointUpdateFunctor::LQPointUpdateFunctor
LQPointUpdateFunctor(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:511
ogdf::fast_multipole_embedder::FMELocalContext::leafPartition
FMENodeChainPartition leafPartition
chain of leaf nodes assigned to the thread
Definition: FMEFunc.h:133
ogdf::fast_multipole_embedder::ArrayGraph::numNodes
uint32_t numNodes() const
Returns the number of nodes.
Definition: ArrayGraph.h:56
ogdf::fast_multipole_embedder::FMETreePartition::for_loop
void for_loop(Func &func)
Definition: FMEFunc.h:53
ogdf::fast_multipole_embedder::EdgeForceFunctor
Definition: FMEFunc.h:731
ogdf::fast_multipole_embedder::LinearQuadtree::computeCoords
void computeCoords(NodeID nodeIndex)
Definition: LinearQuadtree.h:624
ogdf::fast_multipole_embedder::FMECollect::NoFactor
@ NoFactor
ogdf::fast_multipole_embedder::FMECollect::ZeroThreadArray
@ ZeroThreadArray
ogdf::fast_multipole_embedder::pair_call
static pair_call_functor< F, A > pair_call(F f, A a)
creates a pair call resulting in a call f(a, *)
Definition: FMEFunctional.h:141
ogdf::fast_multipole_embedder::FMECollect::EdgeFactor
@ EdgeFactor
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfDirectPairs
uint32_t numberOfDirectPairs() const
Definition: LinearQuadtree.h:603
ogdf::fast_multipole_embedder::TIME_STEP_NORMAL
static constexpr int TIME_STEP_NORMAL
Definition: FMEFunc.h:922
ogdf::fast_multipole_embedder::FMENodeChainPartition::begin
uint32_t begin
Definition: FMEFunc.h:62
ogdf::fast_multipole_embedder::p2m_functor::operator()
void operator()(LinearQuadtree::NodeID nodeIndex)
Definition: FMEFunc.h:209
ogdf::fast_multipole_embedder::ArrayGraph::nodeXPos
float * nodeXPos()
Returns the x coord array for all nodes.
Definition: ArrayGraph.h:165
ogdf::fast_multipole_embedder::LQPartitioner::l_par
std::list< uint32_t > l_par
Definition: FMEFunc.h:502
ogdf::fast_multipole_embedder::FMEGlobalContext::pGraph
ArrayGraph * pGraph
pointer to the array graph
Definition: FMEFunc.h:101
ogdf::fast_multipole_embedder::FMECollect::RepulsiveFactor
@ RepulsiveFactor
ogdf::fast_multipole_embedder::LinearQuadtree::nextNode
NodeID nextNode(NodeID nodeID) const
Definition: LinearQuadtree.h:374
ogdf::fast_multipole_embedder::LQMortonFunctor::quadtree
LinearQuadtree * quadtree
Definition: FMEFunc.h:191
ogdf::fast_multipole_embedder::l2p_functor::operator()
void operator()(LinearQuadtree::NodeID nodeIndex, LinearQuadtree::PointID pointIndex)
Definition: FMEFunc.h:313
LinearQuadtreeBuilder.h
Declaration of class LinearQuadtreeBuilder.
ogdf::fast_multipole_embedder::FMELocalContext::forceY
float * forceY
local force array for all nodes, points
Definition: FMEFunc.h:123
ogdf::fast_multipole_embedder::TIME_STEP_PREP
static constexpr int TIME_STEP_PREP
Definition: FMEFunc.h:923
ogdf::fast_multipole_embedder::p2p_functor::operator()
void operator()(LinearQuadtree::NodeID nodeIndex)
Definition: FMEFunc.h:356
ogdf::fast_multipole_embedder::LQMortonFunctor::operator()
void operator()(uint32_t begin, uint32_t end)
Definition: FMEFunc.h:182
ogdf::fast_multipole_embedder::CollectForceFunctor::globalArrayX
float * globalArrayX
Definition: FMEFunc.h:908
ogdf::fast_multipole_embedder::FMEGlobalContext::coolDown
float coolDown
Definition: FMEFunc.h:110
ogdf::fast_multipole_embedder::NodeMoveFunctor::operator()
void operator()(uint32_t begin, uint32_t end)
Definition: FMEFunc.h:994
ArrayGraph.h
Declaration of class ArrayGraph.
ogdf::fast_multipole_embedder::FMELocalContext::max_y
float max_y
global point, node max y coordinate for bounding box calculations
Definition: FMEFunc.h:129
ogdf::fast_multipole_embedder::NodeMoveFunctor::nodeMoveRadius
float * nodeMoveRadius
Definition: FMEFunc.h:1008
LinearQuadtreeExpansion.h
Declaration of class LinearQuadtreeExpansion.
ogdf::fast_multipole_embedder::LQPointUpdateFunctor::operator()
uint32_t operator()(void) const
Definition: FMEFunc.h:519
ogdf::fast_multipole_embedder::LinearQuadtree::pointSize
float pointSize(PointID point) const
Definition: LinearQuadtree.h:513
ogdf::fast_multipole_embedder::FMELocalContext::avgForce
double avgForce
local maximum force
Definition: FMEFunc.h:125
ogdf::fast_multipole_embedder::LQPartitioner::numThreads
uint32_t numThreads
Definition: FMEFunc.h:500
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfLeaves
uint32_t numberOfLeaves() const
Definition: LinearQuadtree.h:598
ogdf::fast_multipole_embedder::FMEGlobalOptions::preProcMaxNumIterations
uint32_t preProcMaxNumIterations
number of iterations the preprocessing is applied
Definition: FMEFunc.h:72
ogdf::fast_multipole_embedder::EdgeForceFunctor::operator()
void operator()(uint32_t i)
Definition: FMEFunc.h:752
ogdf::fast_multipole_embedder::WSPD::nextPair
uint32_t nextPair(uint32_t currPairIndex, NodeID a) const
Returns the index of the next pair of currPairIndex of the node with index a.
Definition: WSPD.h:95
ogdf::fast_multipole_embedder::FMELocalContext::numInnerNodes
uint32_t numInnerNodes
number of inner nodes the thread prepared
Definition: FMEFunc.h:137
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfPoints
uint32_t numberOfPoints(NodeID nodeID) const
returns the number of points contained in the subtree of node nodeID
Definition: LinearQuadtree.h:453
ogdf::fast_multipole_embedder::m2m_functor::m2m_functor
m2m_functor(const LinearQuadtree &t, LinearQuadtreeExpansion &e)
Definition: FMEFunc.h:234
ogdf::fast_multipole_embedder::FMEGlobalContext::pQuadtree
LinearQuadtree * pQuadtree
pointer to the quadtree
Definition: FMEFunc.h:102
ogdf::fast_multipole_embedder::FMETreePartition::nodes
std::list< LinearQuadtree::NodeID > nodes
Definition: FMEFunc.h:49
ogdf::fast_multipole_embedder::FMEGlobalContext::currAvgEdgeLength
double currAvgEdgeLength
Definition: FMEFunc.h:115
ogdf::fast_multipole_embedder::LinearQuadtreeExpansion
Definition: LinearQuadtreeExpansion.h:39
ogdf::fast_multipole_embedder::LinearQuadtreeExpansion::P2M
void P2M(uint32_t point, uint32_t receiver)
adds a point with the given charge to the receiver expansion
ogdf::fast_multipole_embedder::FMELocalContext::firstInnerNode
LinearQuadtree::NodeID firstInnerNode
first inner nodes the thread prepared
Definition: FMEFunc.h:135
ogdf::fast_multipole_embedder::LinearQuadtree::LQPoint::mortonNr
MortonNR mortonNr
Definition: LinearQuadtree.h:57
ogdf::fast_multipole_embedder::NodeMoveFunctor::y
float * y
Definition: FMEFunc.h:1005
ogdf::fast_multipole_embedder::m2m_functor::operator()
void operator()(LinearQuadtree::NodeID parent, LinearQuadtree::NodeID child)
Definition: FMEFunc.h:236
ogdf::fast_multipole_embedder::LQPartitioner::partitionNodeChains
void partitionNodeChains()
Definition: FMEFunc.h:384
ogdf::fast_multipole_embedder::FMEGlobalOptions::doPrepProcessing
bool doPrepProcessing
enable preprocessing
Definition: FMEFunc.h:82
ogdf::fast_multipole_embedder::NodeMoveFunctor::operator()
void operator()(uint32_t i)
Definition: FMEFunc.h:965
ogdf::fast_multipole_embedder::LinearQuadtreeExpansion::L2L
void L2L(uint32_t source, uint32_t receiver)
shifts the source local coefficient to the center of the receiver and adds them
ogdf::fast_multipole_embedder::EdgeForceFunctor::edgeInfo
EdgeAdjInfo * edgeInfo
Definition: FMEFunc.h:795
ogdf::fast_multipole_embedder::node_move_function
static NodeMoveFunctor< FLAGS > node_move_function(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:1016
ogdf::fast_multipole_embedder::CollectForceFunctor::pGraph
ArrayGraph * pGraph
Definition: FMEFunc.h:905
ogdf::fast_multipole_embedder::LinearQuadtree::firstPoint
PointID firstPoint(NodeID nodeID) const
Definition: LinearQuadtree.h:389
ogdf::fast_multipole_embedder::LinearQuadtree::pointLeaf
NodeID pointLeaf(PointID point) const
Definition: LinearQuadtree.h:499
ogdf::fast_multipole_embedder::l2l_functor
Local-to-Local functor.
Definition: FMEFunc.h:277
ogdf::fast_multipole_embedder::LinearQuadtree::child
NodeID child(NodeID nodeID, uint32_t i) const
returns the i th child index of node nodeID
Definition: LinearQuadtree.h:429
ogdf::fast_multipole_embedder::m2m_function
static m2m_functor m2m_function(FMELocalContext *pLocalContext)
creates Multipole-to-Multipole functor
Definition: FMEFunc.h:249
ogdf::fast_multipole_embedder::M2LFunctor::operator()
uint32_t operator()(void) const
Definition: FMEFunc.h:597
ogdf::fast_multipole_embedder::LQPointUpdateFunctor::operator()
void operator()(uint32_t i)
Definition: FMEFunc.h:524
ogdf::fast_multipole_embedder::LQPartitioner::currPartition
FMETreePartition * currPartition()
Definition: FMEFunc.h:493
ogdf::fast_multipole_embedder::CollectForceFunctor::numContexts
uint32_t numContexts
Definition: FMEFunc.h:910
ogdf::fast_multipole_embedder::FMEGlobalOptions
the main global options for a run
Definition: FMEFunc.h:68
ogdf::fast_multipole_embedder::FMEGlobalContext::min_y
float min_y
global point, node min y coordinate for bounding box calculations
Definition: FMEFunc.h:113
ogdf::fast_multipole_embedder::FMELocalContext::min_x
float min_x
global point, node min x coordinate for bounding box calculations
Definition: FMEFunc.h:126
ogdf::fast_multipole_embedder::FMEEdgeForce::SubRep
@ SubRep
ogdf::fast_multipole_embedder::LQPartitioner::tree
LinearQuadtree * tree
Definition: FMEFunc.h:503
ogdf::fast_multipole_embedder::LinearQuadtree::LQPoint::ref
uint32_t ref
Definition: LinearQuadtree.h:59
ogdf::fast_multipole_embedder::LQMortonFunctor::operator()
void operator()(uint32_t i)
Definition: FMEFunc.h:175
ogdf::fast_multipole_embedder::M2LFunctor
Converts the multipole expansion coefficients from all nodes which are well separated from the i-th n...
Definition: FMEFunc.h:587
WSPD.h
Declaration of class WSPD (well-separated pair decomposition).
ogdf::fast_multipole_embedder::LinearQuadtree::pointX
float pointX(PointID point) const
Definition: LinearQuadtree.h:509
ogdf::fast_multipole_embedder::FMEGlobalContext
Global Context.
Definition: FMEFunc.h:97
ogdf::fast_multipole_embedder::USE_NODE_MOVE_RAD
static constexpr int USE_NODE_MOVE_RAD
Definition: FMEFunc.h:925
ogdf::fast_multipole_embedder::p2p_functor::fy
float * fy
Definition: FMEFunc.h:338
ogdf::fast_multipole_embedder::ArrayGraph::nodeMoveRadius
float * nodeMoveRadius()
Returns the node movement radius array for all nodes.
Definition: ArrayGraph.h:183
ogdf::fast_multipole_embedder::LQCoordsFunctor::operator()
void operator()(uint32_t begin, uint32_t end)
Definition: FMEFunc.h:569
ogdf::fast_multipole_embedder::EdgeForceFunctor::EdgeForceFunctor
EdgeForceFunctor(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:734
ogdf::fast_multipole_embedder::NodeMoveFunctor::NodeMoveFunctor
NodeMoveFunctor(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:932
ogdf::fast_multipole_embedder::LQMortonFunctor::LQMortonFunctor
LQMortonFunctor(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:159
ogdf::fast_multipole_embedder::D2DFunctor::operator()
void operator()(uint32_t begin, uint32_t end)
Definition: FMEFunc.h:706
ogdf::fast_multipole_embedder::FMEGlobalOptions::stopCritAvgForce
double stopCritAvgForce
stopping criteria
Definition: FMEFunc.h:86
ogdf::fast_multipole_embedder::FMECollect
FMECollect
Definition: FMEFunc.h:813
ogdf::fast_multipole_embedder::LinearQuadtree::firstLeaf
NodeID firstLeaf() const
Definition: LinearQuadtree.h:596
ogdf::fast_multipole_embedder::edge_force_function
static EdgeForceFunctor< FLAGS > edge_force_function(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:807
ogdf::fast_multipole_embedder::LQPartitioner::localContexts
FMELocalContext ** localContexts
Definition: FMEFunc.h:504
ogdf::fast_multipole_embedder::m2l_functor::m2l_functor
m2l_functor(LinearQuadtreeExpansion &e)
Definition: FMEFunc.h:260
ogdf::fast_multipole_embedder::ArrayGraph::nodeInfo
NodeAdjInfo & nodeInfo(uint32_t i)
Returns the adjacency information for the node at index i in m_nodeAdj.
Definition: ArrayGraph.h:141
ogdf::fast_multipole_embedder::NDFunctor
Calculates the repulsive forces acting between all nodes inside the cell of the i-th LinearQuadtree n...
Definition: FMEFunc.h:631
ogdf::fast_multipole_embedder::p2p_functor::p2p_functor
p2p_functor(const LinearQuadtree &t, float *x, float *y)
Definition: FMEFunc.h:340
ogdf::fast_multipole_embedder::l2p_functor
Local-to-Point functor.
Definition: FMEFunc.h:304
ogdf::fast_multipole_embedder::M2LFunctor::operator()
void operator()(uint32_t i)
Definition: FMEFunc.h:602
ogdf::fast_multipole_embedder::FMEGlobalContext::min_x
float min_x
global point, node min x coordinate for bounding box calculations
Definition: FMEFunc.h:111
ogdf::fast_multipole_embedder::FMEGlobalContext::globalForceY
float * globalForceY
the global node force y array
Definition: FMEFunc.h:106
ogdf::fast_multipole_embedder::m2l_functor::operator()
void operator()(LinearQuadtree::NodeID nodeIndexSource, LinearQuadtree::NodeID nodeIndexReceiver)
Definition: FMEFunc.h:262
ogdf::fast_multipole_embedder::M2LFunctor::quadtree
LinearQuadtree * quadtree
Definition: FMEFunc.h:622
ogdf::fast_multipole_embedder::min_max_x_function
static min_max_functor< float > min_max_x_function(FMELocalContext *pLocalContext)
creates a min max functor for the x coords of the node
Definition: FMEFunc.h:145
ogdf::fast_multipole_embedder::LinearQuadtree::LQPoint
Definition: LinearQuadtree.h:55
ogdf::fast_multipole_embedder::LinearQuadtree::pointY
float pointY(PointID point) const
Definition: LinearQuadtree.h:511
ogdf::fast_multipole_embedder::LinearQuadtree::point
LQPoint & point(PointID pointID)
Definition: LinearQuadtree.h:399
ogdf::fast_multipole_embedder::FMELocalContext
Local thread Context.
Definition: FMEFunc.h:119
ogdf::fast_multipole_embedder::CollectForceFunctor::globalContext
FMEGlobalContext * globalContext
Definition: FMEFunc.h:906
ogdf::fast_multipole_embedder::LQCoordsFunctor::operator()
uint32_t operator()(void) const
Definition: FMEFunc.h:559
ogdf::fast_multipole_embedder::LinearQuadtree::minY
float minY() const
Definition: LinearQuadtree.h:618
ogdf::fast_multipole_embedder::D2DFunctor
Calculates the repulsive forces acting between all nodes of the direct interacting cells of the i-th ...
Definition: FMEFunc.h:674
ogdf::fast_multipole_embedder::LinearQuadtreeExpansion::M2M
void M2M(uint32_t source, uint32_t receiver)
shifts the source multipole coefficient to the center of the receiver and adds them
ogdf::fast_multipole_embedder::ArrayGraph::desiredEdgeLength
float * desiredEdgeLength()
Returns the edge length array for all edges.
Definition: ArrayGraph.h:186
ogdf::fast_multipole_embedder::l2l_function
static l2l_functor l2l_function(FMELocalContext *pLocalContext)
creates Local-to-Local functor
Definition: FMEFunc.h:297
ogdf::fast_multipole_embedder::FMECollect::EdgeFactorRep
@ EdgeFactorRep
ogdf::fast_multipole_embedder::LQMortonFunctor::x
float * x
Definition: FMEFunc.h:195
ogdf::fast_multipole_embedder::p2m_functor
Point-to-Multipole functor.
Definition: FMEFunc.h:202
ogdf::fast_multipole_embedder::m2m_functor
Multipole-to-Multipole functor.
Definition: FMEFunc.h:229
ogdf::fast_multipole_embedder::NodeMoveFunctor::x
float * x
Definition: FMEFunc.h:1004
ogdf::fast_multipole_embedder::NDFunctor::quadtree
LinearQuadtree * quadtree
Definition: FMEFunc.h:664
ogdf::fast_multipole_embedder::m2m_functor::expansions
LinearQuadtreeExpansion & expansions
Definition: FMEFunc.h:232
ogdf::fast_multipole_embedder::FMEGlobalContext::max_y
float max_y
global point, node max y coordinate for bounding box calculations
Definition: FMEFunc.h:114
ogdf::fast_multipole_embedder::NodeMoveFunctor::localContext
FMELocalContext * localContext
Definition: FMEFunc.h:1011
ogdf::fast_multipole_embedder::FMEGlobalOptions::maxNumIterations
uint32_t maxNumIterations
maximum number of iterations in the main step
Definition: FMEFunc.h:79
ogdf::fast_multipole_embedder::FMECollect::Tree2GraphOrder
@ Tree2GraphOrder
ogdf::fast_multipole_embedder::m2l_functor
Multipole-to-Local functor.
Definition: FMEFunc.h:256
ogdf::fast_multipole_embedder::FMEGlobalOptions::multipolePrecision
uint32_t multipolePrecision
Definition: FMEFunc.h:89
ogdf::fast_multipole_embedder::collect_force_function
static CollectForceFunctor< FLAGS > collect_force_function(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:916
ogdf::fast_multipole_embedder::LQPartitioner
The partitioner which partitions the quadtree into subtrees and partitions the sequence of inner node...
Definition: FMEFunc.h:373
ogdf::fast_multipole_embedder::FMEGlobalContext::max_x
float max_x
global point, node max x coordinate for bounding box calculations
Definition: FMEFunc.h:112
ogdf::fast_multipole_embedder::M2LFunctor::wspd
WSPD * wspd
Definition: FMEFunc.h:624
ogdf::fast_multipole_embedder::p2m_function
static p2m_functor p2m_function(FMELocalContext *pLocalContext)
creates a Point-to-Multipole functor
Definition: FMEFunc.h:222
ogdf::fast_multipole_embedder::LQMortonFunctor::y
float * y
Definition: FMEFunc.h:196
ogdf::fast_multipole_embedder::FMELocalContext::firstLeaf
LinearQuadtree::NodeID firstLeaf
first leaves the thread prepared
Definition: FMEFunc.h:139
ogdf::fast_multipole_embedder::l2p_functor::tree
const LinearQuadtree & tree
Definition: FMEFunc.h:306
ogdf::fast_multipole_embedder::NDFunctor::quadtreeExp
LinearQuadtreeExpansion * quadtreeExp
Definition: FMEFunc.h:665
ogdf::fast_multipole_embedder::LQMortonFunctor::translate_x
float translate_x
Definition: FMEFunc.h:192
ogdf::fast_multipole_embedder::LQMortonFunctor::scale
double scale
Definition: FMEFunc.h:194
ogdf::fast_multipole_embedder::ArrayGraph::nodeSize
float * nodeSize()
Returns the node size array for all nodes.
Definition: ArrayGraph.h:177
ogdf::fast_multipole_embedder::FMEEdgeForce
FMEEdgeForce
Definition: FMEFunc.h:721
ogdf::fast_multipole_embedder::FMELocalContext::numLeaves
uint32_t numLeaves
number of leaves the thread prepared
Definition: FMEFunc.h:141
ogdf::fast_multipole_embedder::EdgeForceFunctor::x
float * x
Definition: FMEFunc.h:793
ogdf::fast_multipole_embedder::CollectForceFunctor::CollectForceFunctor
CollectForceFunctor(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:840
ogdf::fast_multipole_embedder::LinearQuadtree
Definition: LinearQuadtree.h:47
ogdf::fast_multipole_embedder::LinearQuadtree::PointID
unsigned int PointID
Definition: LinearQuadtree.h:53
ogdf::fast_multipole_embedder::LQCoordsFunctor::LQCoordsFunctor
LQCoordsFunctor(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:553
ogdf::fast_multipole_embedder::CollectForceFunctor
Definition: FMEFunc.h:836
ogdf::fast_multipole_embedder::min_max_functor
generic min max functor for an array
Definition: FMEFunctional.h:206
ogdf::fast_multipole_embedder::LQMortonFunctor
Definition: FMEFunc.h:156
ogdf::fast_multipole_embedder::FMEGlobalOptions::timeStep
float timeStep
time step factor for the main step
Definition: FMEFunc.h:74
ogdf::fast_multipole_embedder::NodeMoveFunctor
Definition: FMEFunc.h:928
ogdf::fast_multipole_embedder::p2m_functor::tree
const LinearQuadtree & tree
Definition: FMEFunc.h:204
ogdf::fast_multipole_embedder::FMEGlobalOptions::normEdgeLength
float normEdgeLength
average edge length when desired edge length are normalized
Definition: FMEFunc.h:77
ogdf::fast_multipole_embedder::LQPartitioner::currThread
uint32_t currThread
Definition: FMEFunc.h:501
ogdf::fast_multipole_embedder::LQMortonFunctor::operator()
uint32_t operator()(void) const
Definition: FMEFunc.h:170
ogdf::fast_multipole_embedder::M2LFunctor::M2LFunctor
M2LFunctor(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:590
ogdf::fast_multipole_embedder::WSPD::firstPairEntry
uint32_t firstPairEntry(NodeID nodeID) const
Returns the index of the first pair of node nodeID.
Definition: WSPD.h:107
ogdf::fast_multipole_embedder::operator|
constexpr int operator|(int lhs, FMECollect rhs)
Definition: FMEFunc.h:827
ogdf::fast_multipole_embedder::p2p_functor
Local-to-Point functor.
Definition: FMEFunc.h:334
ogdf::fast_multipole_embedder::LQPointUpdateFunctor::s
float * s
Definition: FMEFunc.h:543
ogdf::fast_multipole_embedder::NodeAdjInfo::degree
uint32_t degree
Total count of pairs where is either the first or second node.
Definition: EdgeChain.h:44
ogdf::fast_multipole_embedder::D2DFunctor::quadtreeExp
LinearQuadtreeExpansion * quadtreeExp
Definition: FMEFunc.h:716
ogdf::fast_multipole_embedder::LinearQuadtree::isLeaf
bool isLeaf(NodeID nodeID) const
returns true if the given node index is a leaf
Definition: LinearQuadtree.h:441
ogdf::fast_multipole_embedder::CollectForceFunctor::factor
float factor
Definition: FMEFunc.h:911
ogdf::fast_multipole_embedder::ArrayGraph::nodeYPos
float * nodeYPos()
Returns the y coord array for all nodes.
Definition: ArrayGraph.h:171
ogdf::fast_multipole_embedder::l2p_function
static l2p_functor l2p_function(FMELocalContext *pLocalContext)
creates Local-to-Point functor
Definition: FMEFunc.h:327
ogdf::fast_multipole_embedder::NDFunctor::forceArrayY
float * forceArrayY
Definition: FMEFunc.h:667
ogdf::fast_multipole_embedder::EdgeForceFunctor::pGraph
ArrayGraph * pGraph
Definition: FMEFunc.h:798
ogdf::fast_multipole_embedder::p2p_functor::operator()
void operator()(LinearQuadtree::NodeID nodeIndexA, LinearQuadtree::NodeID nodeIndexB)
Definition: FMEFunc.h:342
ogdf::fast_multipole_embedder::m2l_function
static m2l_functor m2l_function(FMELocalContext *pLocalContext)
creates Multipole-to-Local functor
Definition: FMEFunc.h:270
ogdf::fast_multipole_embedder::LQPartitioner::LQPartitioner
LQPartitioner(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:376
ogdf::fast_multipole_embedder::FMEGlobalOptions::preProcEdgeForceFactor
float preProcEdgeForceFactor
edge force factor for the preprocessing step
Definition: FMEFunc.h:71
ogdf::fast_multipole_embedder::LQPartitioner::partition
void partition()
Definition: FMEFunc.h:445
ogdf::fast_multipole_embedder::p2m_functor::p2m_functor
p2m_functor(const LinearQuadtree &t, LinearQuadtreeExpansion &e)
Definition: FMEFunc.h:207
ogdf::fast_multipole_embedder::EdgeAdjInfo
Information about an edge (16 bytes).
Definition: EdgeChain.h:51
ogdf::fast_multipole_embedder::ArrayGraph::numEdges
uint32_t numEdges() const
Returns the number of edges.
Definition: ArrayGraph.h:59
ogdf::fast_multipole_embedder::m2m_functor::operator()
void operator()(LinearQuadtree::NodeID nodeIndex)
Definition: FMEFunc.h:241
ogdf::fast_multipole_embedder::EdgeForceFunctor::desiredEdgeLength
float * desiredEdgeLength
Definition: FMEFunc.h:799
ogdf::fast_multipole_embedder::FMELocalContext::forceX
float * forceX
local force array for all nodes, points
Definition: FMEFunc.h:122
ogdf::fast_multipole_embedder::FMELocalContext::max_x
float max_x
global point, node max x coordinate for bounding box calculations
Definition: FMEFunc.h:127
ogdf::fast_multipole_embedder::LinearQuadtree::root
NodeID root() const
returns the index of the root
Definition: LinearQuadtree.h:465
ogdf::fast_multipole_embedder::LinearQuadtree::refOfPoint
uint32_t refOfPoint(PointID id) const
Definition: LinearQuadtree.h:563
ogdf::fast_multipole_embedder::CollectForceFunctor::operator()
void operator()(uint32_t begin, uint32_t end)
Definition: FMEFunc.h:896
ogdf::fast_multipole_embedder::FMEGlobalOptions::repForceFactor
float repForceFactor
repulsive force factor for the main step
Definition: FMEFunc.h:76
ogdf::fast_multipole_embedder::M2LFunctor::operator()
void operator()(uint32_t begin, uint32_t end)
Definition: FMEFunc.h:613
ogdf::fast_multipole_embedder::NDFunctor::NDFunctor
NDFunctor(FMELocalContext *pLocalContext)
Definition: FMEFunc.h:634
ogdf::fast_multipole_embedder::FMEGlobalContext::numThreads
uint32_t numThreads
number of threads, local contexts
Definition: FMEFunc.h:100
ogdf::fast_multipole_embedder::CollectForceFunctor::globalArrayY
float * globalArrayY
Definition: FMEFunc.h:909
ogdf::fast_multipole_embedder::NodeMoveFunctor::timeStep
float timeStep
Definition: FMEFunc.h:1003
ogdf::fast_multipole_embedder::FMEGlobalContext::scaleFactor
float scaleFactor
var
Definition: FMEFunc.h:109
ogdf::fast_multipole_embedder::EdgeForceFunctor::forceArrayX
float * forceArrayX
Definition: FMEFunc.h:801
ogdf::fast_multipole_embedder::FMEGlobalOptions::minNumIterations
uint32_t minNumIterations
minimum number of iterations to be done regardless of any other conditions
Definition: FMEFunc.h:80
ogdf::fast_multipole_embedder::FMEGlobalOptions::stopCritConstSq
double stopCritConstSq
stopping criteria
Definition: FMEFunc.h:87
ogdf::fast_multipole_embedder::FMELocalContext::innerNodePartition
FMENodeChainPartition innerNodePartition
chain of inner nodes assigned to the thread
Definition: FMEFunc.h:132
ogdf::fast_multipole_embedder::FMELocalContext::lastInnerNode
LinearQuadtree::NodeID lastInnerNode
last inner nodes the thread prepared
Definition: FMEFunc.h:136
ogdf::fast_multipole_embedder::FMELocalContext::min_y
float min_y
global point, node min y coordinate for bounding box calculations
Definition: FMEFunc.h:128
ogdf::fast_multipole_embedder::LinearQuadtree::nodeFence
void nodeFence(NodeID nodeID)
Definition: LinearQuadtree.h:573
ogdf::fast_multipole_embedder::l2p_functor::operator()
void operator()(LinearQuadtree::PointID pointIndex)
Definition: FMEFunc.h:318
ogdf::fast_multipole_embedder::p2m_functor::expansions
LinearQuadtreeExpansion & expansions
Definition: FMEFunc.h:205
ogdf::fast_multipole_embedder::WSPD::numWSNodes
uint32_t numWSNodes(NodeID a) const
Returns the number of well separated nodes for node a.
Definition: WSPD.h:59
ogdf::fast_multipole_embedder::for_loop_array_set
void for_loop_array_set(uint32_t threadNr, uint32_t numThreads, TYP *a, uint32_t n, TYP value)
Definition: FMEFunc.h:1023
ogdf::fast_multipole_embedder::NodeMoveFunctor::forceArrayX
float * forceArrayX
Definition: FMEFunc.h:1006
ogdf::fast_multipole_embedder::p2p_functor::tree
const LinearQuadtree & tree
Definition: FMEFunc.h:336
ogdf::fast_multipole_embedder::NDFunctor::operator()
void operator()(uint32_t begin, uint32_t end)
Definition: FMEFunc.h:655
ogdf::fast_multipole_embedder::LinearQuadtree::directNodeB
NodeID directNodeB(uint32_t i) const
Definition: LinearQuadtree.h:611
ogdf::fast_multipole_embedder::EdgeForceFunctor::nodeSize
float * nodeSize
Definition: FMEFunc.h:800
ogdf::fast_multipole_embedder::ZERO_GLOBAL_ARRAY
static constexpr int ZERO_GLOBAL_ARRAY
Definition: FMEFunc.h:924
ogdf::fast_multipole_embedder::LQPointUpdateFunctor
Definition: FMEFunc.h:508
ogdf::fast_multipole_embedder::LQPointUpdateFunctor::x
float * x
Definition: FMEFunc.h:541
ogdf::fast_multipole_embedder::FMELocalContext::currAvgEdgeLength
double currAvgEdgeLength
Definition: FMEFunc.h:130
FMEKernel.h
Declaration of FME kernel.
ogdf::fast_multipole_embedder::NodeMoveFunctor::currentEdgeLength
float * currentEdgeLength
Definition: FMEFunc.h:1009
ogdf::fast_multipole_embedder::m2m_functor::tree
const LinearQuadtree & tree
Definition: FMEFunc.h:231
ogdf::fast_multipole_embedder::LinearQuadtree::directNodeA
NodeID directNodeA(uint32_t i) const
Definition: LinearQuadtree.h:609
ogdf::fast_multipole_embedder::LQCoordsFunctor::quadtreeExp
LinearQuadtreeExpansion * quadtreeExp
Definition: FMEFunc.h:579
ogdf::fast_multipole_embedder::FMEGlobalContext::pLocalContext
FMELocalContext ** pLocalContext
all local contexts
Definition: FMEFunc.h:99
ogdf::fast_multipole_embedder::FMEGlobalContext::pWSPD
WSPD * pWSPD
pointer to the well separated pairs decomposition
Definition: FMEFunc.h:104
ogdf::fast_multipole_embedder::l2p_functor::expansions
LinearQuadtreeExpansion & expansions
Definition: FMEFunc.h:307
ogdf::fast_multipole_embedder::LQPointUpdateFunctor::operator()
void operator()(uint32_t begin, uint32_t end)
Definition: FMEFunc.h:531
ogdf::fast_multipole_embedder::FMELocalContext::lastLeaf
LinearQuadtree::NodeID lastLeaf
last leaves the thread prepared
Definition: FMEFunc.h:140
ogdf::fast_multipole_embedder::CollectForceFunctor::operator()
void operator()(uint32_t i)
Definition: FMEFunc.h:866
ogdf::fast_multipole_embedder::LinearQuadtree::setPoint
void setPoint(PointID id, float x, float y, uint32_t ref)
Definition: LinearQuadtree.h:533
ogdf::fast_multipole_embedder::FMEGlobalContext::earlyExit
bool earlyExit
var for the main thread to notify the other threads that they are done
Definition: FMEFunc.h:108
ogdf::fast_multipole_embedder::l2l_functor::l2l_functor
l2l_functor(const LinearQuadtree &t, LinearQuadtreeExpansion &e)
Definition: FMEFunc.h:282
ogdf::fast_multipole_embedder::D2DFunctor::operator()
uint32_t operator()(void) const
Definition: FMEFunc.h:685
ogdf::fast_multipole_embedder::NodeMoveFunctor::pGraph
ArrayGraph * pGraph
Definition: FMEFunc.h:1010
ogdf::fast_multipole_embedder::LinearQuadtreeExpansion::L2P
void L2P(uint32_t source, uint32_t point, float &fx, float &fy)
evaluates the derivate of the local expansion at the point and adds the forces to fx fy
ogdf::fast_multipole_embedder::FMEGlobalContext::globalForceX
float * globalForceX
the global node force x array
Definition: FMEFunc.h:105
ogdf::fast_multipole_embedder::NodeMoveFunctor::forceArrayY
float * forceArrayY
Definition: FMEFunc.h:1007
ogdf::fast_multipole_embedder::EdgeAdjInfo::b
uint32_t b
Second node of the pair.
Definition: EdgeChain.h:54
ogdf::fast_multipole_embedder::M2LFunctor::quadtreeExp
LinearQuadtreeExpansion * quadtreeExp
Definition: FMEFunc.h:623
ogdf::fast_multipole_embedder::LinearQuadtreeExpansion::M2L
void M2L(uint32_t source, uint32_t receiver)
converts the source multipole coefficient in to a local coefficients at the center of the receiver an...
ogdf::fast_multipole_embedder::NDFunctor::forceArrayX
float * forceArrayX
Definition: FMEFunc.h:666
ogdf::fast_multipole_embedder::LQPartitioner::newPartition
void newPartition(uint32_t nodeID)
Definition: FMEFunc.h:459
ogdf::fast_multipole_embedder::FMEGlobalOptions::preProcTimeStep
float preProcTimeStep
time step factor for the preprocessing step
Definition: FMEFunc.h:70
ogdf::fast_multipole_embedder::FMETreePartition
struct for distributing subtrees to the threads
Definition: FMEFunc.h:47
ogdf::fast_multipole_embedder::LQPartitioner::numPointsPerThread
uint32_t numPointsPerThread
Definition: FMEFunc.h:499
ogdf::fast_multipole_embedder::ArrayGraph::edgeInfo
EdgeAdjInfo & edgeInfo(uint32_t i)
Returns the adjacency information for the edge at index i in m_edgeAdj.
Definition: ArrayGraph.h:147
ogdf::fast_multipole_embedder::l2l_functor::operator()
void operator()(LinearQuadtree::NodeID parent, LinearQuadtree::NodeID child)
Definition: FMEFunc.h:284
ogdf::fast_multipole_embedder::FMELocalContext::treePartition
FMETreePartition treePartition
tree partition assigned to the thread
Definition: FMEFunc.h:131
ogdf::fast_multipole_embedder::EdgeForceFunctor::y
float * y
Definition: FMEFunc.h:794
ogdf::fast_multipole_embedder::LinearQuadtree::numberOfChilds
uint32_t numberOfChilds(NodeID nodeID) const
returns the number of children of node nodeID. for an inner node this is 1..4 and can be accessed by ...
Definition: LinearQuadtree.h:417
ogdf::fast_multipole_embedder::eval_direct_fast
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:172
ogdf::fast_multipole_embedder::EdgeForceFunctor::operator()
void operator()(uint32_t begin, uint32_t end)
Definition: FMEFunc.h:784
ogdf::fast_multipole_embedder::D2DFunctor::forceArrayY
float * forceArrayY
Definition: FMEFunc.h:718
ogdf::fast_multipole_embedder::FMEEdgeForce::DivDegree
@ DivDegree