MFEM  v4.5.1
Finite element discretization library
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Pages
gecko.hpp
Go to the documentation of this file.
1 // Copyright (c) 2010-2022, Lawrence Livermore National Security, LLC. Produced
2 // at the Lawrence Livermore National Laboratory. All Rights reserved. See files
3 // LICENSE and NOTICE for details. LLNL-CODE-806117.
4 //
5 // This file is part of the MFEM library. For more information and source code
6 // availability visit https://mfem.org.
7 //
8 // MFEM is free software; you can redistribute it and/or modify it under the
9 // terms of the BSD-3 license. We welcome feedback and contributions, see file
10 // CONTRIBUTING.md for details.
11 
12 #ifndef MFEM_GECKO_HPP
13 #define MFEM_GECKO_HPP
14 
15 // This file collects the sources of the Gecko library as a single module.
16 // The original library can be found at https://github.com/LLNL/gecko
17 // Used here with permission.
18 
19 // ------------------------------------------------------------------------------
20 
21 // BSD 3-Clause License
22 //
23 // Copyright (c) 2019-2022, Lawrence Livermore National Security, LLC
24 // All rights reserved.
25 //
26 // Redistribution and use in source and binary forms, with or without
27 // modification, are permitted provided that the following conditions are met:
28 //
29 // * Redistributions of source code must retain the above copyright notice, this
30 // list of conditions and the following disclaimer.
31 //
32 // * Redistributions in binary form must reproduce the above copyright notice,
33 // this list of conditions and the following disclaimer in the documentation
34 // and/or other materials provided with the distribution.
35 //
36 // * Neither the name of the copyright holder nor the names of its
37 // contributors may be used to endorse or promote products derived from
38 // this software without specific prior written permission.
39 //
40 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
41 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
42 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
43 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
44 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
45 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
46 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
47 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
48 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
49 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
50 
51 // ------------------------------------------------------------------------------
52 
53 // Copyright (c) 2019-2022, Lawrence Livermore National Security, LLC and other
54 // gecko project contributors. See the above license for details.
55 // SPDX-License-Identifier: BSD-3-Clause
56 // LLNL-CODE-800597
57 
58 /* ------------------------------------------------------------------------------
59 
60 Gecko
61 =====
62 
63 Gecko is a C++ library for solving graph linear arrangement problems. Gecko
64 orders graph nodes, representing data elements, connected by undirected edges,
65 representing affinity relations, with the goal of minimizing a chosen
66 functional of edge length. Gecko was primarily designed to minimize the
67 product of edge lengths but can also be used to reduce bandwidth (maximum
68 edge length) and 1-sum (sum of edge lengths), among others.
69 Minimum-edge-product orderings generalize space-filling curve orderings to
70 geometryless graphs and find applications in data locality optimization,
71 graph partitioning, and dimensionality reduction.
72 
73 
74 Author
75 ------
76 
77 Gecko was written by [Peter Lindstrom](https://people.llnl.gov/pl) at
78 Lawrence Livermore National Laboratory.
79 
80 
81 Algorithm
82 =========
83 
84 Gecko orders the nodes of an undirected and optionally weighted graph in an
85 effort to place nodes connected by an edge in consecutive positions in the
86 linear ordering (aka. *layout*). Such orderings promote good data locality,
87 e.g., to improve cache utilization, but also find applications in graph
88 partitioning and dimensionality reduction.
89 
90 The gecko ordering method is inspired by algebraic multigrid methods, and
91 uses V-cycles to coarsen, optimize, and refine the graph layout.
92 The graph constitutes an abstract representation of the relationship
93 between elements in a data set, e.g., a graph node may represent a
94 vertex or a cell in a mesh, a pixel in an image, a node in a binary
95 search tree, an element in a sparse matrix, etc. The graph edges
96 represent node affinities, or a desire that adjacent nodes be stored
97 close together on linear storage (e.g., disk or main memory). Such a
98 data layout is likely to improve cache utilization in block-based
99 caches common on today's computer architectures. For instance, the
100 edges may connect adjacent pixels in an image, as many image
101 processing operations involve accessing local neighborhoods. The
102 resulting node layouts are "cache-oblivious" in the sense that no
103 particular knowledge of the cache parameters (number and size of
104 blocks, associativity, replacement policy, etc.) are accounted for.
105 Rather, the expectation is that the layouts will provide good
106 locality across all levels of cache. Note that the ordering method
107 accepts any undirected graph, whether it represent a structured or
108 unstructured data set, and is also oblivious of any geometric
109 structure inherent in the data set.
110 
111 The optimization algorithm attempts to order the nodes of the graph
112 so as to minimize the geometric mean edge length, or equivalently
113 the product
114 
115  product |p(i) - p(j)|^w(i, j)
116 
117 or weighted sum
118 
119  sum w(i, j) log(|p(i) - p(j)|)
120 
121 where *i* and *j* are nodes joined by an edge, *w*(*i*, *j*) is a positive
122 edge weight (equal to one unless otherwise specified), *p*(*i*) is
123 the integer position of node *i* in the linear layout of the graph
124 (with *p*(*i*) = *p*(*j*) if and only if *i* = *j*), and where the product
125 or sum is over all edges of the graph.
126 
127 The algorithm is described in further detail in the paper
128 
129 * Peter Lindstrom
130  The Minimum Edge Product Linear Ordering Problem
131  LLNL technical report LLNL-TR-496076, August 26, 2011.
132 
133 
134 Ordering Parameters
135 -------------------
136 
137 The `Graph::order()` function and the `gecko` command-line executable take a
138 number of parameters that govern the layout process. These parameters are
139 described below:
140 
141 * The **functional** is the objective being optimized and expresses the cost
142  of the graph layout in terms of some average of its edge lengths
143  |*p*(*i*) - *p*(*j*)|. The predefined functionals are
144  * `h` (harmonic mean)
145  * `g` (geometric mean)
146  * `s` (square mean root)
147  * `a` (arithmetic mean)
148  * `r` (root mean square)
149  * `m` (maximum)
150 
151  Note that the algorithm has not been well tuned or tested to optimize
152  functionals other than the geometric mean.
153 
154 * The number of **iterations** specifies the number of multigrid V-cycles
155  to perform. Usually a handful of cycles is sufficient. The default is
156  a single cycle.
157 
158 * The optimization **window** is the number of consecutive nodes optimized
159  concurrently using exhaustive search. The larger the window, the higher
160  the quality. Note that the running time increases exponentially with the
161  window size. Usually a window no larger than six nodes is sufficient.
162  The default is a window size of two nodes.
163 
164 * The **period** is the number of V-cycles to run between increments of the
165  window size. Usually it is beneficial to start with a small window to get
166  a rough layout, and to then increase the window size to fine-tune the
167  layout. The default is a period of one cycle.
168 
169 * The random **seed** allows injecting some randomness in the optimization
170  process. When the seed is nonzero, the nodes are randomly shuffled prior
171  to invoking the ordering algorithm, thereby affecting subsequent coarsening
172  and ordering decisions. In effect, this randomization allows different
173  directions to be explored in the combinatorial optimization space. Fixing
174  the seed allows for reproducibility, i.e., the same seed always leads to
175  the same layout. Since the global optimum is seldom (if ever) reached,
176  it often makes sense to run several instances of the algorithm, each with
177  a new random seed, and to pick the best layout found. In the gecko
178  executable, the current time is used as random seed if not specified.
179 
180 A reasonable parameter choice for good-quality layouts is:
181 
182 * iterations = 4
183 * window = 4
184 * period = 2
185 
186 */
187 
188 #include <algorithm>
189 #include <string>
190 #include <utility>
191 #include <vector>
192 #include <cmath>
193 #include <cfloat>
194 #include <limits>
195 
196 // ----- types.h ----------------------------------------------------------------
197 
198 #define GECKO_FLOAT_EPSILON std::numeric_limits<Float>::epsilon()
199 #define GECKO_FLOAT_MAX std::numeric_limits<Float>::max()
200 
201 namespace Gecko
202 {
203 
204 typedef unsigned int uint;
205 
206 // precision for node positions and computations
207 #if GECKO_WITH_DOUBLE_PRECISION
208 typedef double Float;
209 #else
210 typedef float Float;
211 #endif
212 }
213 
214 // ----- functional.h -----------------------------------------------------------
215 
216 namespace Gecko
217 {
218 
219 // abstract base class for weighted terms and sums
221 {
222 public:
223  WeightedValue(Float value, Float weight) : value(value), weight(weight) {}
226 };
227 
228 // weighted sum of terms
230 {
231 public:
233 };
234 
235 // abstract base class for ordering functionals
237 {
238 public:
239  virtual ~Functional() {}
240 
241  virtual WeightedSum sum(const WeightedSum& s, const WeightedValue& t) const
242  {
243  WeightedSum tot = s;
244  accumulate(tot, sum(t));
245  return tot;
246  }
247 
248  virtual WeightedSum sum(const WeightedSum& s, const WeightedSum& t) const
249  {
250  WeightedSum tot = s;
251  accumulate(tot, t);
252  return tot;
253  }
254 
255  // add weighted term to weighted sum
256  virtual void accumulate(WeightedSum& s, const WeightedValue& t) const
257  {
258  accumulate(s, sum(t));
259  }
260 
261  // add two weighted sums
262  virtual void accumulate(WeightedSum& s, const WeightedSum& t) const
263  {
264  s.value += t.value;
265  s.weight += t.weight;
266  }
267 
268  // is s potentially less than t?
269  virtual bool less(const WeightedSum& s, const WeightedSum& t) const
270  {
271  return s.value < t.value;
272  }
273 
274  // transform term into weighted sum
275  virtual WeightedSum sum(const WeightedValue& term) const = 0;
276 
277  // compute weighted mean from a weighted sum
278  virtual Float mean(const WeightedSum& sum) const = 0;
279 
280  // compute k'th iteration bond for edge of length l and weight w
281  virtual Float bond(Float w, Float l, uint k) const = 0;
282 
283  // compute position that minimizes weighted distance to a point set
284  virtual Float optimum(const std::vector<WeightedValue>& v) const = 0;
285 };
286 
287 // functionals with quasiconvex terms, e.g., p-means with p < 1.
289 {
290 protected:
291  Float optimum(const std::vector<WeightedValue>& v, Float lmin) const
292  {
293  // Compute the optimum as the node position that minimizes the
294  // functional. Any nodes coincident with each candidate position
295  // are excluded from the functional.
296  Float x = v[0].value;
297  Float min = GECKO_FLOAT_MAX;
298  switch (v.size())
299  {
300  case 1:
301  // Only one choice.
302  break;
303  case 2:
304  // Functional is the same for both nodes; pick node with
305  // larger weight.
306  if (v[1].weight > v[0].weight)
307  {
308  x = v[1].value;
309  }
310  break;
311  default:
312  for (std::vector<WeightedValue>::const_iterator p = v.begin(); p != v.end();
313  p++)
314  {
315  WeightedSum s;
316  for (std::vector<WeightedValue>::const_iterator q = v.begin(); q != v.end();
317  q++)
318  {
319  Float l = std::fabs(p->value - q->value);
320  if (l > lmin)
321  {
322  accumulate(s, WeightedValue(l, q->weight));
323  }
324  }
325  Float f = mean(s);
326  if (f < min)
327  {
328  min = f;
329  x = p->value;
330  }
331  }
332  break;
333  }
334  return x;
335  }
336 private:
337  using Functional::optimum; // silence overload vs. override warning
338 };
339 
340 // harmonic mean (p = -1)
342 {
343 public:
344  using Functional::sum;
345  bool less(const WeightedSum& s, const WeightedSum& t) const
346  {
347  // This is only a loose bound when s.weight < t.weight.
348  return s.value - s.weight > t.value - t.weight;
349  }
350  WeightedSum sum(const WeightedValue& term) const
351  {
352  return WeightedSum(term.weight / term.value, term.weight);
353  }
354  Float mean(const WeightedSum& sum) const
355  {
356  return sum.weight > 0 ? sum.weight / sum.value : 0;
357  }
358  Float bond(Float w, Float l, uint k) const
359  {
360  return w * std::pow(l, -Float(3) * Float(k) / Float(k + 1));
361  }
362  Float optimum(const std::vector<WeightedValue>& v) const
363  {
364  return FunctionalQuasiconvex::optimum(v, Float(0.5));
365  }
366 };
367 
368 // geometric mean (p = 0)
370 {
371 public:
372  using Functional::sum;
373  WeightedSum sum(const WeightedValue& term) const
374  {
375  return WeightedSum(term.weight * std::log(term.value), term.weight);
376  }
377  Float mean(const WeightedSum& sum) const
378  {
379  return sum.weight > 0 ? std::exp(sum.value / sum.weight) : 0;
380  }
381  Float bond(Float w, Float l, uint k) const
382  {
383  return w * std::pow(l, -Float(2) * Float(k) / Float(k + 1));
384  }
385  Float optimum(const std::vector<WeightedValue>& v) const
386  {
387  return FunctionalQuasiconvex::optimum(v, Float(0.5));
388  }
389 };
390 
391 // square mean root (p = 1/2)
393 {
394 public:
395  using Functional::sum;
396  WeightedSum sum(const WeightedValue& term) const
397  {
398  return WeightedSum(term.weight * std::sqrt(term.value), term.weight);
399  }
400  Float mean(const WeightedSum& sum) const
401  {
402  return sum.weight > 0 ? (sum.value / sum.weight) * (sum.value / sum.weight) : 0;
403  }
404  Float bond(Float w, Float l, uint k) const
405  {
406  return w * std::pow(l, -Float(1.5) * Float(k) / Float(k + 1));
407  }
408  Float optimum(const std::vector<WeightedValue>& v) const
409  {
410  return FunctionalQuasiconvex::optimum(v, Float(0.0));
411  }
412 };
413 
414 // arithmetic mean (p = 1)
416 {
417 public:
418  using Functional::sum;
419  WeightedSum sum(const WeightedValue& term) const
420  {
421  return WeightedSum(term.weight * term.value, term.weight);
422  }
423  Float mean(const WeightedSum& sum) const
424  {
425  return sum.weight > 0 ? sum.value / sum.weight : 0;
426  }
427  Float bond(Float w, Float l, uint k) const
428  {
429  return w * std::pow(l, -Float(1) * Float(k) / Float(k + 1));
430  }
431  Float optimum(const std::vector<WeightedValue>& v) const
432  {
433  // Compute the optimum as the weighted median. Since the median may
434  // not be unique, the largest interval [x, y] is computed and its
435  // centroid is chosen. The optimum must occur at a node, and hence
436  // we consider each node position pi at a time and the relative
437  // positions of the remaining nodes pj.
438  Float x = 0;
439  Float y = 0;
440  Float min = GECKO_FLOAT_MAX;
441  for (std::vector<WeightedValue>::const_iterator p = v.begin(); p != v.end();
442  p++)
443  {
444  // Compute f = |sum_{j:pj<pi} wj - sum_{j:pj>pi} wj|.
445  Float f = 0;
446  for (std::vector<WeightedValue>::const_iterator q = v.begin(); q != v.end();
447  q++)
448  if (q->value < p->value)
449  {
450  f += q->weight;
451  }
452  else if (q->value > p->value)
453  {
454  f -= q->weight;
455  }
456  f = std::fabs(f);
457  // Update interval if f is minimal.
458  if (f <= min)
459  {
460  if (f < min)
461  {
462  min = f;
463  x = y = p->value;
464  }
465  else
466  {
467  x = std::min(x, p->value);
468  y = std::max(y, p->value);
469  }
470  }
471  }
472  return (x + y) / 2;
473  }
474 };
475 
476 // root mean square (p = 2)
477 class FunctionalRMS : public Functional
478 {
479 public:
480  using Functional::sum;
481  WeightedSum sum(const WeightedValue& term) const
482  {
483  return WeightedSum(term.weight * term.value * term.value, term.weight);
484  }
485  Float mean(const WeightedSum& sum) const
486  {
487  return sum.weight > 0 ? std::sqrt(sum.value / sum.weight) : 0;
488  }
489  Float bond(Float w, Float, uint) const
490  {
491  return w;
492  }
493  Float optimum(const std::vector<WeightedValue>& v) const
494  {
495  // Compute the optimum as the weighted mean.
496  WeightedSum s;
497  for (std::vector<WeightedValue>::const_iterator p = v.begin(); p != v.end();
498  p++)
499  {
500  s.value += p->weight * p->value;
501  s.weight += p->weight;
502  }
503  return s.value / s.weight;
504  }
505 };
506 
507 // maximum (p = infinity)
509 {
510 public:
511  using Functional::sum;
513  WeightedSum sum(const WeightedValue& term) const
514  {
515  return WeightedSum(term.value, term.weight);
516  }
517  void accumulate(WeightedSum& s, const WeightedSum& t) const
518  {
519  s.value = std::max(s.value, t.value);
520  }
521  Float mean(const WeightedSum& sum) const
522  {
523  return sum.value;
524  }
526  {
527  return Float(1);
528  }
529  Float optimum(const std::vector<WeightedValue>& v) const
530  {
531  // Compute the optimum as the midrange.
532  Float min = v[0].value;
533  Float max = v[0].value;
534  for (std::vector<WeightedValue>::const_iterator p = v.begin() + 1; p != v.end();
535  p++)
536  {
537  if (p->value < min)
538  {
539  min = p->value;
540  }
541  else if (p->value > max)
542  {
543  max = p->value;
544  }
545  }
546  return (min + max) / 2;
547  }
548 };
549 
550 }
551 
552 // ----- progress.h -------------------------------------------------------------
553 
554 namespace Gecko
555 {
556 
557 class Graph;
558 
559 // Callbacks between iterations and phases.
560 class Progress
561 {
562 public:
563  virtual ~Progress() {}
564  virtual void beginorder(const Graph* /*graph*/, Float /*cost*/) const {}
565  virtual void endorder(const Graph* /*graph*/, Float /*cost*/) const {}
566  virtual void beginiter(const Graph* /*graph*/, uint /*iter*/, uint /*maxiter*/,
567  uint /*window*/) const {}
568  virtual void enditer(const Graph* /*graph*/, Float /*mincost*/,
569  Float /*cost*/) const {}
570  virtual void beginphase(const Graph* /*graph*/, std::string /*name*/) const {};
571  virtual void endphase(const Graph* /*graph*/, bool /*show*/) const {};
572  virtual bool quit() const { return false; }
573 };
574 
575 }
576 
577 // ----- graph.h ----------------------------------------------------------------
578 
579 namespace Gecko
580 {
581 
582 // Multilevel graph arc.
583 class Arc
584 {
585 public:
586  typedef uint Index;
587  typedef std::vector<Index>::const_iterator ConstPtr;
588  enum { null = 0 };
589 };
590 
591 // Multilevel graph node.
592 class Node
593 {
594 public:
595  typedef uint Index;
596  typedef std::vector<Node>::const_iterator ConstPtr;
597  enum { null = 0 };
598 
599  // comparator for sorting node indices
601  {
602  public:
603  Comparator(ConstPtr node_) : node(node_) {}
604  bool operator()(uint k, uint l) const { return node[k].pos < node[l].pos; }
605  private:
606  const ConstPtr node;
607  };
608 
609  // constructor
610  Node(Float pos = -1, Float length = 1, Arc::Index arc = Arc::null,
611  Node::Index parent = Node::null) : pos(pos), hlen(Float(0.5) * length),
612  arc(arc), parent(parent) {}
613 
614  Float pos; // start position at full resolution
615  Float hlen; // half of node length (number of full res nodes)
616  Arc::Index arc; // one past index of last incident arc
617  Node::Index parent; // parent in next coarser resolution
618 };
619 
620 // Multilevel graph.
621 class Graph
622 {
623 public:
624  // constructor of graph with given (initial) number of nodes
625  Graph(uint nodes = 0) : level(0), last_node(Node::null) { init(nodes); }
626 
627  // number of nodes and edges
628  uint nodes() const { return uint(node.size() - 1); }
629  uint edges() const { return uint((adj.size() - 1) / 2); }
630 
631  // insert node and return its index
633 
634  // outgoing arcs {begin, ..., end-1} originating from node i
635  Arc::Index node_begin(Node::Index i) const { return node[i - 1].arc; }
636  Arc::Index node_end(Node::Index i) const { return node[i].arc; }
637 
638  // node degree and neighbors
639  uint node_degree(Node::Index i) const { return node_end(i) - node_begin(i); }
640  std::vector<Node::Index> node_neighbors(Node::Index i) const;
641 
642  // insert directed edge (i, j)
644 
645  // remove arc or edge
646  bool remove_arc(Arc::Index a);
649 
650  // index of arc (i, j) or null if not present
652 
653  // arc source and target nodes and weight
655  Node::Index arc_target(Arc::Index a) const { return adj[a]; }
656  Float arc_weight(Arc::Index a) const { return weight[a]; }
657 
658  // reverse arc (j, i) of arc a = (i, j)
660 
661  // order graph
662  void order(Functional* functional, uint iterations = 1, uint window = 2,
663  uint period = 2, uint seed = 0, Progress* progress = 0);
664 
665  // optimal permutation found
666  const std::vector<Node::Index>& permutation() const { return perm; }
667 
668  // node of given rank in reordered graph (0 <= rank <= nodes() - 1)
669  Node::Index permutation(uint rank) const { return perm[rank]; }
670 
671  // position of node i in reordered graph (1 <= i <= nodes())
672  uint rank(Node::Index i) const { return static_cast<uint>(std::floor(node[i].pos)); }
673 
674  // cost of current layout
675  Float cost() const;
676 
677  // return first directed arc if one exists or null otherwise
678  Arc::Index directed() const;
679 
680 protected:
681  friend class Subgraph;
682  friend class Drawing;
683 
684  // constructor/destructor
685  Graph(uint nodes, uint level) : level(level), last_node(Node::null) { init(nodes); }
686 
687  // arc length
688  Float length(Node::Index i, Node::Index j) const { return std::fabs(node[i].pos - node[j].pos); }
690  {
691  Node::Index i = arc_source(a);
692  Node::Index j = arc_target(a);
693  return length(i, j);
694  }
695 
696  // coarsen graph
697  Graph* coarsen();
698 
699  // refine graph
700  void refine(const Graph* graph);
701 
702  // perform m sweeps of compatible or Gauss-Seidel relaxation
703  void relax(bool compatible, uint m = 1);
704 
705  // optimize using n-node window
706  void optimize(uint n);
707 
708  // place all nodes according to their positions
709  void place(bool sort = false);
710 
711  // place nodes {k, ..., k + n - 1} according to their positions
712  void place(bool sort, uint k, uint n);
713 
714  // perform V cycle using n-node window
715  void vcycle(uint n, uint work = 0);
716 
717  // randomly shuffle nodes
718  void shuffle(uint seed = 0);
719 
720  // recompute arc bonds for iteration i
721  void reweight(uint i);
722 
723  // compute cost
724  WeightedSum cost(const std::vector<Arc::Index>& subset, Float pos) const;
725 
726  // node attributes
727  bool persistent(Node::Index i) const { return node[i].parent != Node::null; }
728  bool placed(Node::Index i) const { return node[i].pos >= Float(0); }
729 
730  Functional* functional; // ordering functional
731  Progress* progress; // progress callbacks
732  std::vector<Node::Index> perm; // ordered list of indices to nodes
733  std::vector<Node> node; // statically ordered list of nodes
734  std::vector<Node::Index> adj; // statically ordered list of adjacent nodes
735  std::vector<Float> weight; // statically ordered list of arc weights
736  std::vector<Float> bond; // statically ordered list of coarsening weights
737 
738 private:
739  // initialize graph with given number of nodes
740  void init(uint nodes);
741 
742  // find optimal position of node i while fixing all other nodes
743  Float optimal(Node::Index i) const;
744 
745  // add contribution of fine arc to coarse graph
746  void update(Node::Index i, Node::Index j, Float w, Float b);
747 
748  // transfer contribution of fine arc a to coarse node p
749  void transfer(Graph* g, const std::vector<Float>& part, Node::Index p,
750  Arc::Index a, Float f = 1) const;
751 
752  // swap the positions of nodes
753  void swap(uint k, uint l);
754 
755  // random number generator
756  static uint random(uint seed = 0);
757 
758  uint level; // level of coarsening
759  Node::Index last_node; // last node with outgoing arcs
760 };
761 
762 }
763 
764 #endif // MFEM_GECKO_HPP
Node(Float pos=-1, Float length=1, Arc::Index arc=Arc::null, Node::Index parent=Node::null)
Definition: gecko.hpp:610
Node::Index permutation(uint rank) const
Definition: gecko.hpp:669
Float optimum(const std::vector< WeightedValue > &v) const
Definition: gecko.hpp:493
virtual Float optimum(const std::vector< WeightedValue > &v) const =0
Arc::Index node_begin(Node::Index i) const
Definition: gecko.hpp:635
virtual bool less(const WeightedSum &s, const WeightedSum &t) const
Definition: gecko.hpp:269
Float mean(const WeightedSum &sum) const
Definition: gecko.hpp:400
Arc::Index insert_arc(Node::Index i, Node::Index j, Float w=1, Float b=1)
Definition: gecko.cpp:679
std::vector< Float > bond
Definition: gecko.hpp:736
std::vector< Index >::const_iterator ConstPtr
Definition: gecko.hpp:587
Float mean(const WeightedSum &sum) const
Definition: gecko.hpp:354
Float mean(const WeightedSum &sum) const
Definition: gecko.hpp:521
Float optimum(const std::vector< WeightedValue > &v) const
Definition: gecko.hpp:529
std::vector< Node >::const_iterator ConstPtr
Definition: gecko.hpp:596
Graph * coarsen()
Definition: gecko.cpp:918
WeightedSum sum(const WeightedValue &term) const
Definition: gecko.hpp:419
Arc::Index arc
Definition: gecko.hpp:616
std::vector< Float > weight
Definition: gecko.hpp:735
unsigned int uint
Definition: gecko.hpp:204
Float bond(Float w, Float l, uint k) const
Definition: gecko.hpp:404
Float bond(Float, Float, uint) const
Definition: gecko.hpp:525
Float pos
Definition: gecko.hpp:614
virtual void beginiter(const Graph *, uint, uint, uint) const
Definition: gecko.hpp:566
WeightedSum sum(const WeightedValue &term) const
Definition: gecko.hpp:396
bool remove_arc(Arc::Index a)
Definition: gecko.cpp:699
void order(Functional *functional, uint iterations=1, uint window=2, uint period=2, uint seed=0, Progress *progress=0)
Definition: gecko.cpp:1232
std::vector< Node::Index > adj
Definition: gecko.hpp:734
Float arc_weight(Arc::Index a) const
Definition: gecko.hpp:656
friend class Drawing
Definition: gecko.hpp:682
Arc::Index node_end(Node::Index i) const
Definition: gecko.hpp:636
virtual void endorder(const Graph *, Float) const
Definition: gecko.hpp:565
Node::Index arc_source(Arc::Index a) const
Definition: gecko.cpp:749
Float optimum(const std::vector< WeightedValue > &v, Float lmin) const
Definition: gecko.hpp:291
Float bond(Float w, Float l, uint k) const
Definition: gecko.hpp:427
std::vector< Node::Index > node_neighbors(Node::Index i) const
Definition: gecko.cpp:667
void relax(bool compatible, uint m=1)
Definition: gecko.cpp:1102
Float mean(const WeightedSum &sum) const
Definition: gecko.hpp:377
WeightedValue(Float value, Float weight)
Definition: gecko.hpp:223
std::vector< Node > node
Definition: gecko.hpp:733
uint rank(Node::Index i) const
Definition: gecko.hpp:672
virtual WeightedSum sum(const WeightedSum &s, const WeightedValue &t) const
Definition: gecko.hpp:241
friend class Subgraph
Definition: gecko.hpp:681
virtual void enditer(const Graph *, Float, Float) const
Definition: gecko.hpp:568
uint Index
Definition: gecko.hpp:595
std::vector< Node::Index > perm
Definition: gecko.hpp:732
WeightedSum sum(const WeightedValue &term) const
Definition: gecko.hpp:481
bool placed(Node::Index i) const
Definition: gecko.hpp:728
WeightedSum sum(const WeightedValue &term) const
Definition: gecko.hpp:373
Float optimum(const std::vector< WeightedValue > &v) const
Definition: gecko.hpp:408
Graph(uint nodes=0)
Definition: gecko.hpp:625
double b
Definition: lissajous.cpp:42
Float hlen
Definition: gecko.hpp:615
Float cost() const
Definition: gecko.cpp:857
virtual void accumulate(WeightedSum &s, const WeightedValue &t) const
Definition: gecko.hpp:256
WeightedSum sum(const WeightedValue &term) const
Definition: gecko.hpp:350
virtual Float bond(Float w, Float l, uint k) const =0
void optimize(uint n)
Definition: gecko.cpp:1120
double Float
Definition: gecko.hpp:208
const std::vector< Node::Index > & permutation() const
Definition: gecko.hpp:666
WeightedSum(Float value=0, Float weight=0)
Definition: gecko.hpp:232
bool remove_edge(Node::Index i, Node::Index j)
Definition: gecko.cpp:725
Arc::Index directed() const
Definition: gecko.cpp:782
Node::Index parent
Definition: gecko.hpp:617
Comparator(ConstPtr node_)
Definition: gecko.hpp:603
Functional * functional
Definition: gecko.hpp:730
Float mean(const WeightedSum &sum) const
Definition: gecko.hpp:423
uint node_degree(Node::Index i) const
Definition: gecko.hpp:639
Float optimum(const std::vector< WeightedValue > &v) const
Definition: gecko.hpp:362
virtual ~Progress()
Definition: gecko.hpp:563
virtual Float mean(const WeightedSum &sum) const =0
virtual WeightedSum sum(const WeightedSum &s, const WeightedSum &t) const
Definition: gecko.hpp:248
Float length(Arc::Index a) const
Definition: gecko.hpp:689
uint Index
Definition: gecko.hpp:586
WeightedSum sum(const WeightedValue &term) const
Definition: gecko.hpp:513
Graph(uint nodes, uint level)
Definition: gecko.hpp:685
Float bond(Float w, Float, uint) const
Definition: gecko.hpp:489
void vcycle(uint n, uint work=0)
Definition: gecko.cpp:1169
double a
Definition: lissajous.cpp:41
void accumulate(WeightedSum &s, const WeightedSum &t) const
Definition: gecko.hpp:517
Arc::Index arc_index(Node::Index i, Node::Index j) const
Definition: gecko.cpp:737
Node::Index arc_target(Arc::Index a) const
Definition: gecko.hpp:655
Float optimum(const std::vector< WeightedValue > &v) const
Definition: gecko.hpp:431
virtual void beginphase(const Graph *, std::string) const
Definition: gecko.hpp:570
void shuffle(uint seed=0)
Definition: gecko.cpp:1207
virtual void beginorder(const Graph *, Float) const
Definition: gecko.hpp:564
uint edges() const
Definition: gecko.hpp:629
void reweight(uint i)
Definition: gecko.cpp:1221
Float bond(Float w, Float l, uint k) const
Definition: gecko.hpp:381
Float optimum(const std::vector< WeightedValue > &v) const
Definition: gecko.hpp:385
bool less(const WeightedSum &s, const WeightedSum &t) const
Definition: gecko.hpp:345
Arc::Index reverse_arc(Arc::Index a) const
Definition: gecko.cpp:766
virtual void endphase(const Graph *, bool) const
Definition: gecko.hpp:571
RefCoord t[3]
Float length(Node::Index i, Node::Index j) const
Definition: gecko.hpp:688
virtual ~Functional()
Definition: gecko.hpp:239
virtual void accumulate(WeightedSum &s, const WeightedSum &t) const
Definition: gecko.hpp:262
uint nodes() const
Definition: gecko.hpp:628
RefCoord s[3]
Node::Index insert_node(Float length=1)
Definition: gecko.cpp:657
void refine(const Graph *graph)
Definition: gecko.cpp:1051
void place(bool sort=false)
Definition: gecko.cpp:1140
Float mean(const WeightedSum &sum) const
Definition: gecko.hpp:485
bool operator()(uint k, uint l) const
Definition: gecko.hpp:604
virtual bool quit() const
Definition: gecko.hpp:572
bool persistent(Node::Index i) const
Definition: gecko.hpp:727
Progress * progress
Definition: gecko.hpp:731
Float bond(Float w, Float l, uint k) const
Definition: gecko.hpp:358
double f(const Vector &p)