Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

FastUtils.h
Go to the documentation of this file.
1 
32 #pragma once
33 
35 
36 #ifdef OGDF_SYSTEM_UNIX
37 #include <sys/time.h>
38 #endif
39 
40 #ifdef OGDF_FME_KERNEL_USE_SSE
42 #endif
43 
44 namespace ogdf {
45 namespace fast_multipole_embedder {
46 
47 // use SSE for Multipole computations
48 //#define OGDF_FME_KERNEL_USE_SSE
49 
50 // simple parallel quadtree sort
51 //#define OGDF_FME_PARALLEL_QUADTREE_SORT
52 
53 // use SSE for direct interaction (this is slower than the normal direct computation)
54 //#define OGDF_FME_KERNEL_USE_SSE_DIRECT
55 
56 inline void OGDF_FME_Print_Config()
57 {
58 #ifdef OGDF_FME_KERNEL_USE_SSE
59  std::cout << "OGDF_FME_KERNEL_USE_SSE" << std::endl;
60 #endif
61 #ifdef OGDF_FME_PARALLEL_QUADTREE_SORT
62  std::cout << "OGDF_FME_PARALLEL_QUADTREE_SORT" << std::endl;
63 #endif
64 #ifdef OGDF_FME_KERNEL_USE_SSE_DIRECT
65  std::cout << "OGDF_FME_KERNEL_USE_SSE_DIRECT" << std::endl;
66 #endif
67 }
68 
69 using MortonNR = uint64_t;
70 using CoordInt = uint32_t;
71 
72 template<typename T>
73 inline bool is_align_16(T* ptr)
74 {
75  return !(((size_t)(void*)ptr) & 0x0F);
76 }
77 
78 template<typename T>
79 inline T* align_16_prev_ptr(T* t)
80 {
81  return (T*)(((size_t)((void*)t))&~ 0x0F);
82 }
83 
84 template<typename T>
85 inline T* align_16_next_ptr(T* t)
86 {
87  return (T*)((((size_t)((void*)t)) + 15)&~ 0x0F);
88 }
89 
90 #ifdef OGDF_SYSTEM_UNIX
91 inline timeval GetDiffTime(timeval _then, double& dtime)
92 {
93  timeval then = (timeval) _then;
94  timeval now;
95  gettimeofday(&now, nullptr);
96  timeval diff;
97 
98  diff.tv_sec = now.tv_sec - then.tv_sec;
99  diff.tv_usec = now.tv_usec - then.tv_usec;
100  while(diff.tv_usec < 0)
101  {
102  diff.tv_sec--;
103  diff.tv_usec = 1000000 + now.tv_usec - then.tv_usec;
104  }
105 
106  dtime = (double) diff.tv_sec;
107  dtime += (double) diff.tv_usec / 1e6;
108 
109  return (timeval) now;
110 }
111 #endif
112 
113 inline void printProfiledTime(double t, const char* text) { std::cout << t <<"s\t" << text << std::endl; }
114 inline void printProfiledTime(double t, double sum, const char* text) { std::cout << t <<"s\t" << text << "\t" << (t / sum)*100.0 <<"%"<< std::endl; }
115 
117 #define OGDF_MALLOC_16(s) System::alignedMemoryAlloc16((s))
118 
120 #define OGDF_FREE_16(ptr) System::alignedMemoryFree((ptr))
121 
123 template<typename MNR_T, typename C_T>
124 inline MNR_T mortonNumber(C_T ix, C_T iy)
125 {
126  MNR_T x = (MNR_T)ix;
127  MNR_T y = (MNR_T)iy;
128  // bit length of the result
129  const unsigned int BIT_LENGTH = static_cast<unsigned int>(sizeof(MNR_T)) << 3;
130  // set all bits
131  MNR_T mask = 0x0;
132  mask = ~mask;
133 
134  for (unsigned int i = (BIT_LENGTH >> 1);i>0; i = i >> 1) {
135  // increase frequency
136  mask = mask ^ (mask << i);
137  x = (x | (x << i)) & mask;
138  y = (y | (y << i)) & mask;
139  }
140  return x | (y << 1);
141 }
142 
143 
145 template<typename MNR_T, typename C_T>
146 inline void mortonNumberInv(MNR_T mnr, C_T& x, C_T& y)
147 {
148  // bit length of the coordinates
149  unsigned int BIT_LENGTH = static_cast<unsigned int>(sizeof(C_T)) << 3;
150  // set least significant bit
151  MNR_T mask = 0x1;
152  // set coords to zero
153  x = y = 0;
154  for (unsigned int i=0; i < BIT_LENGTH; i++)
155  {
156  x = (C_T)(x | (mnr & mask));
157  mnr = mnr >> 1;
158  y = (C_T)(y | (mnr & mask));
159  mask = mask << 1;
160  }
161 }
162 
164 template<typename T>
165 inline uint32_t mostSignificantBit(T n)
166 {
167  uint32_t BIT_LENGTH = static_cast<uint32_t>(sizeof(T)) << 3;
168  T mask = 0x1;
169  mask = mask << (BIT_LENGTH - 1);
170  for (uint32_t i = 0; i < BIT_LENGTH; i++)
171  {
172  if (mask & n)
173  return i;
174  mask = mask >> 1;
175  }
176  return BIT_LENGTH;
177 }
178 
180 inline uint32_t prevPowerOfTwo(uint32_t n)
181 {
182  uint32_t msb = 32 - mostSignificantBit(n);
183  return 0x1 << (msb - 1);
184 }
185 
188 {
189 public:
191  explicit RandomNodeSet(const Graph& G) : m_graph(G) { allocate(); }
192 
195 
197  node chooseNode() const
198  {
199  int i = m_numNodesChoosen + ogdf::randomNumber(0,nodesLeft()-1);//(int)((double)nodesLeft()*rand()/(RAND_MAX+1.0));
200  return m_array[i];
201  }
202 
204  void removeNode(node v)
205  {
206  int i = m_nodeIndex[v];
207  int j = m_numNodesChoosen;
208  node w = m_array[j];
209  std::swap(m_array[i], m_array[j]);
210  m_nodeIndex[w] = i;
211  m_nodeIndex[v] = j;
213  }
214 
215  bool isAvailable(node v) const { return m_nodeIndex[v] >= m_numNodesChoosen; }
216 
218  int nodesLeft() const { return m_numNodes - m_numNodesChoosen; }
219 
220 private:
221  void allocate()
222  {
226  m_numNodesChoosen = 0;
227  int i = 0;
228  for(node v : m_graph.nodes)
229  {
230  m_array[i] = v;
231  m_nodeIndex[v] = i;
232  i++;
233  }
234  }
235 
236  void deallocate()
237  {
238  delete[] m_array;
239  }
240 
242  const Graph& m_graph;
243 
246 
249 
252 
255 };
256 
257 inline void gridGraph(Graph& G, int n, int m)
258 {
259  G.clear();
260  node v;
261  node* topRow = new node[m];
262  topRow[0] = G.newNode();
263  for (int j=1; j<m; j++)
264  {
265  topRow[j] = G.newNode();
266  G.newEdge(topRow[j-1], topRow[j]);
267  }
268  for (int i=1; i<n; i++)
269  {
270  v = G.newNode();
271  G.newEdge(topRow[0], v);
272  topRow[0] = v;
273  for (int j=1; j<m; j++)
274  {
275  v = G.newNode();
276  G.newEdge(topRow[j-1], v);
277  G.newEdge(topRow[j], v);
278  topRow[j] = v;
279  }
280  }
281  delete[] topRow;
282 }
283 
284 inline void randomGridGraph(Graph& G, int n, int m, double missinNodesPercentage = 0.03)
285 {
286  gridGraph(G, n, m);
287  int numberOfNodesToDelete = (int)((double)G.numberOfNodes() * missinNodesPercentage);
288 
289  RandomNodeSet rndSet(G);
290  for(int i=0; i<numberOfNodesToDelete;i++)
291  {
292  node v = rndSet.chooseNode();
293  rndSet.removeNode(v);
294  G.delNode(v);
295  }
296 }
297 
299 template<class TYP>
300 class BinCoeff
301 {
302 public:
303  explicit BinCoeff(unsigned int n) : m_max_n(n) { init_array(); }
304 
306 
308  void init_array()
309  {
310  using ptr = TYP*;
311  unsigned int i,j;
312  m_binCoeffs = new ptr[m_max_n+1];
313  for(i = 0;i<= m_max_n ;i++)
314  {
315  m_binCoeffs[i]= new TYP[i+1];
316  }
317 
318  //Pascalsches Dreieck
319  for (i = 0; i <= m_max_n;i++)
320  {
321  m_binCoeffs[i][0] = m_binCoeffs[i][i] = 1;
322  }
323 
324  for (i = 2; i <= m_max_n; i ++)
325  {
326  for (j = 1; j < i; j++)
327  {
328  m_binCoeffs[i][j] = m_binCoeffs[i-1][j-1]+m_binCoeffs[i-1][j];
329  }
330  }
331  }
332 
334  void free_array()
335  {
336  unsigned int i;
337  for(i = 0;i<= m_max_n;i++)
338  {
339  delete[] m_binCoeffs[i];
340  }
341  delete[] m_binCoeffs;
342  }
343 
344  //Returns n over k.
345  inline TYP value(unsigned int n, unsigned int k) const
346  {
347  return m_binCoeffs[n][k];
348  }
349 
350 private:
351  unsigned int m_max_n;
352 
354  TYP** m_binCoeffs;
355 };
356 
357 
358 // nothing
359 struct EmptyArgType {};
360 
361 //
362 // Function Invoker for 8 args
363 //
364 template<typename FunctionType,
365  typename ArgType1 = EmptyArgType,
366  typename ArgType2 = EmptyArgType,
367  typename ArgType3 = EmptyArgType,
368  typename ArgType4 = EmptyArgType,
369  typename ArgType5 = EmptyArgType,
370  typename ArgType6 = EmptyArgType,
371  typename ArgType7 = EmptyArgType,
372  typename ArgType8 = EmptyArgType>
374 {
375  FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7, ArgType8 _arg8) :
376  function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3), arg4(_arg4), arg5(_arg5), arg6(_arg6), arg7(_arg7), arg8(_arg8) { }
377 
378  inline void operator()() { function(arg1, arg2, arg3, arg4, arg5, arg6, arg7, arg8); }
379 
380  FunctionType function;
381  ArgType1 arg1;
382  ArgType2 arg2;
383  ArgType3 arg3;
384  ArgType4 arg4;
385  ArgType5 arg5;
386  ArgType6 arg6;
387  ArgType7 arg7;
388  ArgType8 arg8;
389 };
390 
391 
392 //
393 // Function Invoker for 7 args
394 //
395 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5, typename ArgType6, typename ArgType7>
396 struct FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType>
397 {
398  FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7) :
399  function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3), arg4(_arg4), arg5(_arg5), arg6(_arg6), arg7(_arg7) { }
400 
401  inline void operator()() { function(arg1, arg2, arg3, arg4, arg5, arg6, arg7); }
402 
403  FunctionType function;
404  ArgType1 arg1;
405  ArgType2 arg2;
406  ArgType3 arg3;
407  ArgType4 arg4;
408  ArgType5 arg5;
409  ArgType6 arg6;
410  ArgType7 arg7;
411 };
412 
413 //
414 // Function Invoker for 6 args
415 //
416 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5, typename ArgType6>
417 struct FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, EmptyArgType, EmptyArgType>
418 {
419  FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6) :
420  function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3), arg4(_arg4), arg5(_arg5), arg6(_arg6) { }
421 
422  inline void operator()() { function(arg1, arg2, arg3, arg4, arg5, arg6); }
423 
424  FunctionType function;
425  ArgType1 arg1;
426  ArgType2 arg2;
427  ArgType3 arg3;
428  ArgType4 arg4;
429  ArgType5 arg5;
430  ArgType6 arg6;
431 };
432 
433 //
434 // Function Invoker for 5 args
435 //
436 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5>
437 struct FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, EmptyArgType, EmptyArgType, EmptyArgType>
438 {
439  FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5) :
440  function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3), arg4(_arg4), arg5(_arg5) { }
441 
442  inline void operator()() { function(arg1, arg2, arg3, arg4, arg5); }
443 
444  FunctionType function;
445  ArgType1 arg1;
446  ArgType2 arg2;
447  ArgType3 arg3;
448  ArgType4 arg4;
449  ArgType5 arg5;
450 };
451 
452 //
453 // Function Invoker for 4 args
454 //
455 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4>
456 struct FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType>
457 {
458  FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4) :
459  function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3), arg4(_arg4) { }
460 
461  inline void operator()() { function(arg1, arg2, arg3, arg4); }
462 
463  FunctionType function;
464  ArgType1 arg1;
465  ArgType2 arg2;
466  ArgType3 arg3;
467  ArgType4 arg4;
468 };
469 
470 //
471 // Function Invoker for 3 args
472 //
473 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3>
474 struct FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType>
475 {
476  FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3) :
477  function(f), arg1(_arg1), arg2(_arg2), arg3(_arg3) { }
478 
479  inline void operator()() { function(arg1, arg2, arg3); }
480 
481  FunctionType function;
482  ArgType1 arg1;
483  ArgType2 arg2;
484  ArgType3 arg3;
485 };
486 
487 //
488 // Function Invoker for 2 args
489 //
490 template<typename FunctionType, typename ArgType1, typename ArgType2>
492 {
493  FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2) :
494  function(f), arg1(_arg1), arg2(_arg2) { }
495 
496  inline void operator()() { function(arg1, arg2); }
497 
498  FunctionType function;
499  ArgType1 arg1;
500  ArgType2 arg2;
501 };
502 
503 //
504 // Function Invoker for 1 args
505 //
506 template<typename FunctionType, typename ArgType1>
508 {
509  FuncInvoker(FunctionType f, ArgType1 _arg1) :
510  function(f), arg1(_arg1) { }
511 
512  inline void operator()() { function(arg1); }
513 
514  FunctionType function;
515  ArgType1 arg1;
516 };
517 
518 //
519 // Function Invoker for 0 args
520 //
521 template<typename FunctionType>
523 {
524  FuncInvoker(FunctionType f) :
525  function(f) { }
526 
527  inline void operator()() { function(); }
528 
529  FunctionType function;
530 };
531 
532 
533 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5, typename ArgType6, typename ArgType7, typename ArgType8>
535 createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7, ArgType8 _arg8)
536 {
537  return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, ArgType8>(func, _arg1, _arg2, _arg3, _arg4, _arg5, _arg6, _arg7, _arg8);
538 }
539 
540 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5, typename ArgType6, typename ArgType7, typename ArgType8>
541 FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, ArgType8>
542 createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7)
543 {
545 }
546 
547 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5, typename ArgType6>
548 FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6>
549 createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6)
550 {
551  return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6>(func, _arg1, _arg2, _arg3, _arg4, _arg5, _arg6);
552 }
553 
554 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4, typename ArgType5>
555 FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5>
556 createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5)
557 {
558  return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5>(func, _arg1, _arg2, _arg3, _arg4, _arg5);
559 }
560 
561 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3, typename ArgType4>
562 FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4>
563 createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4)
564 {
565  return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3, ArgType4>(func, _arg1, _arg2, _arg3, _arg4);
566 }
567 
568 template<typename FunctionType, typename ArgType1, typename ArgType2, typename ArgType3>
569 FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3>
570 createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3)
571 {
572  return FuncInvoker<FunctionType, ArgType1, ArgType2, ArgType3>(func, _arg1, _arg2, _arg3);
573 }
574 
575 template<typename FunctionType, typename ArgType1, typename ArgType2>
576 FuncInvoker<FunctionType, ArgType1, ArgType2>
577 createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2)
578 {
579  return FuncInvoker<FunctionType, ArgType1, ArgType2>(func, _arg1, _arg2);
580 }
581 
582 template<typename FunctionType, typename ArgType1>
583 FuncInvoker<FunctionType, ArgType1>
584 createFuncInvoker(FunctionType func, ArgType1 _arg1)
585 {
586  return FuncInvoker<FunctionType, ArgType1>(func, _arg1);
587 }
588 
589 template<typename FunctionType>
590 FuncInvoker<FunctionType>
591 createFuncInvoker(FunctionType func)
592 {
593  return FuncInvoker<FunctionType>(func);
594 }
595 
596 }
597 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::fast_multipole_embedder::RandomNodeSet::isAvailable
bool isAvailable(node v) const
Definition: FastUtils.h:215
GraphAttributes.h
Declaration of class GraphAttributes which extends a Graph by additional attributes.
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::FuncInvoker
FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4)
Definition: FastUtils.h:458
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::operator()
void operator()()
Definition: FastUtils.h:496
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, EmptyArgType, EmptyArgType >::arg5
ArgType5 arg5
Definition: FastUtils.h:429
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::arg2
ArgType2 arg2
Definition: FastUtils.h:465
ogdf::fast_multipole_embedder::gridGraph
void gridGraph(Graph &G, int n, int m)
Definition: FastUtils.h:257
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, EmptyArgType, EmptyArgType, EmptyArgType >::arg1
ArgType1 arg1
Definition: FastUtils.h:445
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::operator()
void operator()()
Definition: FastUtils.h:461
ogdf::fast_multipole_embedder::RandomNodeSet::nodesLeft
int nodesLeft() const
number of nodes available
Definition: FastUtils.h:218
ogdf::fast_multipole_embedder::BinCoeff::BinCoeff
BinCoeff(unsigned int n)
Definition: FastUtils.h:303
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, EmptyArgType, EmptyArgType >::arg3
ArgType3 arg3
Definition: FastUtils.h:427
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, EmptyArgType, EmptyArgType, EmptyArgType >::arg2
ArgType2 arg2
Definition: FastUtils.h:446
ogdf::fast_multipole_embedder::RandomNodeSet::removeNode
void removeNode(node v)
removes a node from available nodes (assumes v is available) in O(1)
Definition: FastUtils.h:204
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::arg2
ArgType2 arg2
Definition: FastUtils.h:500
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::arg1
ArgType1 arg1
Definition: FastUtils.h:515
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::FuncInvoker
FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3)
Definition: FastUtils.h:476
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::arg1
ArgType1 arg1
Definition: FastUtils.h:464
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, EmptyArgType, EmptyArgType >::FuncInvoker
FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6)
Definition: FastUtils.h:419
ogdf::fast_multipole_embedder::RandomNodeSet::allocate
void allocate()
Definition: FastUtils.h:221
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType >
Definition: FastUtils.h:396
ogdf::fast_multipole_embedder::FuncInvoker
Definition: FastUtils.h:373
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::FuncInvoker
FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2)
Definition: FastUtils.h:493
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, EmptyArgType, EmptyArgType, EmptyArgType >::operator()
void operator()()
Definition: FastUtils.h:442
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType >::arg1
ArgType1 arg1
Definition: FastUtils.h:404
ogdf::fast_multipole_embedder::printProfiledTime
void printProfiledTime(double t, const char *text)
Definition: FastUtils.h:113
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, EmptyArgType, EmptyArgType >::arg2
ArgType2 arg2
Definition: FastUtils.h:426
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, EmptyArgType, EmptyArgType >::arg6
ArgType6 arg6
Definition: FastUtils.h:430
ogdf::fast_multipole_embedder::FuncInvoker::arg3
ArgType3 arg3
Definition: FastUtils.h:383
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType >::arg6
ArgType6 arg6
Definition: FastUtils.h:409
ogdf::fast_multipole_embedder::FuncInvoker::arg1
ArgType1 arg1
Definition: FastUtils.h:381
ogdf::NodeArray< int >
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::FuncInvoker
FuncInvoker(FunctionType f)
Definition: FastUtils.h:524
ogdf::fast_multipole_embedder::FuncInvoker::arg8
ArgType8 arg8
Definition: FastUtils.h:388
ogdf::fast_multipole_embedder::CoordInt
uint32_t CoordInt
Definition: FastUtils.h:70
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, EmptyArgType, EmptyArgType, EmptyArgType >::FuncInvoker
FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5)
Definition: FastUtils.h:439
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, EmptyArgType, EmptyArgType >::operator()
void operator()()
Definition: FastUtils.h:422
ogdf::fast_multipole_embedder::RandomNodeSet::m_nodeIndex
NodeArray< int > m_nodeIndex
the index in the array of the nodes
Definition: FastUtils.h:248
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType >::arg2
ArgType2 arg2
Definition: FastUtils.h:405
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType >::FuncInvoker
FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7)
Definition: FastUtils.h:398
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType >::operator()
void operator()()
Definition: FastUtils.h:401
ogdf::Graph::nodes
internal::GraphObjectContainer< NodeElement > nodes
The container containing all node objects.
Definition: Graph_d.h:568
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, EmptyArgType, EmptyArgType >::arg1
ArgType1 arg1
Definition: FastUtils.h:425
ogdf::fast_multipole_embedder::RandomNodeSet::m_graph
const Graph & m_graph
the graph
Definition: FastUtils.h:242
ogdf::fast_multipole_embedder::prevPowerOfTwo
uint32_t prevPowerOfTwo(uint32_t n)
returns the prev power of two
Definition: FastUtils.h:180
ogdf::fast_multipole_embedder::MortonNR
uint64_t MortonNR
Definition: FastUtils.h:69
ogdf::fast_multipole_embedder::RandomNodeSet::m_array
node * m_array
the set of all nodes (at the end the available nodes)
Definition: FastUtils.h:245
ogdf::Graph::numberOfNodes
int numberOfNodes() const
Returns the number of nodes in the graph.
Definition: Graph_d.h:601
ogdf::fast_multipole_embedder::RandomNodeSet::~RandomNodeSet
~RandomNodeSet()
destructor
Definition: FastUtils.h:194
ogdf::fast_multipole_embedder::OGDF_FME_Print_Config
void OGDF_FME_Print_Config()
Definition: FastUtils.h:56
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, EmptyArgType, EmptyArgType, EmptyArgType >::arg3
ArgType3 arg3
Definition: FastUtils.h:447
ogdf::fast_multipole_embedder::mortonNumber
MNR_T mortonNumber(C_T ix, C_T iy)
common template for bit-interleaving to compute the morton number assumes sizeOf(MNR_T) = 2*sizeOf(C_...
Definition: FastUtils.h:124
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::operator()
void operator()()
Definition: FastUtils.h:479
ogdf::fast_multipole_embedder::FuncInvoker::arg6
ArgType6 arg6
Definition: FastUtils.h:386
ogdf::fast_multipole_embedder::BinCoeff::~BinCoeff
~BinCoeff()
Definition: FastUtils.h:305
ogdf::fast_multipole_embedder::RandomNodeSet::m_numNodes
int m_numNodes
total num nodes
Definition: FastUtils.h:251
ogdf::Graph
Data type for general directed graphs (adjacency list representation).
Definition: Graph_d.h:495
ogdf::fast_multipole_embedder::createFuncInvoker
FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, ArgType8 > createFuncInvoker(FunctionType func, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7, ArgType8 _arg8)
Definition: FastUtils.h:535
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::arg1
ArgType1 arg1
Definition: FastUtils.h:482
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::FuncInvoker
FuncInvoker(FunctionType f, ArgType1 _arg1)
Definition: FastUtils.h:509
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, EmptyArgType, EmptyArgType, EmptyArgType >::arg5
ArgType5 arg5
Definition: FastUtils.h:449
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::arg4
ArgType4 arg4
Definition: FastUtils.h:467
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType >::arg5
ArgType5 arg5
Definition: FastUtils.h:408
ogdf::fast_multipole_embedder::mostSignificantBit
uint32_t mostSignificantBit(T n)
returns the index of the most signficant bit set. 0 = most signif, bitlength-1 = least signif
Definition: FastUtils.h:165
ogdf::fast_multipole_embedder::FuncInvoker::FuncInvoker
FuncInvoker(FunctionType f, ArgType1 _arg1, ArgType2 _arg2, ArgType3 _arg3, ArgType4 _arg4, ArgType5 _arg5, ArgType6 _arg6, ArgType7 _arg7, ArgType8 _arg8)
Definition: FastUtils.h:375
ogdf::fast_multipole_embedder::RandomNodeSet::deallocate
void deallocate()
Definition: FastUtils.h:236
ogdf::fast_multipole_embedder::BinCoeff::free_array
void free_array()
Free space for BK.
Definition: FastUtils.h:334
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::arg1
ArgType1 arg1
Definition: FastUtils.h:499
ogdf::fast_multipole_embedder::RandomNodeSet::RandomNodeSet
RandomNodeSet(const Graph &G)
init the random node set with the given graph. takes O(n)
Definition: FastUtils.h:191
ogdf::Math::sum
Container::value_type sum(const Container &values)
Returns the sum of an iterable container of given values.
Definition: Math.h:245
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::operator()
void operator()()
Definition: FastUtils.h:527
ogdf::fast_multipole_embedder::FuncInvoker::arg2
ArgType2 arg2
Definition: FastUtils.h:382
ogdf::fast_multipole_embedder::is_align_16
bool is_align_16(T *ptr)
Definition: FastUtils.h:73
ogdf::fast_multipole_embedder::RandomNodeSet::chooseNode
node chooseNode() const
chooses a node from the available nodes in O(1)
Definition: FastUtils.h:197
ogdf::fast_multipole_embedder::FuncInvoker::arg7
ArgType7 arg7
Definition: FastUtils.h:387
ogdf::fast_multipole_embedder::EmptyArgType
Definition: FastUtils.h:359
ogdf::fast_multipole_embedder::BinCoeff::m_binCoeffs
TYP ** m_binCoeffs
holds the binominal coefficients
Definition: FastUtils.h:354
ogdf::fast_multipole_embedder::FuncInvoker::function
FunctionType function
Definition: FastUtils.h:380
ogdf::fast_multipole_embedder::BinCoeff::init_array
void init_array()
Init BK -matrix for values n, k in 0 to t.
Definition: FastUtils.h:308
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::arg3
ArgType3 arg3
Definition: FastUtils.h:484
ogdf::NodeArray::init
void init()
Reinitializes the array. Associates the array with no graph.
Definition: NodeArray.h:255
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::arg2
ArgType2 arg2
Definition: FastUtils.h:483
ogdf::fast_multipole_embedder::align_16_prev_ptr
T * align_16_prev_ptr(T *t)
Definition: FastUtils.h:79
ogdf::fast_multipole_embedder::BinCoeff
binomial coeffs from Hachuls FMMM
Definition: FastUtils.h:300
intrinsics.h
Include of header files for SSE-intrinsics.
ogdf::fast_multipole_embedder::RandomNodeSet::m_numNodesChoosen
int m_numNodesChoosen
num available nodes
Definition: FastUtils.h:254
ogdf::fast_multipole_embedder::FuncInvoker::operator()
void operator()()
Definition: FastUtils.h:378
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType >::arg3
ArgType3 arg3
Definition: FastUtils.h:406
ogdf::fast_multipole_embedder::mortonNumberInv
void mortonNumberInv(MNR_T mnr, C_T &x, C_T &y)
common template for extracting the coordinates from a morton number assumes sizeOf(MNR_T) = 2*sizeOf(...
Definition: FastUtils.h:146
ogdf::fast_multipole_embedder::align_16_next_ptr
T * align_16_next_ptr(T *t)
Definition: FastUtils.h:85
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, EmptyArgType, EmptyArgType >::arg4
ArgType4 arg4
Definition: FastUtils.h:428
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::operator()
void operator()()
Definition: FastUtils.h:512
ogdf::randomNumber
int randomNumber(int low, int high)
Returns random integer between low and high (including).
ogdf::fast_multipole_embedder::randomGridGraph
void randomGridGraph(Graph &G, int n, int m, double missinNodesPercentage=0.03)
Definition: FastUtils.h:284
ogdf::fast_multipole_embedder::BinCoeff::value
TYP value(unsigned int n, unsigned int k) const
Definition: FastUtils.h:345
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType >::arg4
ArgType4 arg4
Definition: FastUtils.h:407
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, ArgType6, ArgType7, EmptyArgType >::arg7
ArgType7 arg7
Definition: FastUtils.h:410
ogdf::fast_multipole_embedder::BinCoeff::m_max_n
unsigned int m_max_n
Definition: FastUtils.h:351
ogdf::NodeElement
Class for the representation of nodes.
Definition: Graph_d.h:169
ogdf::fast_multipole_embedder::FuncInvoker::arg5
ArgType5 arg5
Definition: FastUtils.h:385
ogdf::fast_multipole_embedder::FuncInvoker::arg4
ArgType4 arg4
Definition: FastUtils.h:384
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, EmptyArgType, EmptyArgType, EmptyArgType, EmptyArgType >::arg3
ArgType3 arg3
Definition: FastUtils.h:466
ogdf::fast_multipole_embedder::FuncInvoker< FunctionType, ArgType1, ArgType2, ArgType3, ArgType4, ArgType5, EmptyArgType, EmptyArgType, EmptyArgType >::arg4
ArgType4 arg4
Definition: FastUtils.h:448
ogdf::fast_multipole_embedder::RandomNodeSet
utility class to select multiple nodes randomly
Definition: FastUtils.h:187