All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
MatrixTools.h
Go to the documentation of this file.
1 /*
2  * MatrixTools.h
3  *
4  * Created on: May 31, 2016
5  * Author: Michael Wegner (michael.wegner@student.kit.edu)
6  */
7 
8 #ifndef NETWORKIT_CPP_ALGEBRAIC_MATRIXTOOLS_H_
9 #define NETWORKIT_CPP_ALGEBRAIC_MATRIXTOOLS_H_
10 
11 #include "../graph/Graph.h"
12 #include <atomic>
13 
14 namespace MatrixTools {
15 
21 template<class Matrix>
22 bool isSymmetric(const Matrix& matrix) {
23  bool output = true;
24  matrix.forNonZeroElementsInRowOrder([&] (NetworKit::index i, NetworKit::index j, NetworKit::edgeweight w) {
25  if (fabs(matrix(j, i)-w) > NetworKit::FLOAT_EPSILON) {
26  output = false;
27  return;
28  }
29  });
30  return output;
31 }
32 
38 template<class Matrix>
39 bool isSDD(const Matrix& matrix) {
40  if (!isSymmetric(matrix)) {
41  return false;
42  }
43 
44  /* Criterion: a_ii >= \sum_{j != i} a_ij */
45  std::vector<double> row_sum(matrix.numberOfRows());
46  matrix.parallelForNonZeroElementsInRowOrder([&] (NetworKit::node i, NetworKit::node j, double value) {
47  if (i == j) {
48  row_sum[i] += value;
49  } else {
50  row_sum[i] -= fabs(value);
51  }
52  });
53 
54  return std::all_of(row_sum.begin(), row_sum.end(), [] (double val) {return val > -NetworKit::FLOAT_EPSILON;});
55 }
56 
62 template<typename Matrix>
63 bool isLaplacian(const Matrix& matrix) {
64  if (!isSymmetric(matrix)) {
65  return false;
66  }
67 
68  /* Criterion: \forall_i \sum_j A_ij = 0 */
69  std::vector<double> row_sum(matrix.numberOfRows());
70  std::atomic<bool> right_sign(true);
71  matrix.parallelForNonZeroElementsInRowOrder([&] (NetworKit::node i, NetworKit::node j, double value) {
72  if (i != j && value > NetworKit::FLOAT_EPSILON) {
73  right_sign = false;
74  }
75  row_sum[i] += value;
76  });
77 
78  return right_sign && std::all_of(row_sum.begin(), row_sum.end(), [] (double val) {return fabs(val) < NetworKit::FLOAT_EPSILON;});
79 }
80 
86 template<class Matrix>
88  assert(isLaplacian(laplacian));
89  NetworKit::Graph G(std::max(laplacian.numberOfRows(), laplacian.numberOfColumns()), true, false);
90  laplacian.forNonZeroElementsInRowOrder([&](NetworKit::node u, NetworKit::node v, NetworKit::edgeweight weight) {
91  if (u != v) { // exclude diagonal
92  if (u < v) {
93  G.addEdge(u, v, -weight);
94  }
95  }
96  });
97 
98  return G;
99 }
100 
106 template<class Matrix>
108  bool directed = !isSymmetric(matrix);
109  NetworKit::Graph G(std::max(matrix.numberOfRows(), matrix.numberOfColumns()), true, directed);
110  matrix.forNonZeroElementsInRowOrder([&](NetworKit::node u, NetworKit::node v, NetworKit::edgeweight weight) {
111  if (directed || u <= v) {
112  G.addEdge(u, v, weight);
113  }
114  });
115 
116  return G;
117 }
118 
119 }
120 
121 
122 
123 #endif /* NETWORKIT_CPP_ALGEBRAIC_MATRIXTOOLS_H_ */
bool isSDD(const Matrix &matrix)
Checks if matrix is symmetric diagonally dominant (SDD).
Definition: MatrixTools.h:39
NetworKit::Graph laplacianToGraph(const Matrix &laplacian)
Computes a graph having the given laplacian.
Definition: MatrixTools.h:87
uint64_t index
Typedefs.
Definition: Globals.h:20
void addEdge(node u, node v, edgeweight ew=defaultEdgeWeight)
Insert an edge between the nodes u and v.
Definition: Graph.cpp:600
bool isLaplacian(const Matrix &matrix)
Checks if matrix is a Laplacian matrix.
Definition: MatrixTools.h:63
std::vector< std::vector< count > > Matrix
Definition: DynamicNMIDistance.h:16
constexpr double FLOAT_EPSILON
Floating point epsilon to use in comparisons.
Definition: AlgebraicGlobals.h:23
index node
Definition: Globals.h:23
bool isSymmetric(const Matrix &matrix)
Checks if matrix is symmetric.
Definition: MatrixTools.h:22
NetworKit::Graph matrixToGraph(const Matrix &matrix)
Interprets the matrix as adjacency matrix of a graph.
Definition: MatrixTools.h:107
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
double edgeweight
Definition: Globals.h:24