All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
UnionMaximumSpanningForest.h
Go to the documentation of this file.
1 #ifndef UNIONMAXIMUMSPANNINGFOREST_H
2 #define UNIONMAXIMUMSPANNINGFOREST_H
3 
4 #include "Graph.h"
5 #include <limits>
6 #include "../structures/UnionFind.h"
7 #include "../auxiliary/Log.h"
8 #include "../base/Algorithm.h"
9 
10 namespace NetworKit {
11 
16 public:
23 
32  template <typename A>
33  UnionMaximumSpanningForest(const Graph &G, const std::vector<A> &attribute);
34 
38  virtual void run() override;
39 
48  std::vector<bool> getAttribute(bool move = false);
49 
57  bool inUMSF(node u, node v) const;
58 
65  bool inUMSF(edgeid eid) const;
66 
73  Graph getUMSF(bool move = false);
74 
78  virtual bool isParallel() const override;
79 
83  virtual std::string toString() const override;
84 private:
85  struct weightedEdge {
86  edgeweight attribute;
87  node u;
88  node v;
89  edgeid eid;
90 
91  bool operator>(const weightedEdge &other) const {
92  return (attribute > other.attribute) || (attribute == other.attribute && (u > other.u || (u == other.u && v > other.v)));
93  };
94  weightedEdge(node u, node v, edgeweight attribute, edgeid eid = 0) : attribute(attribute), u(u), v(v), eid(eid) {};
95  };
96 
97  const Graph &G;
98  std::vector<weightedEdge> weightedEdges;
99 
100  Graph umsf;
101  std::vector<bool> umsfAttribute;
102 
103  bool hasWeightedEdges;
104  bool hasUMSF;
105  bool hasAttribute;
106 };
107 
108 template <typename A>
109 UnionMaximumSpanningForest::UnionMaximumSpanningForest(const Graph &G, const std::vector< A > &attribute) : G(G), hasWeightedEdges(false), hasUMSF(false), hasAttribute(false) {
110  if (!G.hasEdgeIds()) {
111  throw std::runtime_error("Error: Edges of G must be indexed for using edge attributes");
112  }
113 
114  weightedEdges.reserve(G.numberOfEdges());
115 
116  G.forEdges([&](node u, node v, edgeid eid) {
117  weightedEdges.emplace_back(u, v, attribute[eid], eid);
118  });
119 
120  INFO(weightedEdges.size(), " weighted edges saved");
121 
122  hasWeightedEdges = true;
123 }
124 
125 } // namespace NetworKit
126 
127 #endif // UNIONMAXIMUMSPANNINGFOREST_H
bool inUMSF(node u, node v) const
Checks if the edge (u, v) is part of any maximum-weight spanning forest.
Definition: UnionMaximumSpanningForest.cpp:93
index edgeid
Definition: Globals.h:25
virtual bool isParallel() const override
Definition: UnionMaximumSpanningForest.cpp:137
std::vector< bool > getAttribute(bool move=false)
Get a boolean attribute that indicates for each edge if it is part of any maximum-weight spanning for...
Definition: UnionMaximumSpanningForest.cpp:103
void forEdges(L handle) const
Iterate over all edges of the const graph and call handle (lambda closure).
Definition: Graph.h:1299
UnionMaximumSpanningForest(const Graph &G)
Initialize the union maximum-weight spanning forest algorithm, uses edge weights. ...
Definition: UnionMaximumSpanningForest.cpp:8
virtual void run() override
Execute the algorithm.
Definition: UnionMaximumSpanningForest.cpp:10
Graph getUMSF(bool move=false)
Gets the union of all maximum-weight spanning forests as graph.
Definition: UnionMaximumSpanningForest.cpp:118
Union maximum-weight spanning forest algorithm, computes the union of all maximum-weight spanning for...
Definition: UnionMaximumSpanningForest.h:15
#define INFO(...)
Definition: Log.h:72
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
virtual std::string toString() const override
Definition: UnionMaximumSpanningForest.cpp:133
Definition: Algorithm.h:9
A graph (with optional weights) and parallel iterator methods.
Definition: Graph.h:79
double edgeweight
Definition: Globals.h:24