source: NonGTP/Boost/boost/pending/disjoint_sets.hpp @ 857

Revision 857, 6.7 KB checked in by igarcia, 19 years ago (diff)
Line 
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
18namespace 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
Note: See TracBrowser for help on using the repository browser.