]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |