FST  openfst-1.8.2 OpenFst Library
union-find.h
Go to the documentation of this file.
2 //
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
8 //
9 // Unless required by applicable law or agreed to in writing, software
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14 //
15 // See www.openfst.org for extensive documentation on this weighted
16 // finite-state transducer library.
17 //
18 // Union-find algorithm for dense sets of non-negative integers, implemented
19 // using disjoint tree forests with rank heuristics and path compression.
20
21 #ifndef FST_UNION_FIND_H_
22 #define FST_UNION_FIND_H_
23
24 #include <vector>
25
26 namespace fst {
27
28 // Union-Find algorithm for dense sets of non-negative integers.
29 template <class T>
30 class UnionFind {
31  public:
32  // Creates a disjoint set forest for the range [0; max); 'fail' is a value
33  // indicating that an element hasn't been initialized using MakeSet(...).
34  // The upper bound of the range can be reset (increased) using MakeSet(...).
35  UnionFind(T max, T fail) : parent_(max, fail), rank_(max), fail_(fail) {}
36
37  // Finds the representative of the set 'item' belongs to, performing path
38  // compression if necessary.
39  T FindSet(T item) {
40  if (item >= parent_.size() || item == fail_ || parent_[item] == fail_) {
41  return fail_;
42  }
43  T root = item;
44  while (root != parent_[root]) {
45  root = parent_[root];
46  }
47  while (item != parent_[item]) {
48  T parent = parent_[item];
49  parent_[item] = root;
50  item = parent;
51  }
52  return root;
53  }
54
55  // Creates the (destructive) union of the sets x and y belong to.
56  void Union(T x, T y) { Link(FindSet(x), FindSet(y)); }
57
58  // Initialization of an element: creates a singleton set containing 'item'.
59  // The range [0; max) is reset if item >= max.
60  T MakeSet(T item) {
61  if (item >= parent_.size()) {
62  // New value in parent_ should be initialized to fail_.
63  const auto nitem = item > 0 ? 2 * item : 2;
64  parent_.resize(nitem, fail_);
65  rank_.resize(nitem);
66  }
67  parent_[item] = item;
68  return item;
69  }
70
71  // Initialization of all elements starting from 0 to max - 1 to distinct sets.
72  void MakeAllSet(T max) {
73  parent_.resize(max);
74  for (T item = 0; item < max; ++item) parent_[item] = item;
75  }
76
77  // For testing only.
78  const T &Parent(const T &x) const { return parent_[x]; }
79
80  private:
81  // Links trees rooted in 'x' and 'y'.
82  void Link(T x, T y) {
83  if (x == y) return;
84  if (rank_[x] > rank_[y]) {
85  parent_[y] = x;
86  } else {
87  parent_[x] = y;
88  if (rank_[x] == rank_[y]) {
89  ++rank_[y];
90  }
91  }
92  }
93
94  UnionFind(const UnionFind &) = delete;
95
96  UnionFind &operator=(const UnionFind &) = delete;
97
98  std::vector<T> parent_; // Parent nodes.
99  std::vector<int> rank_; // Rank of an element = min. depth in tree.
100  T fail_; // Value indicating lookup failure.
101 };
102
103 } // namespace fst
104
105 #endif // FST_UNION_FIND_H_
void MakeAllSet(T max)
Definition: union-find.h:72
const T & Parent(const T &x) const
Definition: union-find.h:78
UnionFind(T max, T fail)
Definition: union-find.h:35
void Union(T x, T y)
Definition: union-find.h:56
T MakeSet(T item)
Definition: union-find.h:60
T FindSet(T item)
Definition: union-find.h:39