LevelHierarchy.h
Go to the documentation of this file.
1 /*
2  * LevelHierarchy.h
3  *
4  * Created on: 10.01.2015
5  * Author: Michael
6  */
7
8 #ifndef LEVELHIERARCHY_H_
9 #define LEVELHIERARCHY_H_
10
11 #include "Level/Level.h"
12 #include "Level/LevelFinest.h"
13 #include "Level/LevelElimination.h"
14 #include "Level/LevelAggregation.h"
15 #include "LAMGSettings.h"
16 #include "../../algebraic/DenseMatrix.h"
17
18 namespace NetworKit {
19
23 template<class Matrix>
25 private:
26  std::vector<LevelType> levelType;
27  std::vector<index> levelIndex;
28  std::vector<LevelElimination<Matrix>> eliminationLevels;
29  std::vector<LevelAggregation<Matrix>> aggregationLevels;
30  LevelFinest<Matrix> finestLevel;
31  DenseMatrix coarseLUMatrix;
32
33  void createCoarseMatrix();
34
35 public:
36  LevelHierarchy() = default;
37
39  void addEliminationLevel(const Matrix& A, const std::vector<EliminationStage<Matrix>>& coarseningStages);
40  void addAggregationLevel(const Matrix& A, const Matrix& P, const Matrix& R);
41  void setLastAsCoarsest();
43  return coarseLUMatrix;
44  }
45
46  inline count size() const {
47  return levelType.size() + 1; // elimination + aggregation levels + finestLevel
48  }
49
50  LevelType getType(index levelIdx) const;
51  Level<Matrix>& at(index levelIdx);
52  double cycleIndex(index levelIdx);
53 };
54
55 template<class Matrix>
57  finestLevel = LevelFinest<Matrix>(A);
58 }
59
60 template<class Matrix>
61 void LevelHierarchy<Matrix>::addEliminationLevel(const Matrix& A, const std::vector<EliminationStage<Matrix>>& coarseningStages) {
62  levelType.push_back(ELIMINATION);
63  levelIndex.push_back(eliminationLevels.size());
64  eliminationLevels.push_back(LevelElimination<Matrix>(A, coarseningStages));
65 }
66
67 template <class Matrix>
69  levelType.push_back(AGGREGATION);
70  levelIndex.push_back(aggregationLevels.size());
71  aggregationLevels.push_back(LevelAggregation<Matrix>(A, P, R));
72 }
73
74 template<class Matrix>
76  const Matrix& A = this->at(size()-1).getLaplacian();
77  count n = A.numberOfRows() + 1;
78  std::vector<double> entries(n*n, 0.0);
79  A.parallelForNonZeroElementsInRowOrder([&](index i, index j, double value) {
80  entries[i * n + j] = value;
81  });
82
83  for (index i = 0; i < n-1; ++i) {
84  entries[i * n + n-1] = 1;
85  entries[(n-1)*n + i] = 1;
86  }
87
88  coarseLUMatrix = DenseMatrix(n, n, entries);
89  DenseMatrix::LUDecomposition(coarseLUMatrix);
90 }
91
92
93 template<class Matrix>
95  assert(levelIdx >= 0 && levelIdx < this->size());
96
97  if (levelIdx == 0) {
98  return FINEST;
99  } else {
100  return levelType[levelIdx-1];
101  }
102 }
103
104 template<class Matrix>
106  assert(levelIdx >= 0 && levelIdx < this->size());
107
108  if (levelIdx == 0) { // finest level
109  return finestLevel;
110  } else {
111  levelIdx--;
112  }
113
114  if (levelType[levelIdx] == ELIMINATION) {
115  return eliminationLevels[levelIndex[levelIdx]];
116  } else {
117  return aggregationLevels[levelIndex[levelIdx]];
118  }
119 }
120
121 template<class Matrix>
123  double gamma = 1.0;
124  if (getType(levelIdx+1) != ELIMINATION) {
125  count finestNumEdges = finestLevel.getLaplacian().nnz();
126  count numFineEdges = this->at(levelIdx).getLaplacian().nnz();
127
128  if (numFineEdges > 0.1 * finestNumEdges) {
129  gamma = SETUP_CYCLE_INDEX;
130  } else {
131  count numCoarseEdges = this->at(levelIdx+1).getLaplacian().nnz();
132  gamma = std::max(1.0, std::min(1.5, SETUP_COARSENING_WORK_GUARD / ((double) numCoarseEdges / (double) numFineEdges)));
133  }
134  }
135
136  return gamma;
137 }
138
139 } /* namespace NetworKit */
140
141 #endif /* LEVELHIERARCHY_H_ */
constexpr double SETUP_COARSENING_WORK_GUARD
Definition: LAMGSettings.h:59
Definition: LevelElimination.h:20
static void LUDecomposition(DenseMatrix &matrix)
Decomposes the given matrix into lower L and upper U matrix (in-place).
Definition: DenseMatrix.cpp:201
double cycleIndex(index levelIdx)
Definition: LevelHierarchy.h:122
void addAggregationLevel(const Matrix &A, const Matrix &P, const Matrix &R)
Definition: LevelHierarchy.h:68
LevelType getType(index levelIdx) const
Definition: LevelHierarchy.h:94
uint64_t index
Typedefs.
Definition: Globals.h:20
Definition: Level.h:15
Definition: LevelAggregation.h:19
Represents a dense matrix.
Definition: DenseMatrix.h:24
count size() const
Definition: LevelHierarchy.h:46
Definition: LevelFinest.h:19
Definition: Level.h:16
uint64_t count
Definition: Globals.h:21
std::vector< std::vector< count > > Matrix
Definition: DynamicNMIDistance.h:16
LevelType
Definition: Level.h:15
Definition: LevelHierarchy.h:56
DenseMatrix & getCoarseMatrix()
Definition: LevelHierarchy.h:42
Abstract base class for an LAMG Level.
Definition: Level.h:26
Level< Matrix > & at(index levelIdx)
Definition: LevelHierarchy.h:105
void setLastAsCoarsest()
Definition: LevelHierarchy.h:75
void addEliminationLevel(const Matrix &A, const std::vector< EliminationStage< Matrix >> &coarseningStages)
Definition: LevelHierarchy.h:61
Definition: Level.h:17
constexpr double SETUP_CYCLE_INDEX
Definition: LAMGSettings.h:30
Definition: LevelHierarchy.h:24
Definition: EliminationStage.h:19