UnionFind.cpp
Go to the documentation of this file.
1 #include "UnionFind.h"
2
4 {
5  UnionFind::UnionFind(std::size_t n)
6  {
7  rank.reserve(n);
8  parent.reserve(n);
9  for (std::size_t i = 0; i < n; i++)
10  {
11  rank.push_back(0);
12  parent.push_back(i);
13  }
14  }
15
16  std::size_t
17  UnionFind::find(std::size_t x)
18  {
19  // Finds the representative of the set
20  // that x is an element of
21  if (parent[x] != x)
22  {
23
24  // if x is not the parent of itself
25  // Then x is not the representative of
26  // his set,
27  parent[x] = find(parent[x]);
28
29  // so we recursively call Find on its parent
30  // and move i's node directly under the
31  // representative of this set
32  }
33
34  return parent[x];
35  }
36
37  void
38  UnionFind::unite(std::size_t a, std::size_t b)
39  {
40  // Find current sets of x and y
41  std::size_t xset = find(a);
42  std::size_t yset = find(b);
43
44  // If they are already in same set
45  if (xset == yset)
46  return;
47
48  // Put smaller ranked item under
49  // bigger ranked item if ranks are
50  // different
51  if (rank[xset] < rank[yset])
52  {
53  parent[xset] = yset;
54  }
55  else if (rank[xset] > rank[yset])
56  {
57  parent[yset] = xset;
58  }
59
60  // If ranks are same, then increment
61  // rank.
62  else
63  {
64  parent[yset] = xset;
65  rank[xset] = rank[xset] + 1;
66  }
67  }
68
69
UnionFind.h
void unite(std::size_t a, std::size_t b)
unite the sets of the elements a and b
Definition: UnionFind.cpp:38
armarx::ctrlutil::a
double a(double t, double a0, double j)
Definition: CtrlUtil.h:45