Home | History | Annotate | Download | only in lib 
      1 // union-find.h
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //      http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     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 //
     16 // \file Union-Find algorithm for dense sets of non-negative
     17 // integers. Implemented using disjoint tree forests with rank
     18 // heuristics and path compression.
     19 
     20 #ifndef __fst_union_find_inl_h__
     21 #define __fst_union_find_inl_h__
     22 
     23 #include <stack>
     24 #include <vector>
     25 
     26 namespace fst {
     27 
     28 // Union-Find algorithm for dense sets of non-negative integers
     29 // (exact type: T).
     30 template <class T>
     31 class UnionFind {
     32  public:
     33   // Ctor: creates a disjoint set forest for the range [0;max).
     34   // 'fail' is a value indicating that an element hasn't been
     35   // initialized using MakeSet(...). The upper bound of the range
     36   // can be reset (increased) using MakeSet(...).
     37   UnionFind(T max, T fail)
     38       : parent_(max, fail), rank_(max), fail_(fail) { }
     39 
     40   // Finds the representative of the set 'item' belongs to.
     41   // Performs path compression if needed.
     42   T FindSet(T item) {
     43     if (item >= parent_.size()
     44         || item == fail_
     45         || parent_[item] == fail_) return fail_;
     46 
     47     CHECK(exec_stack_.empty());
     48     T *p = &parent_[item];
     49     for (; *p != item; item = *p, p = &parent_[item]) {
     50       exec_stack_.push(p);
     51     }
     52     for (; ! exec_stack_.empty(); exec_stack_.pop()) {
     53       *exec_stack_.top() = *p;
     54     }
     55     return *p;
     56   }
     57 
     58   // Creates the (destructive) union of the sets x and y belong to.
     59   void Union(T x, T y) {
     60     Link(FindSet(x), FindSet(y));
     61   }
     62 
     63   // Initialization of an element: creates a singleton set containing
     64   // 'item'. The range [0;max) is reset if item >= max.
     65   T MakeSet(T item) {
     66     if (item >= parent_.size()) {
     67       // New value in parent_ should be initialized to fail_
     68       parent_.resize(2 * item, fail_);
     69       rank_.resize(2 * item);
     70     }
     71     parent_[item] = item;
     72     return item;
     73   }
     74 
     75   // Initialization of all elements starting from 0 to max - 1 to distinct sets
     76   void MakeAllSet(T max) {
     77     parent_.resize(max);
     78     for (T item = 0; item < max; ++item) {
     79       parent_[item] = item;
     80     }
     81   }
     82 
     83  private:
     84   vector<T> parent_;      // Parent nodes.
     85   vector<int> rank_;      // Rank of an element = min. depth in tree.
     86   T fail_;                // Value indicating lookup failure.
     87   stack<T*> exec_stack_;  // Used for path compression.
     88 
     89   // Links trees rooted in 'x' and 'y'.
     90   void Link(T x, T y) {
     91     if (x == y) return;
     92 
     93     if (rank_[x] > rank_[y]) {
     94       parent_[y] = x;
     95     } else {
     96       parent_[x] = y;
     97       if (rank_[x] == rank_[y]) {
     98         ++rank_[y];
     99       }
    100     }
    101   }
    102   DISALLOW_EVIL_CONSTRUCTORS(UnionFind);
    103 };
    104 
    105 }
    106 
    107 #endif  // __fst_union_find_inl_h__
    108