DynamicMatrix.h
Go to the documentation of this file.
1 /*
2  * DynamicMatrix.h
3  *
4  * Created on: 13.03.2014
5  * Author: Michael Wegner (michael.wegner@student.kit.edu)
6  */
7
8 #ifndef DYNAMIC_MATRIX_H_
9 #define DYNAMIC_MATRIX_H_
10
11 #include "../graph/Graph.h"
12 #include "Vector.h"
13 #include "SparseAccumulator.h"
14 #include "AlgebraicGlobals.h"
15
16 namespace NetworKit {
17
24 protected:
26
29
30  double zero;
31
32 public:
34  DynamicMatrix();
35
41  DynamicMatrix(const count dimension, const double zero = 0.0);
42
43
50  DynamicMatrix(const count nRows, const count nCols, const double zero = 0.0);
51
58  DynamicMatrix(const count dimension, const std::vector<Triplet>& triplets, const double zero = 0.0);
59
67  DynamicMatrix(const count nRows, const count nCols, const std::vector<Triplet>& triplets, const double zero = 0.0);
68
70  DynamicMatrix(const DynamicMatrix &other) = default;
71
73  DynamicMatrix(DynamicMatrix &&other) = default;
74
76  virtual ~DynamicMatrix() = default;
77
79  DynamicMatrix& operator=(DynamicMatrix &&other) = default;
80
82  DynamicMatrix& operator=(const DynamicMatrix &other) = default;
83
89  bool operator==(const DynamicMatrix& other) const {
90  bool graphsEqual = graph.numberOfNodes() == other.graph.numberOfNodes() && graph.numberOfEdges() == other.graph.numberOfEdges();
91  if (graphsEqual) {
92  graph.forEdges([&](node u, node v, edgeweight w) {
93  if (w != other.graph.weight(u, v)) {
94  graphsEqual = false;
95  return;
96  }
97  });
98  }
99
100  return graphsEqual && nRows == other.nRows && nCols == other.nCols && zero == other.zero;
101  }
102
108  bool operator!=(const DynamicMatrix& other) const {
109  return !((*this) == other);
110  }
111
115  inline count numberOfRows() const {
116  return nRows;
117  }
118
122  inline count numberOfColumns() const {
123  return nCols;
124  }
125
129  inline double getZero() const {
130  return zero;
131  }
132
137  count nnzInRow(const index i) const;
138
142  count nnz() const;
143
147  double operator()(const index i, const index j) const;
148
152  void setValue(const index i, const index j, const double value);
153
157  Vector row(const index i) const;
158
162  Vector column(const index j) const;
163
167  Vector diagonal() const;
168
173  DynamicMatrix operator+(const DynamicMatrix &other) const;
174
179  DynamicMatrix& operator+=(const DynamicMatrix &other);
180
186  DynamicMatrix operator-(const DynamicMatrix &other) const;
187
192  DynamicMatrix& operator-=(const DynamicMatrix &other);
193
198  DynamicMatrix operator*(const double scalar) const;
199
204  DynamicMatrix& operator*=(const double scalar);
205
210  Vector operator*(const Vector &vector) const;
211
216  DynamicMatrix operator*(const DynamicMatrix &other) const;
217
222  DynamicMatrix operator/(const double divisor) const;
223
228  DynamicMatrix& operator/=(const double divisor);
229
235  static DynamicMatrix mTmMultiply(const DynamicMatrix &A, const DynamicMatrix &B);
236
242  static DynamicMatrix mmTMultiply(const DynamicMatrix &A, const DynamicMatrix &B);
243
249  static Vector mTvMultiply(const DynamicMatrix &matrix, const Vector &vector);
250
254  DynamicMatrix transpose() const;
255
263  DynamicMatrix extract(const std::vector<index>& rowIndices, const std::vector<index>& columnIndices) const;
264
274  void assign(const std::vector<index>& rowIndices, const std::vector<index>& columnIndices, const DynamicMatrix& source);
275
281  template<typename F>
282  void apply(const F unaryElementFunction);
283
288  static DynamicMatrix adjacencyMatrix(const Graph& graph, double zero = 0.0);
289
295  static DynamicMatrix diagonalMatrix(const Vector& diagonalElements, double zero = 0.0);
296
301  static DynamicMatrix incidenceMatrix(const Graph& graph, double zero = 0.0);
302
307  static DynamicMatrix laplacianMatrix(const Graph& graph,double zero = 0.0);
308
313  static DynamicMatrix normalizedLaplacianMatrix(const Graph& graph, double zero = 0.0);
314
318  template<typename L> void forNonZeroElementsInRow(index row, L handle) const;
319
323  template<typename L> void forElementsInRow(index i, L handle) const;
324
328  template<typename L> void forNonZeroElementsInRowOrder(L handle) const;
329
333  template<typename L> void parallelForNonZeroElementsInRowOrder(L handle) const;
334 };
335
336
337 } /* namespace NetworKit */
338
339 template<typename F>
340 void NetworKit::DynamicMatrix::apply(const F unaryElementFunction) {
341  forNonZeroElementsInRowOrder([&](index i, index j, double value) {
342  setValue(i,j, unaryElementFunction(value));
343  });
344 }
345
346 template<typename L>
348  graph.forEdgesOf(row, [&](index j, edgeweight weight){
349  handle(j, weight);
350  });
351 }
352
353 template<typename L>
354 inline void NetworKit::DynamicMatrix::forElementsInRow(index i, L handle) const {
355  Vector rowVector = row(i);
356  index j = 0;
357  rowVector.forElements([&](double value) {
358  handle(j++, value);
359  });
360 }
361
362 template<typename L>
364  for (index i = 0; i < nRows; ++i) {
365  graph.forEdgesOf(i, [&](index j, edgeweight weight){
366  handle(i, j, weight);
367  });
368  }
369 }
370
371 template<typename L>
373 #pragma omp parallel for
374  for (index i = 0; i < nRows; ++i) {
375  graph.forEdgesOf(i, [&](index j, edgeweight weight){
376  handle(i, j, weight);
377  });
378  }
379 }
380
381 #endif /* DYNAMIC_MATRIX_H_ */
static DynamicMatrix normalizedLaplacianMatrix(const Graph &graph, double zero=0.0)
Returns the (weighted) normalized Laplacian matrix of the (weighted) Graph graph. ...
Definition: DynamicMatrix.cpp:337
DynamicMatrix transpose() const
Transposes this matrix and returns it.
Definition: DynamicMatrix.cpp:227
void forNonZeroElementsInRowOrder(L handle) const
Iterate over all non-zero elements of the matrix in row order and call handle(index row...
Definition: DynamicMatrix.h:363
DynamicMatrix & operator/=(const double divisor)
Divides this matrix by a divisor specified in divisor.
Definition: DynamicMatrix.cpp:177
count nnzInRow(const index i) const
Definition: DynamicMatrix.cpp:31
bool operator==(const DynamicMatrix &other) const
Compares this matrix to other and returns true if the shape and zero element are the same as well as ...
Definition: DynamicMatrix.h:89
DynamicMatrix & operator-=(const DynamicMatrix &other)
Subtracts other from this matrix.
Definition: DynamicMatrix.cpp:116
The DynamicMatrix class represents a matrix that is optimized for sparse matrices and internally uses...
Definition: DynamicMatrix.h:23
count nnz() const
Definition: DynamicMatrix.cpp:36
static DynamicMatrix adjacencyMatrix(const Graph &graph, double zero=0.0)
Returns the (weighted) adjacency matrix of the (weighted) Graph graph.
Definition: DynamicMatrix.cpp:269
static DynamicMatrix diagonalMatrix(const Vector &diagonalElements, double zero=0.0)
Creates a diagonal matrix with dimension equal to the dimension of the Vector diagonalElements.
Definition: DynamicMatrix.cpp:281
void assign(const std::vector< index > &rowIndices, const std::vector< index > &columnIndices, const DynamicMatrix &source)
Assign the contents of the matrix source to this matrix at rows and columns specified by rowIndices a...
Definition: DynamicMatrix.cpp:258
uint64_t index
Typedefs.
Definition: Globals.h:20
void forElementsInRow(index i, L handle) const
Iterate over all elements in row i in the matrix and call handle(index column, double value) ...
Definition: DynamicMatrix.h:354
void forEdges(L handle) const
Iterate over all edges of the const graph and call handle (lambda closure).
Definition: Graph.h:1299
count numberOfRows() const
Definition: DynamicMatrix.h:115
void parallelForNonZeroElementsInRowOrder(L handle) const
Iterate in parallel over all rows and call handle(index row, index column, double value) on non-zero ...
Definition: DynamicMatrix.h:372
DynamicMatrix operator+(const DynamicMatrix &other) const
Adds this matrix to other and returns the result.
Definition: DynamicMatrix.cpp:98
edgeweight weight(node u, node v) const
Return edge weight of edge {u,v}.
Definition: Graph.cpp:807
static Vector mTvMultiply(const DynamicMatrix &matrix, const Vector &vector)
Computes matrix^T * vector.
Definition: DynamicMatrix.cpp:214
Vector diagonal() const
Definition: DynamicMatrix.cpp:89
virtual ~DynamicMatrix()=default
Default destructor.
DynamicMatrix operator*(const double scalar) const
Multiplies this matrix with a scalar specified in scalar and returns the result.
Definition: DynamicMatrix.cpp:126
double operator()(const index i, const index j) const
Definition: DynamicMatrix.cpp:45
count numberOfColumns() const
Definition: DynamicMatrix.h:122
DynamicMatrix operator/(const double divisor) const
Divides this matrix by a divisor specified in divisor and returns the result in a new matrix...
Definition: DynamicMatrix.cpp:173
static DynamicMatrix mTmMultiply(const DynamicMatrix &A, const DynamicMatrix &B)
Computes A^T * B.
Definition: DynamicMatrix.cpp:181
uint64_t count
Definition: Globals.h:21
count nCols
Definition: DynamicMatrix.h:28
DynamicMatrix & operator+=(const DynamicMatrix &other)
Definition: DynamicMatrix.cpp:102
index node
Definition: Globals.h:23
Vector column(const index j) const
Definition: DynamicMatrix.cpp:76
DynamicMatrix & operator=(DynamicMatrix &&other)=default
Default move assignment operator.
count numberOfEdges() const
Return the number of edges in the graph.
Definition: Graph.h:712
void apply(const F unaryElementFunction)
Applies the unary function unaryElementFunction to each value in the matrix.
Definition: DynamicMatrix.h:340
The Vector class represents a basic vector with double coefficients.
Definition: Vector.h:25
void forNonZeroElementsInRow(index row, L handle) const
Iterate over all non-zero elements of row row in the matrix and call handle(index row...
Definition: DynamicMatrix.h:347
DynamicMatrix & operator*=(const double scalar)
Multiplies this matrix with a scalar specified in scalar.
Definition: DynamicMatrix.cpp:130
double getZero() const
Returns the zero element of the matrix.
Definition: DynamicMatrix.h:129
static DynamicMatrix laplacianMatrix(const Graph &graph, double zero=0.0)
Returns the (weighted) Laplacian matrix of the (weighteD) Graph graph.
Definition: DynamicMatrix.cpp:319
double zero
Definition: DynamicMatrix.h:30
count numberOfNodes() const
Return the number of nodes in the graph.
Definition: Graph.h:706
static DynamicMatrix mmTMultiply(const DynamicMatrix &A, const DynamicMatrix &B)
Computes A * B^T.
Definition: DynamicMatrix.cpp:196
DynamicMatrix()
Default constructor.
Definition: DynamicMatrix.cpp:12
DynamicMatrix extract(const std::vector< index > &rowIndices, const std::vector< index > &columnIndices) const
Extracts a matrix with rows and columns specified by rowIndices and columnIndices from this matrix...
Definition: DynamicMatrix.cpp:236
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
DynamicMatrix operator-(const DynamicMatrix &other) const
Subtracts other from this matrix and returns the result.
Definition: DynamicMatrix.cpp:112
Vector row(const index i) const
Definition: DynamicMatrix.cpp:65
static DynamicMatrix incidenceMatrix(const Graph &graph, double zero=0.0)
Returns the (weighted) incidence matrix of the (weighted) Graph graph.
Definition: DynamicMatrix.cpp:290
void forElements(L handle)
Iterate over all elements of the vector and call handler (lambda closure).
Definition: Vector.h:330
count nRows
Definition: DynamicMatrix.h:27
double edgeweight
Definition: Globals.h:24
bool operator!=(const DynamicMatrix &other) const
Compares this matrix to other and returns false if the shape and zero element are the same as well as...
Definition: DynamicMatrix.h:108
Graph graph
Definition: DynamicMatrix.h:25
void setValue(const index i, const index j, const double value)
Set the matrix at position (i, j) to value.
Definition: DynamicMatrix.cpp:54