OpenWalnut  1.4.0
WUnionFind.cpp
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 }