← Back to branch summary

~ubuntu-branches/ubuntu/warty/aqsis/warty

« back to all changes in this revision

Viewing changes to boost/boost/pending/disjoint_sets.hpp

  • Committer: Bazaar Package Importer
  • Author(s): LaMont Jones
  • Date: 2004-08-24 07:25:04 UTC
  • Revision ID: james.westby@ubuntu.com-20040824072504-zf993vnevvisdsvb
Tags: upstream-0.9.1
Import upstream version 0.9.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
boost/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
// This file is part of the Generic Graph Component Library
 
7
//
 
8
// You should have received a copy of the License Agreement for the
 
9
// Generic Graph Component Library along with the software;  see the
 
10
// file LICENSE.  If not, contact Office of Research, University of Notre
 
11
// Dame, Notre Dame, IN  46556.
 
12
//
 
13
// Permission to modify the code and to distribute modified code is
 
14
// granted, provided the text of this NOTICE is retained, a notice that
 
15
// the code was modified is included with the above COPYRIGHT NOTICE and
 
16
// with the COPYRIGHT NOTICE in the LICENSE file, and that the LICENSE
 
17
// file is distributed with the modified code.
 
18
//
 
19
// LICENSOR MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR IMPLIED.
 
20
// By way of example, but not limitation, Licensor MAKES NO
 
21
// REPRESENTATIONS OR WARRANTIES OF MERCHANTABILITY OR FITNESS FOR ANY
 
22
// PARTICULAR PURPOSE OR THAT THE USE OF THE LICENSED SOFTWARE COMPONENTS
 
23
// OR DOCUMENTATION WILL NOT INFRINGE ANY PATENTS, COPYRIGHTS, TRADEMARKS
 
24
// OR OTHER RIGHTS.
 
25
//=======================================================================
 
26
//
 
27
#ifndef BOOST_DISJOINT_SETS_HPP
 
28
#define BOOST_DISJOINT_SETS_HPP
 
29
 
 
30
#include <vector>
 
31
#include <boost/graph/properties.hpp>
 
32
#include <boost/pending/detail/disjoint_sets.hpp>
 
33
 
 
34
namespace boost {
 
35
 
 
36
  struct find_with_path_halving {
 
37
    template <class ParentPA, class Vertex>
 
38
    Vertex operator()(ParentPA p, Vertex v) { 
 
39
      return detail::find_representative_with_path_halving(p, v);
 
40
    }
 
41
  };
 
42
 
 
43
  struct find_with_full_path_compression {
 
44
    template <class ParentPA, class Vertex>
 
45
    Vertex operator()(ParentPA p, Vertex v){
 
46
      return detail::find_representative_with_full_compression(p, v);
 
47
    }
 
48
  };
 
49
 
 
50
  // This is a generalized functor to provide disjoint sets operations
 
51
  // with "union by rank" and "path compression".  A disjoint-set data
 
52
  // structure maintains a collection S={S1, S2, ..., Sk} of disjoint
 
53
  // sets. Each set is identified by a representative, which is some
 
54
  // member of of the set. Sets are represented by rooted trees. Two
 
55
  // heuristics: "union by rank" and "path compression" are used to
 
56
  // speed up the operations.
 
57
 
 
58
  // Disjoint Set requires two vertex properties for internal use.  A
 
59
  // RankPA and a ParentPA. The RankPA must map Vertex to some Integral type
 
60
  // (preferably the size_type associated with Vertex). The ParentPA
 
61
  // must map Vertex to Vertex.
 
62
  template <class RankPA, class ParentPA,
 
63
    class FindCompress = find_with_full_path_compression
 
64
    >
 
65
  class disjoint_sets {
 
66
    typedef disjoint_sets self;
 
67
    
 
68
    inline disjoint_sets() {}
 
69
  public:
 
70
    inline disjoint_sets(RankPA r, ParentPA p) 
 
71
      : rank(r), parent(p) {}
 
72
 
 
73
    inline disjoint_sets(const self& c) 
 
74
      : rank(c.rank), parent(c.parent) {}
 
75
    
 
76
    // Make Set -- Create a singleton set containing vertex x
 
77
    template <class Element>
 
78
    inline void make_set(Element x)
 
79
    {
 
80
      put(parent, x, x);
 
81
      typedef typename property_traits<RankPA>::value_type R;
 
82
      put(rank, x, R());
 
83
    }
 
84
    
 
85
    // Link - union the two sets represented by vertex x and y
 
86
    template <class Element>
 
87
    inline void link(Element x, Element y)
 
88
    {
 
89
      detail::link_sets(parent, rank, x, y, rep);
 
90
    }
 
91
    
 
92
    // Union-Set - union the two sets containing vertex x and y 
 
93
    template <class Element>
 
94
    inline void union_set(Element x, Element y)
 
95
    {
 
96
      link(find_set(x), find_set(y));
 
97
    }
 
98
    
 
99
    // Find-Set - returns the Element representative of the set
 
100
    // containing Element x and applies path compression.
 
101
    template <class Element>
 
102
    inline Element find_set(Element x)
 
103
    {
 
104
      return rep(parent, x);
 
105
    }
 
106
 
 
107
    template <class ElementIterator>
 
108
    inline std::size_t count_sets(ElementIterator first, ElementIterator last)
 
109
    {
 
110
      std::size_t count = 0;  
 
111
      for ( ; first != last; ++first)
 
112
      if (get(parent, *first) == *first)
 
113
        ++count;
 
114
      return count;
 
115
    }
 
116
 
 
117
    template <class ElementIterator>
 
118
    inline void normalize_sets(ElementIterator first, ElementIterator last)
 
119
    {
 
120
      for (; first != last; ++first) 
 
121
        detail::normalize_node(parent, *first);
 
122
    }    
 
123
    
 
124
    template <class ElementIterator>
 
125
    inline void compress_sets(ElementIterator first, ElementIterator last)
 
126
    {
 
127
      for (; first != last; ++first) 
 
128
        detail::find_representative_with_full_compression(parent, *first);
 
129
    }    
 
130
  protected:
 
131
    RankPA rank;
 
132
    ParentPA parent;
 
133
    FindCompress rep;
 
134
  };
 
135
 
 
136
 
 
137
  
 
138
 
 
139
  template <class ID = identity_property_map,
 
140
            class InverseID = identity_property_map,
 
141
            class FindCompress = find_with_full_path_compression
 
142
            >
 
143
  class disjoint_sets_with_storage
 
144
  {
 
145
    typedef typename property_traits<ID>::value_type Index;
 
146
    typedef std::vector<Index> ParentContainer;
 
147
    typedef std::vector<unsigned char> RankContainer;
 
148
  public:
 
149
    typedef typename ParentContainer::size_type size_type;
 
150
 
 
151
    disjoint_sets_with_storage(size_type n = 0,
 
152
                               ID id_ = ID(),
 
153
                               InverseID inv = InverseID())
 
154
      : id(id_), id_to_vertex(inv), rank(n, 0), parent(n)
 
155
    {
 
156
      for (Index i = 0; i < n; ++i)
 
157
        parent[i] = i;
 
158
    }
 
159
    // note this is not normally needed
 
160
    template <class Element>
 
161
    inline void 
 
162
    make_set(Element x) {
 
163
      parent[x] = x;
 
164
      rank[x]   = 0;
 
165
    }
 
166
    template <class Element>
 
167
    inline void 
 
168
    link(Element x, Element y)
 
169
    {
 
170
      extend_sets(x,y);
 
171
      detail::link_sets(&parent[0], &rank[0], 
 
172
                        get(id,x), get(id,y), rep);
 
173
    }
 
174
    template <class Element>
 
175
    inline void 
 
176
    union_set(Element x, Element y) {
 
177
      Element rx = find_set(x);
 
178
      Element ry = find_set(y);
 
179
      link(rx, ry);
 
180
    }
 
181
    template <class Element>
 
182
    inline Element find_set(Element x) {
 
183
      return id_to_vertex[rep(&parent[0], get(id,x))];
 
184
    }
 
185
 
 
186
    template <class ElementIterator>
 
187
    inline std::size_t count_sets(ElementIterator first, ElementIterator last)
 
188
    {
 
189
      std::size_t count = 0;  
 
190
      for ( ; first != last; ++first)
 
191
      if (parent[*first] == *first)
 
192
        ++count;
 
193
      return count;
 
194
    }
 
195
 
 
196
    template <class ElementIterator>
 
197
    inline void normalize_sets(ElementIterator first, ElementIterator last)
 
198
    {
 
199
      for (; first != last; ++first) 
 
200
        detail::normalize_node(&parent[0], *first);
 
201
    }    
 
202
    
 
203
    template <class ElementIterator>
 
204
    inline void compress_sets(ElementIterator first, ElementIterator last)
 
205
    {
 
206
      for (; first != last; ++first) 
 
207
        detail::find_representative_with_full_compression(&parent[0],
 
208
                                                          *first);
 
209
    }    
 
210
 
 
211
    const ParentContainer& parents() { return parent; }
 
212
 
 
213
  protected:
 
214
 
 
215
    template <class Element>
 
216
    inline void 
 
217
    extend_sets(Element x, Element y)
 
218
    {
 
219
      Index needed = get(id,x) > get(id,y) ? get(id,x) + 1 : get(id,y) + 1;
 
220
      if (needed > parent.size()) {
 
221
        rank.insert(rank.end(), needed - rank.size(), 0);
 
222
        for (Index k = parent.size(); k < needed; ++k)
 
223
        parent.push_back(k);
 
224
      } 
 
225
    }
 
226
 
 
227
    ID id;
 
228
    InverseID id_to_vertex;
 
229
    RankContainer rank;
 
230
    ParentContainer parent;
 
231
    FindCompress rep;
 
232
  };
 
233
 
 
234
} // namespace boost
 
235
 
 
236
#endif // BOOST_DISJOINT_SETS_HPP