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 #include <algorithm> 00026 #include <map> 00027 #include <set> 00028 #include <string> 00029 #include <vector> 00030 00031 #include <boost/shared_ptr.hpp> 00032 00033 #include "../exceptions/WOutOfBounds.h" 00034 #include "WUnionFind.h" 00035 00036 WUnionFind::WUnionFind( size_t size ) 00037 : m_component( size ) 00038 { 00039 for( size_t i = 0; i < size; ++i ) 00040 { 00041 m_component[i] = i; 00042 } 00043 } 00044 00045 size_t WUnionFind::find( size_t x ) 00046 { 00047 if( x >= m_component.size() ) 00048 { 00049 throw WOutOfBounds( std::string( "Element index in UnionFind greater than overall elements!" ) ); 00050 } 00051 if( m_component[x] == x ) // we are the root 00052 { 00053 return x; 00054 } 00055 00056 m_component[x] = find( m_component[x] ); // path compression otherwise 00057 return m_component[x]; 00058 } 00059 00060 void WUnionFind::merge( size_t i, size_t j ) 00061 { 00062 if( i >= m_component.size() || j >= m_component.size() ) 00063 { 00064 throw WOutOfBounds( std::string( "Element index in UnionFind greater than overall elements!" ) ); 00065 } 00066 if( i == j ) 00067 { 00068 return; 00069 } 00070 00071 size_t ci = find( i ); 00072 size_t cj = find( j ); 00073 00074 if( ci == cj ) 00075 { 00076 return; 00077 } 00078 00079 m_component[ ci ] = cj; 00080 } 00081 00082 boost::shared_ptr< std::set< size_t > > WUnionFind::getMaxSet() 00083 { 00084 std::map< size_t, std::set< size_t > > sets; 00085 size_t maxSetSizeSoFar = 0; 00086 size_t maxSetElement = 0; 00087 for( size_t i = 0; i < m_component.size(); ++i ) 00088 { 00089 size_t cE = find( i ); // canonical Element 00090 sets[ cE ].insert( i ); 00091 if( sets[ cE ].size() > maxSetSizeSoFar ) 00092 { 00093 maxSetSizeSoFar = sets[ cE ].size(); 00094 maxSetElement = cE; 00095 } 00096 } 00097 return boost::shared_ptr< std::set< size_t > >( new std::set< size_t >( sets[ maxSetElement ] ) ); 00098 }