All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
RandomMaximumSpanningForest.h
Go to the documentation of this file.
1 #ifndef RANDOMMAXIMUMSPANNINGFOREST_H
2 #define RANDOMMAXIMUMSPANNINGFOREST_H
3 
4 #include "Graph.h"
5 #include <limits>
6 #include "../structures/UnionFind.h"
7 #include "../auxiliary/Log.h"
8 #include "../auxiliary/Random.h"
9 #include "../base/Algorithm.h"
10 
11 namespace NetworKit {
12 
17 public:
24 
33  template <typename A>
34  RandomMaximumSpanningForest(const Graph &G, const std::vector<A> &attribute);
35 
39  virtual void run() override;
40 
49  std::vector<bool> getAttribute(bool move = false);
50 
58  bool inMSF(node u, node v) const;
59 
66  bool inMSF(edgeid eid) const;
67 
74  Graph getMSF(bool move = false);
75 
79  virtual bool isParallel() const override;
80 
84  virtual std::string toString() const override;
85 
86 private:
87  struct weightedEdge {
88  double attribute;
89  node u;
90  node v;
91  edgeid eid;
92  index rand;
93 
94  bool operator>(const weightedEdge &other) const {
95  return
96  (attribute > other.attribute)
97  ||
98  (attribute == other.attribute &&
99  (rand > other.rand ||
100  (rand == other.rand && (u > other.u || (u == other.u && v > other.v)))));
101  };
102  weightedEdge(node u, node v, double attribute, edgeid eid = 0) : attribute(attribute), u(u), v(v), eid(eid), rand(Aux::Random::integer()) {};
103  };
104 
105  const Graph &G;
106  std::vector<weightedEdge> weightedEdges;
107 
108  Graph msf;
109  std::vector<bool> msfAttribute;
110 
111  bool hasWeightedEdges;
112  bool hasMSF;
113  bool hasAttribute;
114 };
115 
116 template <typename A>
117 RandomMaximumSpanningForest::RandomMaximumSpanningForest(const Graph &G, const std::vector< A > &attribute) : G(G), hasWeightedEdges(false), hasMSF(false), hasAttribute(false) {
118  if (!G.hasEdgeIds()) {
119  throw std::runtime_error("Error: Edges of G must be indexed for using edge attributes");
120  }
121 
122  weightedEdges.reserve(G.numberOfEdges());
123 
124  G.forEdges([&](node u, node v, edgeid eid) {
125  weightedEdges.emplace_back(u, v, attribute[eid], eid);
126  });
127 
128  INFO(weightedEdges.size(), " weighted edges saved");
129 
130  hasWeightedEdges = true;
131 }
132 
133 
134 } // namespace NetworKit
135 
136 #endif // RANDOMMAXIMUMSPANNINGFOREST_H
std::vector< bool > getAttribute(bool move=false)
Get a boolean attribute that indicates for each edge if it is part of the calculated maximum-weight s...
Definition: RandomMaximumSpanningForest.cpp:92
virtual void run() override
Execute the algorithm.
Definition: RandomMaximumSpanningForest.cpp:13
index edgeid
Definition: Globals.h:25
uint64_t integer()
Definition: Random.cpp:64
uint64_t index
Typedefs.
Definition: Globals.h:20
bool inMSF(node u, node v) const
Checks if the edge (u, v) is part of the calculated maximum-weight spanning forest.
Definition: RandomMaximumSpanningForest.cpp:82
void forEdges(L handle) const
Iterate over all edges of the const graph and call handle (lambda closure).
Definition: Graph.h:1299
#define INFO(...)
Definition: Log.h:72
Computes a random maximum-weight spanning forest using Kruskal's algorithm by randomizing the order o...
Definition: RandomMaximumSpanningForest.h:16
RandomMaximumSpanningForest(const Graph &G)
Initialize the random maximum-weight spanning forest algorithm, uses edge weights.
Definition: RandomMaximumSpanningForest.cpp:11
index node
Definition: Globals.h:23
count numberOfEdges() const
Return the number of edges in the graph.
Definition: Graph.h:712
bool hasEdgeIds() const
Checks if edges have been indexed.
Definition: Graph.h:410
Definition: Algorithm.h:9
virtual bool isParallel() const override
Definition: RandomMaximumSpanningForest.cpp:126
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
Graph getMSF(bool move=false)
Gets the calculated maximum-weight spanning forest as graph.
Definition: RandomMaximumSpanningForest.cpp:107
virtual std::string toString() const override
Definition: RandomMaximumSpanningForest.cpp:122