All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
SparseAccumulator.h
Go to the documentation of this file.
1 /*
2  * SparseAccumulator.h
3  *
4  * Created on: 14.05.2014
5  * Author: Michael Wegner (michael.wegner@student.kit.edu)
6  */
7 
8 #ifndef SPARSEACCUMULATOR_H_
9 #define SPARSEACCUMULATOR_H_
10 
11 #include <vector>
12 #include <algorithm>
13 #include <cassert>
14 #include "../Globals.h"
15 
16 namespace NetworKit {
17 
23 private:
25  count row;
26 
27 protected:
29  std::vector<double> values; // w
30 
32  std::vector<count> occupied; // b
33 
35  std::vector<index> indices; // LS
36 
37 public:
42  SparseAccumulator(count size) : row(1), values(size), occupied(size, 0) {}
43 
49  void scatter(double value, index pos) {
50  if (occupied[pos] < row) {
51  values[pos] = value;
52  occupied[pos] = row;
53  indices.push_back(pos);
54  } else {
55  values[pos] += value;
56  }
57  }
58 
66  template<typename L>
67  void scatter(double value, index pos, L& handle) {
68  assert(pos < values.size());
69 
70  if (occupied[pos] < row) {
71  values[pos] = value;
72  occupied[pos] = row;
73  indices.push_back(pos);
74  } else {
75  values[pos] = handle(values[pos], value);
76  }
77  }
78 
85  template<typename L> count gather(L handle) {
86  count nonZeros = 0;
87  std::sort(indices.begin(), indices.end());
88  for (index idx : indices) {
89  handle(row - 1, idx, values[idx]);
90  nonZeros++;
91  }
92 
93  return nonZeros;
94  }
95 
99  void increaseRow() {
100  row++;
101  indices.clear();
102  }
103 };
104 
105 } /* namespace NetworKit */
106 
107 #endif /* SPARSEACCUMULATOR_H_ */
uint64_t index
Typedefs.
Definition: Globals.h:20
The SparseAccumulator class represents the sparse accumulator datastructure as described in Kepner...
Definition: SparseAccumulator.h:22
SparseAccumulator(count size)
Constructs the SparseAccumulator with size size.
Definition: SparseAccumulator.h:42
count gather(L handle)
Calls handle for each non zero value of the current row.
Definition: SparseAccumulator.h:85
uint64_t count
Definition: Globals.h:21
void increaseRow()
Sets the SparseAccumulator to the next row which invalidates all currently stored data...
Definition: SparseAccumulator.h:99
std::vector< count > occupied
dense vector of integers which stores whether a valid value is stored in values at each position ...
Definition: SparseAccumulator.h:32
std::vector< index > indices
unordered list to store the position of valid values in values vector
Definition: SparseAccumulator.h:35
std::vector< double > values
dense vector of doubles which stores the computed values
Definition: SparseAccumulator.h:29
void scatter(double value, index pos, L &handle)
Stores value at pos.
Definition: SparseAccumulator.h:67
void scatter(double value, index pos)
Stores value at pos.
Definition: SparseAccumulator.h:49