[ VIGRA Homepage | Function Index | Class Index | Namespaces | File List | Main Page ]

union_find.hxx
1 /************************************************************************/
2 /* */
3 /* Copyright 2008-2009 by Ullrich Koethe */
4 /* */
5 /* This file is part of the VIGRA computer vision library. */
6 /* The VIGRA Website is */
7 /* http://hci.iwr.uni-heidelberg.de/vigra/ */
8 /* Please direct questions, bug reports, and contributions to */
9 /* ullrich.koethe@iwr.uni-heidelberg.de or */
10 /* vigra@informatik.uni-hamburg.de */
11 /* */
12 /* Permission is hereby granted, free of charge, to any person */
13 /* obtaining a copy of this software and associated documentation */
14 /* files (the "Software"), to deal in the Software without */
15 /* restriction, including without limitation the rights to use, */
16 /* copy, modify, merge, publish, distribute, sublicense, and/or */
17 /* sell copies of the Software, and to permit persons to whom the */
18 /* Software is furnished to do so, subject to the following */
19 /* conditions: */
20 /* */
21 /* The above copyright notice and this permission notice shall be */
22 /* included in all copies or substantial portions of the */
23 /* Software. */
24 /* */
25 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND */
26 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES */
27 /* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND */
28 /* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT */
29 /* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, */
30 /* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING */
31 /* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR */
32 /* OTHER DEALINGS IN THE SOFTWARE. */
33 /* */
34 /************************************************************************/
35 
36 
37 #ifndef VIGRA_UNION_FIND_HXX
38 #define VIGRA_UNION_FIND_HXX
39 
40 #include "config.hxx"
41 #include "error.hxx"
42 #include "array_vector.hxx"
43 
44 namespace vigra {
45 
46 namespace detail {
47 
48 template <class T>
49 class UnionFindArray
50 {
51  typedef typename ArrayVector<T>::difference_type IndexType;
52  mutable ArrayVector<T> labels_;
53 
54  public:
55  UnionFindArray(T next_free_label = 1)
56  {
57  for(T k=0; k <= next_free_label; ++k)
58  labels_.push_back(k);
59  }
60 
61  T nextFreeLabel() const
62  {
63  return labels_.back();
64  }
65 
66  T find(T label) const
67  {
68  T root = label;
69  while(root != labels_[(IndexType)root])
70  root = labels_[(IndexType)root];
71  // path compression
72  while(label != root)
73  {
74  T next = labels_[(IndexType)label];
75  labels_[(IndexType)label] = root;
76  label = next;
77  }
78  return root;
79  }
80 
81  T makeUnion(T l1, T l2)
82  {
83  l1 = find(l1);
84  l2 = find(l2);
85  if(l1 <= l2)
86  {
87  labels_[(IndexType)l2] = l1;
88  return l1;
89  }
90  else
91  {
92  labels_[(IndexType)l1] = l2;
93  return l2;
94  }
95  }
96 
97  T finalizeLabel(T label)
98  {
99  if(label == (T)labels_.size()-1)
100  {
101  // indeed a new region
102  vigra_invariant(label < NumericTraits<T>::max(),
103  "connected components: Need more labels than can be represented in the destination type.");
104  // create new back entry
105  labels_.push_back((T)labels_.size());
106  }
107  else
108  {
109  // no new label => reset the back entry of the label array
110  labels_.back() = (T)labels_.size()-1;
111  }
112  return label;
113  }
114 
115  T makeNewLabel()
116  {
117  T label = labels_.back();
118  vigra_invariant(label < NumericTraits<T>::max(),
119  "connected components: Need more labels than can be represented in the destination type.");
120  labels_.push_back((T)labels_.size());
121  return label;
122  }
123 
124  unsigned int makeContiguous()
125  {
126  // compress trees
127  unsigned int count = 0;
128  for(IndexType i=0; i<(IndexType)(labels_.size()-1); ++i)
129  {
130  if(labels_[i] == i)
131  {
132  labels_[i] = (T)count++;
133  }
134  else
135  {
136  labels_[i] = labels_[(IndexType)labels_[i]];
137  }
138  }
139  return count-1;
140  }
141 
142  T operator[](T label) const
143  {
144  return labels_[(IndexType)label];
145  }
146 };
147 
148 } // namespace detail
149 
150 } // namespace vigra
151 
152 #endif // VIGRA_UNION_FIND_HXX

© Ullrich Köthe (ullrich.koethe@iwr.uni-heidelberg.de)
Heidelberg Collaboratory for Image Processing, University of Heidelberg, Germany

html generated using doxygen and Python
vigra 1.9.0 (Tue Sep 24 2013)