All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
AlgebraicMatchingCoarsening.h
Go to the documentation of this file.
1 /*
2  * AlgebraicMatchingCoarsening.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_ALGEBRAICMATCHINGCOARSENING_H_
9 #define NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICMATCHINGCOARSENING_H_
10 
11 #include "../AlgebraicGlobals.h"
12 #include "../../coarsening/GraphCoarsening.h"
13 #include "../../matching/Matching.h"
14 
15 namespace NetworKit {
16 
22 template<class Matrix>
24 public:
33  AlgebraicMatchingCoarsening(const Graph& graph, const Matching& matching, bool noSelfLoops = false);
34 
38  void run() override;
39 
40 private:
41  Matrix A; // adjacency matrix of the graph
42  Matrix P; // projection matrix
43  bool noSelfLoops;
44 };
45 
46 template<class Matrix>
47 AlgebraicMatchingCoarsening<Matrix>::AlgebraicMatchingCoarsening(const Graph& graph, const Matching& matching, bool noSelfLoops) : GraphCoarsening(graph), A(Matrix::adjacencyMatrix(graph)), noSelfLoops(noSelfLoops) {
48  if (G.isDirected()) throw std::runtime_error("Only defined for undirected graphs.");
49  nodeMapping.resize(graph.numberOfNodes());
50  std::vector<Triplet> triplets(graph.numberOfNodes());
51 
52  count numCoarse = graph.numberOfNodes() - matching.size(graph);
53  index idx = 0;
54  graph.forNodes([&](node u) {
55  index mate = matching.mate(u);
56  if ((mate == none) || (u < mate)) {
57  // vertex u is carried over to the new level
58  nodeMapping[u] = idx;
59  ++idx;
60  }
61  else {
62  // vertex u is not carried over, receives ID of mate
63  nodeMapping[u] = nodeMapping[mate];
64  }
65 
66  triplets[u] = {u, nodeMapping[u], 1};
67  });
68 
69  P = Matrix(graph.numberOfNodes(), numCoarse, triplets); // dimensions: fine x coarse
70 }
71 
72 template<class Matrix>
74  Matrix coarseAdj = P.transpose() * A * P; // Matrix::mTmMultiply performs worse due to high sparsity of P (nnz = n)
75 
76  Gcoarsened = Graph(coarseAdj.numberOfRows(), true);
77  coarseAdj.forNonZeroElementsInRowOrder([&](node u, node v, double weight) {
78  if (u == v && !noSelfLoops) {
79  Gcoarsened.addEdge(u, v, weight / 2.0);
80  } else if (u < v) {
81  Gcoarsened.addEdge(u, v, weight);
82  }
83  });
84 
85  hasRun = true;
86 }
87 
88 } /* namespace NetworKit */
89 
90 #endif /* NETWORKIT_CPP_ALGEBRAIC_ALGORITHMS_ALGEBRAICMATCHINGCOARSENING_H_ */
void forNodes(L handle) const
Iterate over all nodes of the graph and call handle (lambda closure).
Definition: Graph.h:1097
count size(const Graph &G) const
Get the number of edges in this matching.
Definition: Matching.cpp:69
bool isDirected() const
Return true if this graph supports directed edges.
Definition: Graph.h:694
Implements an algebraic version of the MatchingCoarsening algorithm by computing a projection matrix ...
Definition: AlgebraicMatchingCoarsening.h:23
uint64_t index
Typedefs.
Definition: Globals.h:20
void run() override
Computes the coarsening for the graph using the given matching.
Definition: AlgebraicMatchingCoarsening.h:73
index mate(node v) const
Get the matched neighbor of v if it exists, otherwise none.
Definition: Matching.cpp:79
AlgebraicMatchingCoarsening(const Graph &graph, const Matching &matching, bool noSelfLoops=false)
Constructs an instance of AlgebraicMatchingCoarsening for the given Graph graph and the corresponding...
Definition: AlgebraicMatchingCoarsening.h:47
Abstract base class for graph coarsening/contraction algorithms.
Definition: GraphCoarsening.h:20
uint64_t count
Definition: Globals.h:21
std::vector< std::vector< count > > Matrix
Definition: DynamicNMIDistance.h:16
constexpr index none
Constants.
Definition: Globals.h:28
index node
Definition: Globals.h:23
std::vector< node > nodeMapping
Definition: GraphCoarsening.h:45
count numberOfNodes() const
Return the number of nodes in the graph.
Definition: Graph.h:706
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
const Graph & G
Definition: GraphCoarsening.h:43
Definition: Matching.h:19