boost/pending/disjoint_sets.hpp

   1 //
   2 //=======================================================================
   3 // Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
   4 // Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
   5 //
   6 // Distributed under the Boost Software License, Version 1.0. (See
   7 // accompanying file LICENSE_1_0.txt or copy at
   8 // http://www.boost.org/LICENSE_1_0.txt)
   9 //=======================================================================
  10 //
  11 #ifndef BOOST_DISJOINT_SETS_HPP
  12 #define BOOST_DISJOINT_SETS_HPP
  13
  14 #include <vector>
  15 #include <boost/graph/properties.hpp>
  16 #include <boost/pending/detail/disjoint_sets.hpp>
  17
  18 namespace boost {
  19
  20   struct find_with_path_halving {
  21     template <class ParentPA, class Vertex>
  22     Vertex operator()(ParentPA p, Vertex v) {
  23       return detail::find_representative_with_path_halving(p, v);
  24     }
  25   };
  26
  27   struct find_with_full_path_compression {
  28     template <class ParentPA, class Vertex>
  29     Vertex operator()(ParentPA p, Vertex v){
  30       return detail::find_representative_with_full_compression(p, v);
  31     }
  32   };
  33
  34   // This is a generalized functor to provide disjoint sets operations
  35   // with "union by rank" and "path compression".  A disjoint-set data
  36   // structure maintains a collection S={S1, S2, ..., Sk} of disjoint
  37   // sets. Each set is identified by a representative, which is some
  38   // member of of the set. Sets are represented by rooted trees. Two
  39   // heuristics: "union by rank" and "path compression" are used to
  40   // speed up the operations.
  41
  42   // Disjoint Set requires two vertex properties for internal use.  A
  43   // RankPA and a ParentPA. The RankPA must map Vertex to some Integral type
  44   // (preferably the size_type associated with Vertex). The ParentPA
  45   // must map Vertex to Vertex.
  46   template <class RankPA, class ParentPA,
  47     class FindCompress = find_with_full_path_compression
  48     >
  49   class disjoint_sets {
  50     typedef disjoint_sets self;
  51
  52     inline disjoint_sets() {}
  53   public:
  54     inline disjoint_sets(RankPA r, ParentPA p)
  55       : rank(r), parent(p) {}
  56
  57     inline disjoint_sets(const self& c)
  58       : rank(c.rank), parent(c.parent) {}
  59
  60     // Make Set -- Create a singleton set containing vertex x
  61     template <class Element>
  62     inline void make_set(Element x)
  63     {
  64       put(parent, x, x);
  65       typedef typename property_traits<RankPA>::value_type R;
  66       put(rank, x, R());
  67     }
  68
  69     // Link - union the two sets represented by vertex x and y
  70     template <class Element>
  71     inline void link(Element x, Element y)
  72     {
  73       detail::link_sets(parent, rank, x, y, rep);
  74     }
  75
  76     // Union-Set - union the two sets containing vertex x and y
  77     template <class Element>
  78     inline void union_set(Element x, Element y)
  79     {
  80       link(find_set(x), find_set(y));
  81     }
  82
  83     // Find-Set - returns the Element representative of the set
  84     // containing Element x and applies path compression.
  85     template <class Element>
  86     inline Element find_set(Element x)
  87     {
  88       return rep(parent, x);
  89     }
  90
  91     template <class ElementIterator>
  92     inline std::size_t count_sets(ElementIterator first, ElementIterator last)
  93     {
  94       std::size_t count = 0;
  95       for ( ; first != last; ++first)
  96       if (get(parent, *first) == *first)
  97         ++count;
  98       return count;
  99     }
 100
 101     template <class ElementIterator>
 102     inline void normalize_sets(ElementIterator first, ElementIterator last)
 103     {
 104       for (; first != last; ++first)
 105         detail::normalize_node(parent, *first);
 106     }
 107
 108     template <class ElementIterator>
 109     inline void compress_sets(ElementIterator first, ElementIterator last)
 110     {
 111       for (; first != last; ++first)
 112         detail::find_representative_with_full_compression(parent, *first);
 113     }
 114   protected:
 115     RankPA rank;
 116     ParentPA parent;
 117     FindCompress rep;
 118   };
 119
 120
 121
 122
 123   template <class ID = identity_property_map,
 124             class InverseID = identity_property_map,
 125             class FindCompress = find_with_full_path_compression
 126             >
 127   class disjoint_sets_with_storage
 128   {
 129     typedef typename property_traits<ID>::value_type Index;
 130     typedef std::vector<Index> ParentContainer;
 131     typedef std::vector<unsigned char> RankContainer;
 132   public:
 133     typedef typename ParentContainer::size_type size_type;
 134
 135     disjoint_sets_with_storage(size_type n = 0,
 136                                ID id_ = ID(),
 137                                InverseID inv = InverseID())
 138       : id(id_), id_to_vertex(inv), rank(n, 0), parent(n)
 139     {
 140       for (Index i = 0; i < n; ++i)
 141         parent[i] = i;
 142     }
 143     // note this is not normally needed
 144     template <class Element>
 145     inline void
 146     make_set(Element x) {
 147       parent[x] = x;
 148       rank[x]   = 0;
 149     }
 150     template <class Element>
 151     inline void
 152     link(Element x, Element y)
 153     {
 154       extend_sets(x,y);
 155       detail::link_sets(&parent[0], &rank[0],
 156                         get(id,x), get(id,y), rep);
 157     }
 158     template <class Element>
 159     inline void
 160     union_set(Element x, Element y) {
 161       Element rx = find_set(x);
 162       Element ry = find_set(y);
 163       link(rx, ry);
 164     }
 165     template <class Element>
 166     inline Element find_set(Element x) {
 167       return id_to_vertex[rep(&parent[0], get(id,x))];
 168     }
 169
 170     template <class ElementIterator>
 171     inline std::size_t count_sets(ElementIterator first, ElementIterator last)
 172     {
 173       std::size_t count = 0;
 174       for ( ; first != last; ++first)
 175       if (parent[*first] == *first)
 176         ++count;
 177       return count;
 178     }
 179
 180     template <class ElementIterator>
 181     inline void normalize_sets(ElementIterator first, ElementIterator last)
 182     {
 183       for (; first != last; ++first)
 184         detail::normalize_node(&parent[0], *first);
 185     }
 186
 187     template <class ElementIterator>
 188     inline void compress_sets(ElementIterator first, ElementIterator last)
 189     {
 190       for (; first != last; ++first)
 191         detail::find_representative_with_full_compression(&parent[0],
 192                                                           *first);
 193     }
 194
 195     const ParentContainer& parents() { return parent; }
 196
 197   protected:
 198
 199     template <class Element>
 200     inline void
 201     extend_sets(Element x, Element y)
 202     {
 203       Index needed = get(id,x) > get(id,y) ? get(id,x) + 1 : get(id,y) + 1;
 204       if (needed > parent.size()) {
 205         rank.insert(rank.end(), needed - rank.size(), 0);
 206         for (Index k = parent.size(); k < needed; ++k)
 207         parent.push_back(k);
 208       }
 209     }
 210
 211     ID id;
 212     InverseID id_to_vertex;
 213     RankContainer rank;
 214     ParentContainer parent;
 215     FindCompress rep;
 216   };
 217
 218 } // namespace boost
 219
 220 #endif // BOOST_DISJOINT_SETS_HPP