All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Cover.h
Go to the documentation of this file.
1 /*
2  * Cover.h
3  *
4  * Created on: 03.10.2013
5  * Author: cls
6  */
7 
8 #ifndef COVER_H_
9 #define COVER_H_
10 
11 #include <cinttypes>
12 #include <set>
13 #include <vector>
14 #include <map>
15 #include <cassert>
16 #include <limits>
17 #include "Partition.h"
18 #include "../Globals.h"
19 
20 namespace NetworKit {
21 
27 class Cover {
28 
29 public:
31  Cover();
32 
38  Cover(index z);
39 
45  Cover(const Partition &p);
46 
48  virtual ~Cover() = default;
49 
50 
56  inline std::set<index>& operator [](const index& e) {
57  return this->data[e];
58  }
64  inline const std::set<index>& operator [](const index& e) const {
65  return this->data[e];
66  }
67 
74  inline std::set<index> subsetsOf(index e) const {
75  // TODO: assert (e < this->numberOfElements());
76  return this->data[e];
77  }
78 
79 
80 
87  bool contains(index e) const;
88 
89 
97  bool inSameSubset(index e1, index e2) const;
98 
99 
105  std::set<index> getMembers(const index s) const;
106 
107 
113  void addToSubset(index s, index e);
114 
115 
121  void removeFromSubset(index s, index e);
122 
123 
130  void moveToSubset(index s, index e);
131 
132 
139 
140 
145  void allToSingletons();
146 
147 
153  void mergeSubsets(index s, index t);
154 
155 
162  index upperBound() const;
163 
168  index lowerBound() const;
169 
170 
176  std::vector<count> subsetSizes() const;
177 
178 
184  std::map<index, count> subsetSizeMap() const;
185 
186 
192  count numberOfSubsets() const;
193 
199  count numberOfElements() const;
200 
206  std::set<index> getSubsetIds() const;
207 
213  void setUpperBound(index upper);
214 
215 
221  template<typename Callback> void forEntries(Callback func) const;
222 
223 
229  template<typename Callback> void parallelForEntries(Callback handle) const;
230 
231 
232 
233 
234 private:
235 
236  index z;
237  index omega;
238  std::vector<std::set<index>> data;
239 
240 
244  inline index newSubsetId() {
245  omega++;
246  index s = omega;
247  return s;
248  }
249 
250 };
251 
252 template<typename Callback>
253 inline void Cover::forEntries(Callback handle) const {
254  for (index e = 0; e <= this->z; e += 1) {
255  handle(e, data[e]);
256  }
257 }
258 
259 template<typename Callback>
260 inline void Cover::parallelForEntries(Callback handle) const {
261  #pragma omp parallel for
262  for (index e = 0; e <= this->z; e += 1) {
263  handle(e, data[e]);
264  }
265 }
266 
267 } /* namespace NetworKit */
268 
269 #endif /* COVER_H_ */
count numberOfSubsets() const
Get the current number of sets in this cover.
Definition: Cover.cpp:149
index upperBound() const
Get an upper bound for the subset ids that have been assigned.
Definition: Cover.cpp:109
void forEntries(Callback func) const
Iterate over all entries (node, subset ID of node) and execute callback function func (lambda closure...
Definition: Cover.h:253
bool inSameSubset(index e1, index e2) const
Check if two elements e1 and e2 belong to the same subset.
Definition: Cover.cpp:31
void mergeSubsets(index s, index t)
Assigns the elements from both sets to a new set.
Definition: Cover.cpp:88
bool contains(index e) const
Check if cover assigns a valid subset to the element e.
Definition: Cover.cpp:27
uint64_t index
Typedefs.
Definition: Globals.h:20
virtual ~Cover()=default
Default destructor.
std::set< index > getSubsetIds() const
Get the ids of nonempty subsets.
Definition: Cover.cpp:180
void moveToSubset(index s, index e)
Move the element e to subset s, i.e.
Definition: Cover.cpp:67
Implements a cover of a set, i.e.
Definition: Cover.h:27
std::set< index > subsetsOf(index e) const
Return the ids of subsets in which the element e is contained.
Definition: Cover.h:74
Implements a partition of a set, i.e.
Definition: Partition.h:31
std::map< index, count > subsetSizeMap() const
Get a map from subset id to size of the subset.
Definition: Cover.cpp:135
Cover()
Default constructor.
Definition: Cover.cpp:15
count numberOfElements() const
Get the current number of elements in this cover.
Definition: Cover.cpp:172
uint64_t count
Definition: Globals.h:21
index lowerBound() const
Get a lower bound for the subset ids that have been assigned.
Definition: Cover.cpp:113
void allToSingletons()
Assigns every element to a singleton set.
Definition: Cover.cpp:82
std::set< index > getMembers(const index s) const
Get the members of a specific subset s.
Definition: Cover.cpp:41
void setUpperBound(index upper)
Sets an upper bound for the subset ids that CAN be assigned.
Definition: Cover.cpp:176
void addToSubset(index s, index e)
Add the (previously unassigned) element e to the set s.
Definition: Cover.cpp:54
std::set< index > & operator[](const index &e)
Index operator.
Definition: Cover.h:56
std::vector< count > subsetSizes() const
Get a list of subset sizes.
Definition: Cover.cpp:117
index toSingleton(index e)
Creates a singleton set containing the element e and returns the index of the new set...
Definition: Cover.cpp:74
void removeFromSubset(index s, index e)
Remove the element e from the set s.
Definition: Cover.cpp:60
void parallelForEntries(Callback handle) const
Iterate over all entries (node, subset ID of node) in parallel and execute callback function func (la...
Definition: Cover.h:260