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

vigra/union_find.hxx |

    00001 /************************************************************************/
    00002 /*                                                                      */
    00003 /*               Copyright 2008-2009 by Ullrich Koethe                  */
    00004 /*                                                                      */
    00005 /*    This file is part of the VIGRA computer vision library.           */
    00006 /*    The VIGRA Website is                                              */
    00007 /*        http://hci.iwr.uni-heidelberg.de/vigra/                       */
    00008 /*    Please direct questions, bug reports, and contributions to        */
    00009 /*        ullrich.koethe@iwr.uni-heidelberg.de    or                    */
    00010 /*        vigra@informatik.uni-hamburg.de                               */
    00011 /*                                                                      */
    00012 /*    Permission is hereby granted, free of charge, to any person       */
    00013 /*    obtaining a copy of this software and associated documentation    */
    00014 /*    files (the "Software"), to deal in the Software without           */
    00015 /*    restriction, including without limitation the rights to use,      */
    00016 /*    copy, modify, merge, publish, distribute, sublicense, and/or      */
    00017 /*    sell copies of the Software, and to permit persons to whom the    */
    00018 /*    Software is furnished to do so, subject to the following          */
    00019 /*    conditions:                                                       */
    00020 /*                                                                      */
    00021 /*    The above copyright notice and this permission notice shall be    */
    00022 /*    included in all copies or substantial portions of the             */
    00023 /*    Software.                                                         */
    00024 /*                                                                      */
    00025 /*    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND    */
    00026 /*    EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES   */
    00027 /*    OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND          */
    00028 /*    NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT       */
    00029 /*    HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,      */
    00030 /*    WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING      */
    00031 /*    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR     */
    00032 /*    OTHER DEALINGS IN THE SOFTWARE.                                   */
    00033 /*                                                                      */
    00034 /************************************************************************/
    00035
    00036
    00037 #ifndef VIGRA_UNION_FIND_HXX
    00038 #define VIGRA_UNION_FIND_HXX
    00039
    00040 #include "config.hxx"
    00041 #include "error.hxx"
    00042 #include "array_vector.hxx"
    00043
    00044 namespace vigra {
    00045
    00046 namespace detail {
    00047
    00048 template <class T>
    00049 class UnionFindArray
    00050 {
    00051     typedef typename ArrayVector<T>::difference_type IndexType;
    00052     mutable ArrayVector<T> labels_;
    00053
    00054   public:
    00055     UnionFindArray(T next_free_label = 1)
    00056     {
    00057         for(T k=0; k <= next_free_label; ++k)
    00058             labels_.push_back(k);
    00059     }
    00060
    00061     T nextFreeLabel() const
    00062     {
    00063         return labels_.back();
    00064     }
    00065
    00066     T find(T label) const
    00067     {
    00068         T root = label;
    00069         while(root != labels_[(IndexType)root])
    00070             root = labels_[(IndexType)root];
    00071         // path compression
    00072         while(label != root)
    00073         {
    00074             T next = labels_[(IndexType)label];
    00075             labels_[(IndexType)label] = root;
    00076             label = next;
    00077         }
    00078         return root;
    00079     }
    00080
    00081     T makeUnion(T l1, T l2)
    00082     {
    00083         l1 = find(l1);
    00084         l2 = find(l2);
    00085         if(l1 <= l2)
    00086         {
    00087             labels_[(IndexType)l2] = l1;
    00088             return l1;
    00089         }
    00090         else
    00091         {
    00092             labels_[(IndexType)l1] = l2;
    00093             return l2;
    00094         }
    00095     }
    00096
    00097     T finalizeLabel(T label)
    00098     {
    00099         if(label == (T)labels_.size()-1)
    00100         {
    00101             // indeed a new region
    00102             vigra_invariant(label < NumericTraits<T>::max(),
    00103                     "connected components: Need more labels than can be represented in the destination type.");
    00104             // create new back entry
    00105             labels_.push_back((T)labels_.size());
    00106         }
    00107         else
    00108         {
    00109             // no new label => reset the back entry of the label array
    00110             labels_.back() = (T)labels_.size()-1;
    00111         }
    00112         return label;
    00113     }
    00114
    00115     T makeNewLabel()
    00116     {
    00117         T label = labels_.back();
    00118         vigra_invariant(label < NumericTraits<T>::max(),
    00119           "connected components: Need more labels than can be represented in the destination type.");
    00120         labels_.push_back((T)labels_.size());
    00121         return label;
    00122     }
    00123
    00124     unsigned int makeContiguous()
    00125     {
    00126         // compress trees
    00127         unsigned int count = 0;
    00128         for(IndexType i=0; i<(IndexType)(labels_.size()-1); ++i)
    00129         {
    00130             if(labels_[i] == i)
    00131             {
    00132                     labels_[i] = (T)count++;
    00133             }
    00134             else
    00135             {
    00136                     labels_[i] = labels_[(IndexType)labels_[i]];
    00137             }
    00138         }
    00139         return count-1;
    00140     }
    00141
    00142     T operator[](T label) const
    00143     {
    00144         return labels_[(IndexType)label];
    00145     }
    00146 };
    00147
    00148 } // namespace detail
    00149
    00150 } // namespace vigra
    00151
    00152 #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 Nov 6 2012)