cprover
union_find.h
Go to the documentation of this file.
1 /*******************************************************************\
2 
3 Module:
4 
5 Author: Daniel Kroening, kroening@kroening.com
6 
7 \*******************************************************************/
8 
9 
10 #ifndef CPROVER_UTIL_UNION_FIND_H
11 #define CPROVER_UTIL_UNION_FIND_H
12 
13 #include <cassert>
14 #include <vector>
15 
16 #include "numbering.h"
17 
18 // Standard union find with weighting and path compression.
19 // See http://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
20 
21 // NOLINTNEXTLINE(readability/identifiers)
23 {
24 public:
25  // NOLINTNEXTLINE(readability/identifiers)
26  typedef std::size_t size_type;
27 
28 protected:
29  struct nodet
30  {
31  size_type count; // set size
33 
34  // constructs a root node
35  explicit nodet(size_type index):count(1), parent(index)
36  {
37  }
38  };
39 
40  // This is mutable to allow path compression in find().
41  mutable std::vector<nodet> nodes;
42 
43 public:
44  // merge the sets 'a' and 'b'
45  void make_union(size_type a, size_type b);
46 
47  // find the root of the set 'a' belongs to
48  size_type find(size_type a) const;
49 
50  // Makes 'this' the union-find with the following:
51  // any union in 'this' will be present in both source sets,
52  // i.e., this is the strongest implication of the two
53  // data structures.
54  void intersection(const unsigned_union_find &other);
55 
56  // remove from any sets
57  void isolate(size_type a);
58 
60  {
61  other.nodes.swap(nodes);
62  }
63 
65  {
66  // We only enlarge. Shrinking is yet to be implemented.
67  assert(nodes.size()<=size);
68  nodes.reserve(size);
69  while(nodes.size()<size)
70  nodes.push_back(nodet(nodes.size()));
71  }
72 
73  void clear()
74  {
75  nodes.clear();
76  }
77 
78  // is 'a' a root?
79  bool is_root(size_type a) const
80  {
81  if(a>=size())
82  return true;
83  // a root is its own parent
84  return nodes[a].parent==a;
85  }
86 
87  // are 'a' and 'b' in the same set?
88  bool same_set(size_type a, size_type b) const
89  {
90  return find(a)==find(b);
91  }
92 
93  // total number of elements
94  size_type size() const
95  {
96  return nodes.size();
97  }
98 
99  // size of the set that 'a' is in
101  {
102  if(a>=size())
103  return 1;
104  return nodes[find(a)].count;
105  }
106 
107  // make the array large enough to contain 'a'
109  {
110  if(a>=size())
111  resize(a+1);
112  }
113 
114  // number of disjoint sets
116  {
117  size_type c=0;
118  for(size_type i=0; i<nodes.size(); i++)
119  if(is_root(i))
120  c++;
121  return c;
122  }
123 
124  // makes 'new_root' the root of the set 'old'
125  void re_root(size_type old, size_type new_root);
126 
127  // find a different member of the same set
129 };
130 
131 template <typename T>
132 // NOLINTNEXTLINE(readability/identifiers)
133 class union_find final
134 {
137 
138  // NOLINTNEXTLINE(readability/identifiers)
140 
141 public:
142  // NOLINTNEXTLINE(readability/identifiers)
144  // NOLINTNEXTLINE(readability/identifiers)
146  // NOLINTNEXTLINE(readability/identifiers)
148 
149  // true == already in same set
150  bool make_union(const T &a, const T &b)
151  {
152  size_type na=number(a), nb=number(b);
153  bool is_union=find_number(na)==find_number(nb);
154  uuf.make_union(na, nb);
155  return is_union;
156  }
157 
158  // true == already in same set
160  typename numbering<T>::const_iterator it_b)
161  {
162  size_type na=it_a-numbers.begin(), nb=it_b-numbers.begin();
163  bool is_union=find_number(na)==find_number(nb);
164  uuf.make_union(na, nb);
165  return is_union;
166  }
167 
168  // are 'a' and 'b' in the same set?
169  bool same_set(const T &a, const T &b) const
170  {
173 
174  if(na && nb)
175  return uuf.same_set(*na, *nb);
176  if(!na && !nb)
177  return a==b;
178  return false;
179  }
180 
181  // are 'a' and 'b' in the same set?
183  typename numbering<T>::const_iterator it_b) const
184  {
185  return uuf.same_set(it_a-numbers.begin(), it_b-numbers.begin());
186  }
187 
188  const T &find(typename numbering<T>::const_iterator it) const
189  {
190  return numbers[find_number(it-numbers.begin())];
191  }
192 
193  const T &find(const T &a)
194  {
195  return numbers[find_number(number(a))];
196  }
197 
199  {
200  return find_number(it-numbers.begin());
201  }
202 
204  {
205  return uuf.find(a);
206  }
207 
208  size_type find_number(const T &a)
209  {
210  return uuf.find(number(a));
211  }
212 
213  bool is_root_number(size_type a) const
214  {
215  return uuf.is_root(a);
216  }
217 
218  bool is_root(const T &a) const
219  {
220  number_type na;
221  if(numbers.get_number(a, na))
222  return true; // not found, it's a root
223  else
224  return uuf.is_root(na);
225  }
226 
227  bool is_root(typename numbering<T>::const_iterator it) const
228  {
229  return uuf.is_root(it-numbers.begin());
230  }
231 
232  size_type number(const T &a)
233  {
234  size_type n=numbers.number(a);
235 
236  if(n>=uuf.size())
237  uuf.resize(numbers.size());
238 
239  INVARIANT(uuf.size()==numbers.size(), "container sizes must match");
240 
241  return n;
242  }
243 
244  void clear()
245  {
246  numbers.clear();
247  uuf.clear();
248  }
249 
251  {
252  uuf.isolate(it-numbers.begin());
253  }
254 
255  void isolate(const T &a)
256  {
257  uuf.isolate(number(a));
258  }
259 
261  {
262  return numbers.get_number(a);
263  }
264 
265  size_t size() const { return numbers.size(); }
266 
267  T &operator[](size_type t) { return numbers[t]; }
268  const T &operator[](size_type t) const { return numbers[t]; }
269 
270  iterator begin() { return numbers.begin(); }
271  const_iterator begin() const { return numbers.begin(); }
272  const_iterator cbegin() const { return numbers.cbegin(); }
273 
274  iterator end() { return numbers.end(); }
275  const_iterator end() const { return numbers.end(); }
276  const_iterator cend() const { return numbers.cend(); }
277 
278 protected:
281 };
282 
283 #endif // CPROVER_UTIL_UNION_FIND_H
const_iterator cend() const
Definition: numbering.h:106
iterator end()
Definition: union_find.h:274
T & operator[](size_type t)
Definition: union_find.h:267
number_type number(const key_type &a)
Definition: numbering.h:37
const T & operator[](size_type t) const
Definition: union_find.h:268
const_iterator begin() const
Definition: union_find.h:271
size_type find_number(typename numbering< T >::const_iterator it) const
Definition: union_find.h:198
bool is_root(typename numbering< T >::const_iterator it) const
Definition: union_find.h:227
size_type size() const
Definition: numbering.h:66
const T & find(const T &a)
Definition: union_find.h:193
nodet(size_type index)
Definition: union_find.h:35
size_t size() const
Definition: union_find.h:265
void isolate(typename numbering< T >::const_iterator it)
Definition: union_find.h:250
size_type size() const
Definition: union_find.h:94
size_type count_roots() const
Definition: union_find.h:115
void resize(size_type size)
Definition: union_find.h:64
const T & find(typename numbering< T >::const_iterator it) const
Definition: union_find.h:188
numbering< T > subt
Definition: union_find.h:280
#define INVARIANT(CONDITION, REASON)
Definition: invariant.h:204
iterator begin()
Definition: union_find.h:270
void make_union(size_type a, size_type b)
Definition: union_find.cpp:13
bool is_root(size_type a) const
Definition: union_find.h:79
bool same_set(const T &a, const T &b) const
Definition: union_find.h:169
size_type find(size_type a) const
Definition: union_find.cpp:145
size_type number(const T &a)
Definition: union_find.h:232
optionalt< number_type > get_number(const key_type &a) const
Definition: numbering.h:50
numbering_typet numbers
Definition: union_find.h:136
typename data_typet::size_type size_type
Definition: numbering.h:33
iterator begin()
Definition: numbering.h:85
nonstd::optional< T > optionalt
Definition: optional.h:35
bool make_union(typename numbering< T >::const_iterator it_a, typename numbering< T >::const_iterator it_b)
Definition: union_find.h:159
size_type count(size_type a) const
Definition: union_find.h:100
void re_root(size_type old, size_type new_root)
Definition: union_find.cpp:74
numbering_typet::iterator iterator
Definition: union_find.h:145
typename data_typet::iterator iterator
Definition: numbering.h:34
typename Map::mapped_type number_type
Definition: numbering.h:24
void isolate(size_type a)
Definition: union_find.cpp:41
typename data_typet::const_iterator const_iterator
Definition: numbering.h:35
void check_index(size_type a)
Definition: union_find.h:108
void clear()
Definition: union_find.h:244
numbering< T > numbering_typet
Definition: union_find.h:135
const_iterator cbegin() const
Definition: union_find.h:272
void isolate(const T &a)
Definition: union_find.h:255
optionalt< number_type > get_number(const T &a) const
Definition: union_find.h:260
std::size_t size_type
Definition: union_find.h:26
void swap(unsigned_union_find &other)
Definition: union_find.h:59
numbering_typet::const_iterator const_iterator
Definition: union_find.h:147
size_type find_number(size_type a) const
Definition: union_find.h:203
std::vector< nodet > nodes
Definition: union_find.h:41
numbering_typet::number_type number_type
Definition: union_find.h:139
bool is_root(const T &a) const
Definition: union_find.h:218
size_type find_number(const T &a)
Definition: union_find.h:208
bool make_union(const T &a, const T &b)
Definition: union_find.h:150
const_iterator cend() const
Definition: union_find.h:276
iterator end()
Definition: numbering.h:98
void intersection(const unsigned_union_find &other)
Definition: union_find.cpp:124
unsigned_union_find uuf
Definition: union_find.h:279
bool same_set(size_type a, size_type b) const
Definition: union_find.h:88
size_type get_other(size_type a)
Definition: union_find.cpp:108
const_iterator end() const
Definition: union_find.h:275
bool same_set(typename numbering< T >::const_iterator it_a, typename numbering< T >::const_iterator it_b) const
Definition: union_find.h:182
numbering_typet::size_type size_type
Definition: union_find.h:143
const_iterator cbegin() const
Definition: numbering.h:93
bool is_root_number(size_type a) const
Definition: union_find.h:213