All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
Partition.h
Go to the documentation of this file.
1 /*
2  * Partition.h
3  *
4  * Created on: 03.10.2013
5  * Author: cls
6  */
7 
8 #ifndef PARTITION_H_
9 #define PARTITION_H_
10 
11 #include <cinttypes>
12 #include <set>
13 #include <vector>
14 #include <map>
15 #include <cassert>
16 #include <limits>
17 
18 #include "../graph/Graph.h"
19 
20 
21 
22 namespace NetworKit {
23 
24 
25 
31 class Partition {
32 
33 public:
34 
35  Partition();
36 
42  Partition(index z);
43 
53  Partition(index z, index defaultValue);
54 
55 
56  Partition(const std::vector<index>& data);
57 
63  inline index& operator [](const index& e) {
64  return this->data[e];
65  }
71  inline const index& operator [](const index& e) const {
72  return this->data[e];
73  }
74 
81  inline index subsetOf(index e) const {
82  assert (e < this->numberOfElements());
83  return this->data[e];
84  }
85 
86 
92  inline index extend() {
93  data.push_back(none);
94  z++;
95  assert (z == data.size()); //(data.size() - 1)
96  return z-1;
97  }
98 
99 
104  inline void remove(index e) {
105  assert (e < z);
106  data[e] = none;
107  }
108 
115  inline void addToSubset(index s, index e) {
116  assert (data[e] == none); // guarantee that element was unassigned
117  assert (s <= omega); // do not create new subset ids
118  data[e] = s;
119  }
120 
121 
128  inline void moveToSubset(index s, index e) {
129  assert (this->contains(e));
130  assert (s <= omega); // do not create new subset ids
131  data[e] = s;
132  }
133 
139  inline void toSingleton(index e) {
140  data[e] = newSubsetId();
141  }
142 
147  void allToSingletons();
148 
153  void allToOnePartition();
154 
163 
164 
169  //bool isOnePartition(Graph& G);
170 
171 
176  //bool isSingletonPartition(Graph& G) const;
177 
183  inline void setUpperBound(index upper) {
184  this->omega = upper-1;
185  }
186 
193  inline index upperBound() const {
194  return omega+1;
195  }
196 
202  inline index lowerBound() const {
203  return 0;
204  }
205 
211  void compact(bool useTurbo = false);
212 
213 
220  inline bool contains(index e) const {
221  return (e < z) && (data[e] != none); // e is in the element index range and the entry is not empty
222  }
223 
224 
232  inline bool inSameSubset(index e1, index e2) const {
233  assert (data[e1] != none);
234  assert (data[e2] != none);
235  return (data[e1] == data[e2]);
236  }
237 
238 
244  std::vector<count> subsetSizes() const;
245 
246 
252  std::map<index, count> subsetSizeMap() const;
253 
254 
261  std::set<index> getMembers(const index s) const;
262 
263 
267  inline count numberOfElements() const {
268  return z; // z is the maximum element id
269  }
270 
271 
277  count numberOfSubsets() const;
278 
283  std::vector<index> getVector() const;
284 
285 
289  std::set<std::set<index> > getSubsets() const;
290 
291 
297  std::set<index> getSubsetIds() const;
298 
304  inline void setName(std::string name) {
305  this->name = name;
306  }
307 
308 
314  inline std::string getName() const {
315  return this->name;
316  }
317 
323  template<typename Callback> void forEntries(Callback func) const;
324 
330  template<typename Callback> void parallelForEntries(Callback handle) const;
331 
332 
333 private:
334  index z;
335  index omega;
336  std::vector<index> data;
337  std::string name;
338 
342  inline index newSubsetId() {
343  index s = ++omega;
344  return s;
345  }
346 };
347 
348 template<typename Callback>
349 inline void Partition::forEntries(Callback handle) const {
350  for (index e = 0; e < this->z; e++) {
351  handle(e, data[e]);
352  }
353 }
354 
355 template<typename Callback>
356 inline void Partition::parallelForEntries(Callback handle) const {
357  #pragma omp parallel for
358  for (index e = 0; e < this->z; e++) {
359  handle(e, this->data[e]);
360  }
361 }
362 
363 } /* namespace NetworKit */
364 
365 #endif /* PARTITION_H_ */
std::set< index > getSubsetIds() const
Get the ids of nonempty subsets.
Definition: Partition.cpp:179
index lowerBound() const
Get a lower bound for the subset ids that have been assigned.
Definition: Partition.h:202
std::string getName() const
Get the human-readable identifier.
Definition: Partition.h:314
void forEntries(Callback func) const
Iterate over all entries (node, cluster id) and execute callback function func (lambda closure)...
Definition: Partition.h:349
void toSingleton(index e)
Creates a singleton set containing the element e.
Definition: Partition.h:139
void parallelForEntries(Callback handle) const
Iterate over all entries (node, cluster id) in parallel and execute callback function handle (lambda ...
Definition: Partition.h:356
void moveToSubset(index s, index e)
Move the (previously assigned) element e to the set s.
Definition: Partition.h:128
std::vector< index > getVector() const
Get the actual vector representing the partition data structure.
Definition: Partition.cpp:151
count numberOfSubsets() const
Get the current number of sets in this partition.
Definition: Partition.cpp:70
count numberOfElements() const
Definition: Partition.h:267
uint64_t index
Typedefs.
Definition: Globals.h:20
index mergeSubsets(index s, index t)
Assigns the elements from both sets to a new set and returns the id of it.
Definition: Partition.cpp:39
bool contains(index e) const
Check if partition assigns a valid subset to the element e.
Definition: Partition.h:220
index & operator[](const index &e)
Index operator.
Definition: Partition.h:63
index extend()
Extend the data structure and create a slot for one more element.
Definition: Partition.h:92
index subsetOf(index e) const
Get the set (id) in which the element e is contained.
Definition: Partition.h:81
void allToSingletons()
Assigns every element to a singleton set.
Definition: Partition.cpp:32
Implements a partition of a set, i.e.
Definition: Partition.h:31
void compact(bool useTurbo=false)
Change subset IDs to be consecutive, starting at 0.
Definition: Partition.cpp:88
void setUpperBound(index upper)
Check if partition is a 1-partition, i.e.
Definition: Partition.h:183
std::vector< count > subsetSizes() const
Get a list of subset sizes.
Definition: Partition.cpp:119
std::map< index, count > subsetSizeMap() const
Get a map from subset id to size of the subset.
Definition: Partition.cpp:128
uint64_t count
Definition: Globals.h:21
constexpr index none
Constants.
Definition: Globals.h:28
void allToOnePartition()
Assigns every element to the same subset.
Definition: Partition.cpp:172
std::set< std::set< index > > getSubsets() const
Definition: Partition.cpp:156
void addToSubset(index s, index e)
Add a (previously unassigned) element e to the set s.
Definition: Partition.h:115
void setName(std::string name)
Set a human-readable identifier name for the instance.
Definition: Partition.h:304
bool inSameSubset(index e1, index e2) const
Check if two elements e1 and e2 belong to the same subset.
Definition: Partition.h:232
index upperBound() const
Return an upper bound for the subset ids that have been assigned.
Definition: Partition.h:193
std::set< index > getMembers(const index s) const
Get the members of the subset s.
Definition: Partition.cpp:140
Partition()
Definition: Partition.cpp:13