OpenWalnut  1.4.0
WUnionFind.h
00001 //---------------------------------------------------------------------------
00002 //
00003 // Project: OpenWalnut ( http://www.openwalnut.org )
00004 //
00005 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
00006 // For more information see http://www.openwalnut.org/copying
00007 //
00008 // This file is part of OpenWalnut.
00009 //
00010 // OpenWalnut is free software: you can redistribute it and/or modify
00011 // it under the terms of the GNU Lesser General Public License as published by
00012 // the Free Software Foundation, either version 3 of the License, or
00013 // (at your option) any later version.
00014 //
00015 // OpenWalnut is distributed in the hope that it will be useful,
00016 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00017 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00018 // GNU Lesser General Public License for more details.
00019 //
00020 // You should have received a copy of the GNU Lesser General Public License
00021 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
00022 //
00023 //---------------------------------------------------------------------------
00024 
00025 #ifndef WUNIONFIND_H
00026 #define WUNIONFIND_H
00027 
00028 #include <set>
00029 #include <vector>
00030 
00031 #include <boost/shared_ptr.hpp>
00032 
00033 
00034 /**
00035  * Implements a very simple union-find datastructure aka disjoint_sets.
00036  * \note I know there is a boost solution on that, but I didn't get it to work and I don't know how fast it is:
00037  * http://www.boost.org/doc/libs/1_42_0/libs/disjoint_sets/disjoint_sets.html
00038  *
00039  * And you may use it like this:
00040    \verbatim
00041    typedef std::vector< SizeType >          RankVector;
00042    typedef RankVector::iterator             RankRAIter;
00043    typedef std::vector< VertexDescriptor >  ParentVector;
00044    typedef ParentVector::iterator           ParentRAIter;
00045 
00046    typedef boost::iterator_property_map< RankRAIter,
00047                                          IndexMap,
00048                                          std::iterator_traits< RankRAIter >::value_type,
00049                                          std::iterator_traits< RankRAIter >::reference > RankMap;
00050 
00051    typedef boost::iterator_property_map< ParentRAIter,
00052                                          IndexMap,
00053                                          std::iterator_traits< ParentRAIter >::value_type,
00054                                          std::iterator_traits< ParentRAIter >::reference > ParentMap;
00055 
00056    RankVector   ranks( d_numOfVertices );
00057    ParentVector parents( d_numOfVertices );
00058    boost::disjoint_sets< RankMap, ParentMap > dset( boost::make_iterator_property_map( ranks.begin(),
00059                                                                                        boost::get( boost::vertex_index, g ),
00060                                                                                        ranks[0] ),
00061                                                     boost::make_iterator_property_map( parents.begin(),
00062                                                                                        boost::get( boost::vertex_index, g ),
00063                                                                                        parents[0] )
00064                                                   );
00065 
00066    // After the disjoint set dset is construct, we can use
00067 
00068    dset.make_set( u ); // make u a set
00069    dset.link( u, v );  // u and v are belonging to the same set.
00070    dset.find_set( u ); // find the set owning u. A representative of the set is returned
00071    \endverbatim
00072  */
00073 class WUnionFind
00074 {
00075 friend class WUnionFindTest;
00076 public:
00077     /**
00078      * Creates a new union find datastructure with size elements where each
00079      * element is initialized as a single set.
00080      *
00081      * \param size Number of elements
00082      */
00083     explicit WUnionFind( size_t size );
00084 
00085     /**
00086      * Find the canonical element of the given element and do path compression
00087      *
00088      * http://en.wikipedia.org/wiki/Disjoint-set_data_structure
00089      *
00090      * depth of recursion is said to be small, therefore, recursion
00091      * works fine for large dataset, too.
00092      *
00093      * \throw WOutOfBounds If x is bigger than the number of elements available
00094      *
00095      * \param x The x'th element
00096      * \return The canonical element of that component which x is also member of
00097      */
00098     size_t find( size_t x );
00099 
00100     /**
00101      * Computes the set with maximum number of elements. If there are more than one candidate one is
00102      * picked arbitrarily.
00103      *
00104      * \return Reference to the set of indices all beloning to a set of maximal size.
00105      */
00106     boost::shared_ptr< std::set< size_t > > getMaxSet();
00107 
00108     /**
00109      * Merges two components (iow: makes a union) where the given elements are
00110      * members of.
00111      *
00112      * \throw WOutOfBounds If i or j are bigger than the number of elements available
00113      *
00114      * \param i Element of some component
00115      * \param j Element of some (maybe other) component
00116      */
00117     void merge( size_t i, size_t j );
00118 
00119 private:
00120     std::vector< size_t > m_component; //!< Stores for each index its ID
00121 };
00122 
00123 
00124 #endif  // WUNIONFIND_H