AlgebraicTriangleCounting.h
Go to the documentation of this file.
1 /*
2  * AlgebraicTriangleCounting.h
3  *
4  * Created on: Jul 12, 2016
5  * Author: Michael Wegner (michael.wegner@student.kit.edu)
6  */
7
8 #ifndef NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICTRIANGLECOUNTING_H_
9 #define NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICTRIANGLECOUNTING_H_
10
11 #include "../../base/Algorithm.h"
12
13 namespace NetworKit {
14
19 template<class Matrix>
21 public:
26  AlgebraicTriangleCounting(const Graph& graph) : A(Matrix::adjacencyMatrix(graph)), directed(graph.isDirected()) {}
27
32  void run() override;
33
38  count score(node u) const {
39  if (!hasRun) throw std::runtime_error("AlgebraicTriangleCounting::score(node u): Call run() method first.");
40  assert(u < A.numberOfRows());
41  return nodeScores[u];
42  }
43
49  std::vector<count> getScores(bool moveOut = false) {
50  if (!hasRun) throw std::runtime_error("AlgebraicTriangleCounting::getScores(): Call run() method first.");
51  hasRun = !moveOut;
52  return moveOut? std::move(nodeScores) : nodeScores;
53  }
54
55 private:
56  Matrix A;
57  bool directed;
58  std::vector<count> nodeScores;
59 };
60
61 template<class Matrix>
63  Matrix powA = A * A * A;
64
65  nodeScores.clear();
66  nodeScores.resize(A.numberOfRows(), 0);
67
68 #pragma omp parallel for
69  for (index i = 0; i < powA.numberOfRows(); ++i) {
70  nodeScores[i] = directed? powA(i,i) : powA(i,i) / 2.0;
71  }
72
73  hasRun = true;
74 }
75
76 } /* namespace NetworKit */
77
78 #endif /* NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICTRIANGLECOUNTING_H_ */
void run() override
Computes the number of triangles each node is part of.
Definition: AlgebraicTriangleCounting.h:62
count score(node u) const
Returns the score of node u.
Definition: AlgebraicTriangleCounting.h:38
uint64_t index
Typedefs.
Definition: Globals.h:20
AlgebraicTriangleCounting(const Graph &graph)
Creates an instance of AlgebraicTriangleCounting for the given Graph graph.
Definition: AlgebraicTriangleCounting.h:26
bool hasRun
A boolean variable indicating whether an algorithm has finished its computation or not...
Definition: Algorithm.h:14
uint64_t count
Definition: Globals.h:21
std::vector< std::vector< count > > Matrix
Definition: DynamicNMIDistance.h:16
index node
Definition: Globals.h:23
Implements a triangle counting algorithm for nodes based on algebraic methods.
Definition: AlgebraicTriangleCounting.h:20
Definition: Algorithm.h:9
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
std::vector< count > getScores(bool moveOut=false)
Returns the scores for all nodes of the graph.
Definition: AlgebraicTriangleCounting.h:49