OpenWalnut
1.4.0
|
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