Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

DisjointSets.h
Go to the documentation of this file.
1 
32 #pragma once
33 
34 #include <cstring>
35 #include <ogdf/basic/exceptions.h>
36 
37 namespace ogdf {
38 
39 #define OGDF_DISJOINT_SETS_INTERMEDIATE_PARENT_CHECK
40 
42 enum class LinkOptions {
43  Naive = 0,
44  Index = 1,
45  Size = 2,
46  Rank = 3
47 };
48 
50 enum class CompressionOptions {
51  PathCompression = 0,
52  PathSplitting = 1,
53  PathHalving = 2,
54  Type1Reversal = 4,
55  Collapsing = 5,
56  Disabled = 6
57 };
58 
60 enum class InterleavingOptions {
61  Disabled = 0,
62  Rem = 1,
63  Tarjan = 2,
64  Type0Reversal = 3,
66 };
67 
68 namespace disjoint_sets {
69 
70 struct AnyOption {};
71 template<LinkOptions linkOption> struct LinkOption : AnyOption {};
72 template<CompressionOptions compressionOption> struct CompressionOption : AnyOption {};
73 template<InterleavingOptions interleavingOption> struct InterleavingOption : AnyOption {};
74 
75 }
76 
78 template <LinkOptions linkOption = LinkOptions::Index,
82 {
83 static_assert(interleavingOption != InterleavingOptions::Rem || linkOption == LinkOptions::Index, "Rem's Algorithm requires linking by index.");
84 static_assert(interleavingOption != InterleavingOptions::Tarjan || linkOption == LinkOptions::Rank, "Tarjan and van Leeuwen's Algorithm requires linking by rank.");
85 static_assert(interleavingOption != InterleavingOptions::Type0Reversal || linkOption == LinkOptions::Naive, "Interleaved Reversal Type 0 requires na├»ve linking.");
86 static_assert(interleavingOption != InterleavingOptions::SplittingCompression || linkOption == LinkOptions::Index, "Interleaved Path Splitting Path Compression requires linking by index.");
87 private:
88  int m_numberOfSets;
91 
92  // Arrays parents, elements, parameters, siblings map a set id to its properties.
93 
94  int *m_parents;
95  int *m_parameters;
96  int *m_siblings;
97 
98  //find
105 
106  //link
109  int link(disjoint_sets::LinkOption<LinkOptions::Size>,int set1,int set2);
110  int link(disjoint_sets::LinkOption<LinkOptions::Rank>,int set1,int set2);
111 
112  //quickUnion
118 
119 public:
121 
124  explicit DisjointSets(int maxNumberOfElements = (1<<15) )
125  : m_parents(nullptr), m_parameters(nullptr), m_siblings(nullptr)
126  {
127  init(maxNumberOfElements);
128  }
129 
130  DisjointSets(const DisjointSets&) = delete;
131 
132  DisjointSets& operator=(const DisjointSets&) = delete;
133 
135  {
136  delete[] this->m_parents;
137  delete[] this->m_parameters;
138  delete[] this->m_siblings;
139  }
140 
142  void init(int maxNumberOfElements)
143  {
144  this->m_maxNumberOfElements = maxNumberOfElements;
145  init();
146  }
147 
149  void init()
150  {
151  delete[] this->m_parents;
152  delete[] this->m_parameters;
153  delete[] this->m_siblings;
154  this->m_numberOfSets = 0;
155  this->m_numberOfElements = 0;
156  this->m_parents = new int[this->m_maxNumberOfElements];
157  this->m_parameters = (linkOption == LinkOptions::Rank || linkOption == LinkOptions::Size)
158  ? new int[this->m_maxNumberOfElements] : nullptr;
159  this->m_siblings = (compressionOption == CompressionOptions::Collapsing)
160  ? new int[this->m_maxNumberOfElements] : nullptr;
161  }
162 
164 
169  int find(int set)
170  {
171  OGDF_ASSERT(set >= 0);
174  }
175 
177 
182  int getRepresentative(int set) const
183  {
184  OGDF_ASSERT(set >= 0);
186  while (set!=m_parents[set]) set=m_parents[set];
187  return set;
188  }
189 
191 
194  int makeSet()
195  {
196  if (this->m_numberOfElements==this->m_maxNumberOfElements)
197  {
198  int *parents = this->m_parents;
199  this->m_parents = new int[this->m_maxNumberOfElements * 2];
200  memcpy(this->m_parents,parents,sizeof(int)*this->m_maxNumberOfElements);
201  delete[] parents;
202 
203  if (this->m_parameters != nullptr)
204  {
205  int *parameters = this->m_parameters;
206  this->m_parameters = new int[this->m_maxNumberOfElements*2];
207  memcpy(this->m_parameters,parameters,sizeof(int)*this->m_maxNumberOfElements);
208  delete[] parameters;
209  }
210 
211  if (this->m_siblings != nullptr)
212  {
213  int *siblings = this->m_siblings;
214  this->m_siblings = new int[this->m_maxNumberOfElements*2];
215  memcpy(this->m_siblings,siblings,sizeof(int)*this->m_maxNumberOfElements);
216  delete[] siblings;
217  }
218  this->m_maxNumberOfElements*=2;
219  }
220  this->m_numberOfSets++;
221  int id = this->m_numberOfElements++;
222  this->m_parents[id]=id;
223  //Initialize size/ rank/ sibling.
224  if (linkOption == LinkOptions::Size) this->m_parameters[id]=1;
225  else if (linkOption == LinkOptions::Rank) this->m_parameters[id]=0;
226  if (compressionOption == CompressionOptions::Collapsing) this->m_siblings[id] = -1;
227  return id;
228  }
229 
231 
235  int link(int set1, int set2)
236  {
237  OGDF_ASSERT(set1 == getRepresentative(set1));
238  OGDF_ASSERT(set2 == getRepresentative(set2));
239  if (set1==set2) return -1;
240  this->m_numberOfSets--;
241  return linkPure(set1, set2);
242  }
243 
245 
248  bool quickUnion(int set1, int set2)
249  {
250  if (set1==set2) return false;
252  m_numberOfSets -= result;
253  return result;
254  }
255 
257  int getNumberOfSets() { return m_numberOfSets; }
258 
261 
262 private:
264 
268  int linkPure(int set1, int set2)
269  {
270  int superset = link(disjoint_sets::LinkOption<linkOption>(), set1, set2);
271  //Collapse subset tree.
272  if (compressionOption == CompressionOptions::Collapsing)
273  {
274  int subset = set1 == superset ? set2 : set1;
275  int id = subset;
276  while (this->m_siblings[id] != -1)
277  {
278  id = this->m_siblings[id];
279  this->m_parents[id]=superset;
280  }
281  this->m_siblings[id] = this->m_siblings[superset];
282  this->m_siblings[superset] = subset;
283  }
284  return superset;
285  }
286 };
287 
288 
289 //find
290 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
292 {
293  int parent = m_parents[set];
294  if (set==parent)
295  {
296  return set;
297  }
298  else
299  {
301  m_parents[set]=parent;
302  return parent;
303  }
304 }
305 
306 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
308 {
309  while (set!=m_parents[set])
310  {
311  int parent = m_parents[set];
312  int grandParent = m_parents[parent];
313  m_parents[set]=grandParent;
314  set = grandParent;
315  }
316  return set;
317 }
318 
319 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
321 {
322  int parent = m_parents[set];
323  int grandParent = m_parents[parent];
324  while (parent!=grandParent)
325  {
326  m_parents[set]=grandParent;
327  set = parent;
328  parent = grandParent;
329  grandParent = m_parents[grandParent];
330  }
331  return parent;
332 }
333 
334 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
336 {
337  int root = set;
338  set = m_parents[root];
339 
340  while (set!=m_parents[set])
341  {
342  int parent = m_parents[set];
343  m_parents[set] = root;
344  set = parent;
345  }
346  m_parents[root] = set;
347  return set;
348 }
349 
350 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
352 {
353  while (set!=m_parents[set]) set=m_parents[set];
354  return set;
355 }
356 
357 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
359 {
360  return m_parents[set];
361 }
362 
363 
364 //quickUnion
365 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
369  int set1, int set2)
370 {
371 #ifdef OGDF_DISJOINT_SETS_INTERMEDIATE_PARENT_CHECK
372  if (m_parents[set1]==m_parents[set2]) return false;
373 #endif
374  set1 = find(set1);
375  set2 = find(set2);
376  if (set1 != set2)
377  {
378  linkPure(set1,set2);
379  return true;
380  }
381  return false;
382 }
383 
384 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
388  int set1, int set2)
389 {
390 #ifdef OGDF_DISJOINT_SETS_INTERMEDIATE_PARENT_CHECK
391  if (m_parents[set1]==m_parents[set2]) return false;
392 #endif
393  int root = set2;
394  int set = set2;
395  int parent = m_parents[set];
396  m_parents[set]=root;
397  while (set != parent)
398  {
399  if (parent == set1)
400  {
401  m_parents[root]=set1;
402  return false;
403  }
404  set = parent;
405  parent = m_parents[set];
406  m_parents[set]=root;
407  }
408 
409  set = set1;
410  parent = m_parents[set];
411  while (true)
412  {
413  if (parent == root) return false;
414  m_parents[set] = root;
415  if (parent == set){
416  return true;
417  }
418  set = parent;
419  parent = m_parents[set];
420  }
421 }
422 
423 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
427  int set1, int set2)
428 {
429  int r_x = set1; int r_y = set2;
430  int p_r_x =m_parents[r_x];
431  int p_r_y =m_parents[r_y];
432  while (p_r_x != p_r_y)
433  {
434  if (p_r_x < p_r_y)
435  {
436  if (r_x == p_r_x)
437  {
438  m_parents[r_x]=p_r_y;
439  return true;
440  }
441  m_parents[r_x]=p_r_y;
442  r_x = p_r_x;
443  p_r_x = m_parents[r_x];
444  }
445  else
446  {
447  if (r_y == p_r_y)
448  {
449  m_parents[r_y]=p_r_x;
450  return true;
451  }
452  m_parents[r_y]=p_r_x;
453  r_y = p_r_y;
454  p_r_y = m_parents[r_y];
455  }
456  }
457  return false;
458 }
459 
460 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
464  int set1, int set2)
465 {
466 #ifdef OGDF_DISJOINT_SETS_INTERMEDIATE_PARENT_CHECK
467  if (m_parents[set1]==m_parents[set2]) return false;
468 #endif
469  int set = set1;
470 
471  if (set1 < set2)
472  {
473  set = set2;
474  set2 = set1;
475  set1 = set;
476  }
477 
479  set = m_parents[set];
480  int parent = m_parents[set];
481  int grandParent = m_parents[parent];
482  while (parent!=grandParent)
483  {
484  m_parents[set]=grandParent;
485  set = parent;
486  parent = grandParent;
487  grandParent = m_parents[grandParent];
488  }
489  m_parents[set1]=parent;
490  int root = parent;
491 
493  set = set2;
494  parent = m_parents[set];
495  while (true)
496  {
497  if (parent < root)
498  {
499  m_parents[set]=root;
500  if (set == parent){
501  return true;
502  }
503  set=parent;
504  parent = m_parents[set];
505  }
506  else if (parent > root)
507  {
508  m_parents[root]=parent;
509  m_parents[set1]=parent;
510  m_parents[set2]=parent;
511  return true;
512  }
513  else return false;
514  }
515 }
516 
517 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
521  int set1, int set2)
522 {
523  int r_x = set1; int r_y = set2;
524  int p_r_x = m_parents[r_x];
525  int p_r_y = m_parents[r_y];
526  while (p_r_x != p_r_y)
527  {
528  if (m_parameters[p_r_x]<=m_parameters[p_r_y])
529  {
530  if (r_x==p_r_x)
531  {
532  if (m_parameters[p_r_x] == m_parameters[p_r_y]
533  && p_r_y == m_parents[p_r_y])
534  {
535  m_parameters[p_r_y]++;
536  }
537  m_parents[r_x]=m_parents[p_r_y];
538  return true;
539  }
540  m_parents[r_x]=p_r_y;
541  r_x = p_r_x;
542  p_r_x = m_parents[r_x];
543  }
544  else
545  {
546  if (r_y==p_r_y)
547  {
548  m_parents[r_y]=m_parents[p_r_x];
549  return true;
550  }
551  m_parents[r_y]=p_r_x;
552  r_y = p_r_y;
553  p_r_y = m_parents[r_y];
554  }
555  }
556  return false;
557 }
558 
559 
560 //link
561 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
563 {
564  if (set1<set2)
565  {
566  m_parents[set1]=set2;
567  return set2;
568  }
569  else
570  {
571  m_parents[set2]=set1;
572  return set1;
573  }
574 }
575 
576 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
578 {
579  int parameter1 = m_parameters[set1];
580  int parameter2 = m_parameters[set2];
581 
582  if (parameter1<parameter2)
583  {
584  m_parents[set1]=set2;
585  return set2;
586  }
587  else if (parameter1>parameter2)
588  {
589  m_parents[set2]=set1;
590  return set1;
591  }
592  else
593  {
594  m_parents[set1]=set2;
595  m_parameters[set2]++;
596  return set2;
597  }
598 }
599 
600 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
602 {
603  int parameter1 = m_parameters[set1];
604  int parameter2 = m_parameters[set2];
605 
606  if (parameter1<parameter2)
607  {
608  m_parents[set1]=set2;
609  m_parameters[set2]+=parameter1;
610  return set2;
611  }
612  else
613  {
614  m_parents[set2]=set1;
615  m_parameters[set1]+=parameter2;
616  return set1;
617  }
618 }
619 
620 template <LinkOptions linkOption, CompressionOptions compressionOption, InterleavingOptions interleavingOption>
622 {
623  m_parents[set1]=set2;
624  return set2;
625 }
626 
627 }
ogdf
The namespace for all OGDF objects.
Definition: AugmentationModule.h:36
ogdf::DisjointSets::m_numberOfElements
int m_numberOfElements
Current number of elements.
Definition: DisjointSets.h:89
exceptions.h
Definition of exception classes.
ogdf::DisjointSets::~DisjointSets
~DisjointSets()
Definition: DisjointSets.h:134
OGDF_ASSERT
#define OGDF_ASSERT(expr)
Assert condition expr. See doc/build.md for more information.
Definition: basic.h:41
ogdf::DisjointSets::m_maxNumberOfElements
int m_maxNumberOfElements
Maximum number of elements (array size) adjusted dynamically.
Definition: DisjointSets.h:90
ogdf::DisjointSets::find
int find(disjoint_sets::CompressionOption< CompressionOptions::PathCompression >, int set)
Definition: DisjointSets.h:291
ogdf::InterleavingOptions::Type0Reversal
@ Type0Reversal
Interleaved Reversal of Type 0 (only compatible with LinkOptions::Naive)
ogdf::disjoint_sets::AnyOption
Definition: DisjointSets.h:70
ogdf::disjoint_sets::CompressionOption
Definition: DisjointSets.h:72
ogdf::CompressionOptions::PathSplitting
@ PathSplitting
Path Splitting (default)
ogdf::DisjointSets::makeSet
int makeSet()
Initializes a singleton set.
Definition: DisjointSets.h:194
ogdf::DisjointSets::m_parameters
int * m_parameters
Maps set id to rank/size.
Definition: DisjointSets.h:95
ogdf::LinkOptions::Naive
@ Naive
Naive Link.
ogdf::InterleavingOptions::Disabled
@ Disabled
No Interleaving (default)
ogdf::InterleavingOptions::Tarjan
@ Tarjan
Tarjan's and van Leeuwen's Algorithm (only compatible with LinkOptions::Rank)
ogdf::InterleavingOptions::Rem
@ Rem
Rem's Algorithm (only compatible with LinkOptions::Index)
ogdf::DisjointSets::init
void init()
Resets the DisjointSets structure to be empty, preserving the previous value of maxNumberOfElements.
Definition: DisjointSets.h:149
ogdf::DisjointSets::init
void init(int maxNumberOfElements)
Resets the DisjointSets structure to be empty, also changing the expected number of elements.
Definition: DisjointSets.h:142
ogdf::DisjointSets::link
int link(disjoint_sets::LinkOption< LinkOptions::Naive >, int set1, int set2)
Definition: DisjointSets.h:621
ogdf::DisjointSets::operator=
DisjointSets & operator=(const DisjointSets &)=delete
ogdf::LinkOptions::Rank
@ Rank
Link by rank.
ogdf::DisjointSets
A Union/Find data structure for maintaining disjoint sets.
Definition: DisjointSets.h:81
ogdf::DisjointSets::m_siblings
int * m_siblings
Maps set id to sibling set id.
Definition: DisjointSets.h:96
ogdf::DisjointSets::getNumberOfSets
int getNumberOfSets()
Returns the current number of disjoint sets.
Definition: DisjointSets.h:257
ogdf::LinkOptions
LinkOptions
Defines options for linking two sets.
Definition: DisjointSets.h:42
ogdf::DisjointSets::getNumberOfElements
int getNumberOfElements()
Returns the current number of elements.
Definition: DisjointSets.h:260
ogdf::DisjointSets::quickUnion
bool quickUnion(int set1, int set2)
Unions the maximal disjoint sets containing set1 and set2.
Definition: DisjointSets.h:248
ogdf::DisjointSets::find
int find(int set)
Returns the id of the largest superset of set and compresses the path according to CompressionOptions...
Definition: DisjointSets.h:169
ogdf::CompressionOptions::PathCompression
@ PathCompression
Path Compression.
ogdf::InterleavingOptions
InterleavingOptions
Defines options for interleaving find/link operations in quickUnion.
Definition: DisjointSets.h:60
ogdf::LinkOptions::Index
@ Index
Link by index (default)
ogdf::CompressionOptions::Type1Reversal
@ Type1Reversal
Reversal of type 1.
ogdf::DisjointSets::DisjointSets
DisjointSets(int maxNumberOfElements=(1<< 15))
Creates an empty DisjointSets structure.
Definition: DisjointSets.h:124
ogdf::disjoint_sets::InterleavingOption
Definition: DisjointSets.h:73
ogdf::DisjointSets::quickUnion
bool quickUnion(disjoint_sets::LinkOption< LinkOptions::Index >, disjoint_sets::InterleavingOption< InterleavingOptions::Rem >, int set1, int set2)
Definition: DisjointSets.h:425
ogdf::DisjointSets::m_parents
int * m_parents
Maps set id to parent set id.
Definition: DisjointSets.h:94
ogdf::DisjointSets::link
int link(int set1, int set2)
Unions set1 and set2.
Definition: DisjointSets.h:235
ogdf::CompressionOptions
CompressionOptions
Defines options for compression search paths.
Definition: DisjointSets.h:50
ogdf::LinkOptions::Size
@ Size
Link by size.
ogdf::CompressionOptions::PathHalving
@ PathHalving
Path Halving.
ogdf::CompressionOptions::Disabled
@ Disabled
No Compression.
ogdf::DisjointSets::getRepresentative
int getRepresentative(int set) const
Returns the id of the largest superset of set.
Definition: DisjointSets.h:182
ogdf::CompressionOptions::Collapsing
@ Collapsing
Collapsing.
ogdf::DisjointSets::m_numberOfSets
int m_numberOfSets
Current number of disjoint sets.
Definition: DisjointSets.h:83
ogdf::InterleavingOptions::SplittingCompression
@ SplittingCompression
Interleaved Path Splitting Path Compression (only compatible with LinkOptions::Index)
ogdf::DisjointSets::linkPure
int linkPure(int set1, int set2)
Unions set1 and set2 w/o decreasing the numberOfSets.
Definition: DisjointSets.h:268
Minisat::Internal::find
static bool find(V &ts, const T &t)
Definition: Alg.h:47