Open
Graph Drawing
Framework

 v. 2023.09 (Elderberry)
 

Loading...
Searching...
No Matches
DisjointSets.h
Go to the documentation of this file.
1
32#pragma once
33
35
36#include <cstring>
37
38namespace ogdf {
39
40#define OGDF_DISJOINT_SETS_INTERMEDIATE_PARENT_CHECK
41
43enum class LinkOptions {
44 Naive = 0,
45 Index = 1,
46 Size = 2,
47 Rank = 3
48};
49
52 PathCompression = 0,
53 PathSplitting = 1,
54 PathHalving = 2,
55 Type1Reversal = 4,
56 Collapsing = 5,
57 Disabled = 6
58};
59
62 Disabled = 0,
63 Rem = 1,
64 Tarjan = 2,
65 Type0Reversal = 3,
67 4
68};
69
70namespace disjoint_sets {
71
72struct AnyOption { };
73
74template<LinkOptions linkOption>
75struct LinkOption : AnyOption { };
76
77template<CompressionOptions compressionOption>
79
80template<InterleavingOptions interleavingOption>
82
83}
84
91 "Rem's Algorithm requires linking by index.");
93 "Tarjan and van Leeuwen's Algorithm requires linking by rank.");
96 "Interleaved Reversal Type 0 requires naïve linking.");
99 "Interleaved Path Splitting Path Compression requires linking by index.");
100
101private:
105
106 // Arrays parents, elements, parameters, siblings map a set id to its properties.
107
111
112 //find
119
120 //link
125
126 //quickUnion
131 int set2);
138 int set2);
139
140public:
142
149
150 DisjointSets(const DisjointSets&) = delete;
151
153
155 delete[] this->m_parents;
156 delete[] this->m_parameters;
157 delete[] this->m_siblings;
158 }
159
162 this->m_maxNumberOfElements = maxNumberOfElements;
163 init();
164 }
165
167 void init() {
168 delete[] this->m_parents;
169 delete[] this->m_parameters;
170 delete[] this->m_siblings;
171 this->m_numberOfSets = 0;
172 this->m_numberOfElements = 0;
173 this->m_parents = new int[this->m_maxNumberOfElements];
174 this->m_parameters = (linkOption == LinkOptions::Rank || linkOption == LinkOptions::Size)
175 ? new int[this->m_maxNumberOfElements]
176 : nullptr;
178 ? new int[this->m_maxNumberOfElements]
179 : nullptr;
180 }
181
183
188 int find(int set) {
189 OGDF_ASSERT(set >= 0);
192 }
193
195
200 int getRepresentative(int set) const {
201 OGDF_ASSERT(set >= 0);
203 while (set != m_parents[set]) {
204 set = m_parents[set];
205 }
206 return set;
207 }
208
210
213 int makeSet() {
214 if (this->m_numberOfElements == this->m_maxNumberOfElements) {
215 int* parents = this->m_parents;
216 this->m_parents = new int[this->m_maxNumberOfElements * 2];
217 memcpy(this->m_parents, parents, sizeof(int) * this->m_maxNumberOfElements);
218 delete[] parents;
219
220 if (this->m_parameters != nullptr) {
221 int* parameters = this->m_parameters;
222 this->m_parameters = new int[this->m_maxNumberOfElements * 2];
223 memcpy(this->m_parameters, parameters, sizeof(int) * this->m_maxNumberOfElements);
224 delete[] parameters;
225 }
226
227 if (this->m_siblings != nullptr) {
228 int* siblings = this->m_siblings;
229 this->m_siblings = new int[this->m_maxNumberOfElements * 2];
230 memcpy(this->m_siblings, siblings, sizeof(int) * this->m_maxNumberOfElements);
231 delete[] siblings;
232 }
233 this->m_maxNumberOfElements *= 2;
234 }
235 this->m_numberOfSets++;
236 int id = this->m_numberOfElements++;
237 this->m_parents[id] = id;
238 //Initialize size/ rank/ sibling.
240 this->m_parameters[id] = 1;
241 } else if (linkOption == LinkOptions::Rank) {
242 this->m_parameters[id] = 0;
243 }
245 this->m_siblings[id] = -1;
246 }
247 return id;
248 }
249
251
255 int link(int set1, int set2) {
258 if (set1 == set2) {
259 return -1;
260 }
261 this->m_numberOfSets--;
262 return linkPure(set1, set2);
263 }
264
266
269 bool quickUnion(int set1, int set2) {
270 if (set1 == set2) {
271 return false;
272 }
275 m_numberOfSets -= result;
276 return result;
277 }
278
281
284
285private:
287
291 int linkPure(int set1, int set2) {
293 //Collapse subset tree.
295 int subset = set1 == superset ? set2 : set1;
296 int id = subset;
297 while (this->m_siblings[id] != -1) {
298 id = this->m_siblings[id];
299 this->m_parents[id] = superset;
300 }
301 this->m_siblings[id] = this->m_siblings[superset];
302 this->m_siblings[superset] = subset;
303 }
304 return superset;
305 }
306};
307
308//find
309template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
312 int parent = m_parents[set];
313 if (set == parent) {
314 return set;
315 } else {
317 parent);
318 m_parents[set] = parent;
319 return parent;
320 }
321}
322
323template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
326 while (set != m_parents[set]) {
327 int parent = m_parents[set];
328 int grandParent = m_parents[parent];
329 m_parents[set] = grandParent;
330 set = grandParent;
331 }
332 return set;
333}
334
335template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
338 int parent = m_parents[set];
339 int grandParent = m_parents[parent];
340 while (parent != grandParent) {
341 m_parents[set] = grandParent;
342 set = parent;
343 parent = grandParent;
344 grandParent = m_parents[grandParent];
345 }
346 return parent;
347}
348
349template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
352 int root = set;
353 set = m_parents[root];
354
355 while (set != m_parents[set]) {
356 int parent = m_parents[set];
357 m_parents[set] = root;
358 set = parent;
359 }
360 m_parents[root] = set;
361 return set;
362}
363
364template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
367 while (set != m_parents[set]) {
368 set = m_parents[set];
369 }
370 return set;
371}
372
373template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
378
379//quickUnion
380template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
383 int set1, int set2) {
384#ifdef OGDF_DISJOINT_SETS_INTERMEDIATE_PARENT_CHECK
385 if (m_parents[set1] == m_parents[set2]) {
386 return false;
387 }
388#endif
389 set1 = find(set1);
390 set2 = find(set2);
391 if (set1 != set2) {
392 linkPure(set1, set2);
393 return true;
394 }
395 return false;
396}
397
398template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
402#ifdef OGDF_DISJOINT_SETS_INTERMEDIATE_PARENT_CHECK
403 if (m_parents[set1] == m_parents[set2]) {
404 return false;
405 }
406#endif
407 int root = set2;
408 int set = set2;
409 int parent = m_parents[set];
410 m_parents[set] = root;
411 while (set != parent) {
412 if (parent == set1) {
413 m_parents[root] = set1;
414 return false;
415 }
416 set = parent;
417 parent = m_parents[set];
418 m_parents[set] = root;
419 }
420
421 set = set1;
422 parent = m_parents[set];
423 while (true) {
424 if (parent == root) {
425 return false;
426 }
427 m_parents[set] = root;
428 if (parent == set) {
429 return true;
430 }
431 set = parent;
432 parent = m_parents[set];
433 }
434}
435
436template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
440 int r_x = set1;
441 int r_y = set2;
442 int p_r_x = m_parents[r_x];
443 int p_r_y = m_parents[r_y];
444 while (p_r_x != p_r_y) {
445 if (p_r_x < p_r_y) {
446 if (r_x == p_r_x) {
447 m_parents[r_x] = p_r_y;
448 return true;
449 }
450 m_parents[r_x] = p_r_y;
451 r_x = p_r_x;
452 p_r_x = m_parents[r_x];
453 } else {
454 if (r_y == p_r_y) {
455 m_parents[r_y] = p_r_x;
456 return true;
457 }
458 m_parents[r_y] = p_r_x;
459 r_y = p_r_y;
460 p_r_y = m_parents[r_y];
461 }
462 }
463 return false;
464}
465
466template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
470 int set2) {
471#ifdef OGDF_DISJOINT_SETS_INTERMEDIATE_PARENT_CHECK
472 if (m_parents[set1] == m_parents[set2]) {
473 return false;
474 }
475#endif
476 int set = set1;
477
478 if (set1 < set2) {
479 set = set2;
480 set2 = set1;
481 set1 = set;
482 }
483
485 set = m_parents[set];
486 int parent = m_parents[set];
487 int grandParent = m_parents[parent];
488 while (parent != grandParent) {
489 m_parents[set] = grandParent;
490 set = parent;
491 parent = grandParent;
492 grandParent = m_parents[grandParent];
493 }
494 m_parents[set1] = parent;
495 int root = parent;
496
498 set = set2;
499 parent = m_parents[set];
500 while (true) {
501 if (parent < root) {
502 m_parents[set] = root;
503 if (set == parent) {
504 return true;
505 }
506 set = parent;
507 parent = m_parents[set];
508 } else if (parent > root) {
509 m_parents[root] = parent;
510 m_parents[set1] = parent;
511 m_parents[set2] = parent;
512 return true;
513 } else {
514 return false;
515 }
516 }
517}
518
519template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
523 int r_x = set1;
524 int r_y = set2;
525 int p_r_x = m_parents[r_x];
526 int p_r_y = m_parents[r_y];
527 while (p_r_x != p_r_y) {
528 if (m_parameters[p_r_x] <= m_parameters[p_r_y]) {
529 if (r_x == p_r_x) {
530 if (m_parameters[p_r_x] == m_parameters[p_r_y] && p_r_y == m_parents[p_r_y]) {
531 m_parameters[p_r_y]++;
532 }
533 m_parents[r_x] = m_parents[p_r_y];
534 return true;
535 }
536 m_parents[r_x] = p_r_y;
537 r_x = p_r_x;
538 p_r_x = m_parents[r_x];
539 } else {
540 if (r_y == p_r_y) {
541 m_parents[r_y] = m_parents[p_r_x];
542 return true;
543 }
544 m_parents[r_y] = p_r_x;
545 r_y = p_r_y;
546 p_r_y = m_parents[r_y];
547 }
548 }
549 return false;
550}
551
552//link
553template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
556 if (set1 < set2) {
557 m_parents[set1] = set2;
558 return set2;
559 } else {
560 m_parents[set2] = set1;
561 return set1;
562 }
563}
564
565template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
568 int parameter1 = m_parameters[set1];
569 int parameter2 = m_parameters[set2];
570
571 if (parameter1 < parameter2) {
572 m_parents[set1] = set2;
573 return set2;
574 } else if (parameter1 > parameter2) {
575 m_parents[set2] = set1;
576 return set1;
577 } else {
578 m_parents[set1] = set2;
579 m_parameters[set2]++;
580 return set2;
581 }
582}
583
584template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
587 int parameter1 = m_parameters[set1];
588 int parameter2 = m_parameters[set2];
589
590 if (parameter1 < parameter2) {
591 m_parents[set1] = set2;
592 m_parameters[set2] += parameter1;
593 return set2;
594 } else {
595 m_parents[set2] = set1;
596 m_parameters[set1] += parameter2;
597 return set1;
598 }
599}
600
601template<LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
607
608}
A Union/Find data structure for maintaining disjoint sets.
bool quickUnion(int set1, int set2)
Unions the maximal disjoint sets containing set1 and set2.
int makeSet()
Initializes a singleton set.
int getRepresentative(int set) const
Returns the id of the largest superset of set.
void init()
Resets the DisjointSets structure to be empty, preserving the previous value of maxNumberOfElements.
int m_numberOfElements
Current number of elements.
bool quickUnion(disjoint_sets::LinkOption< LinkOptions::Index >, disjoint_sets::InterleavingOption< InterleavingOptions::Rem >, int set1, int set2)
int find(int set)
Returns the id of the largest superset of set and compresses the path according to CompressionOptions...
DisjointSets & operator=(const DisjointSets &)=delete
int m_numberOfSets
Current number of disjoint sets.
int getNumberOfSets()
Returns the current number of disjoint sets.
int find(disjoint_sets::CompressionOption< CompressionOptions::PathCompression >, int set)
int link(disjoint_sets::LinkOption< LinkOptions::Naive >, int set1, int set2)
DisjointSets(int maxNumberOfElements=(1<< 15))
Creates an empty DisjointSets structure.
void init(int maxNumberOfElements)
Resets the DisjointSets structure to be empty, also changing the expected number of elements.
int * m_parameters
Maps set id to rank/size.
int getNumberOfElements()
Returns the current number of elements.
int * m_parents
Maps set id to parent set id.
DisjointSets(const DisjointSets &)=delete
int link(int set1, int set2)
Unions set1 and set2.
int linkPure(int set1, int set2)
Unions set1 and set2 w/o decreasing the numberOfSets.
int * m_siblings
Maps set id to sibling set id.
int m_maxNumberOfElements
Maximum number of elements (array size) adjusted dynamically.
Definition of exception classes.
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition basic.h:41
static MultilevelBuilder * getDoubleFactoredZeroAdjustedMerger()
The namespace for all OGDF objects.
LinkOptions
Defines options for linking two sets.
@ Rank
Link by rank.
@ Naive
Naive Link.
@ Size
Link by size.
@ Index
Link by index (default)
InterleavingOptions
Defines options for interleaving find/link operations in quickUnion.
@ Type0Reversal
Interleaved Reversal of Type 0 (only compatible with LinkOptions::Naive)
@ SplittingCompression
Interleaved Path Splitting Path Compression (only compatible with LinkOptions::Index)
@ Tarjan
Tarjan's and van Leeuwen's Algorithm (only compatible with LinkOptions::Rank)
@ Disabled
No Interleaving (default)
@ Rem
Rem's Algorithm (only compatible with LinkOptions::Index)
CompressionOptions
Defines options for compression search paths.
@ PathHalving
Path Halving.
@ PathSplitting
Path Splitting (default)
@ Disabled
No Compression.
@ Type1Reversal
Reversal of type 1.
@ PathCompression
Path Compression.