00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
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 )
00052 {
00053 return x;
00054 }
00055
00056 m_component[x] = find( m_component[x] );
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 );
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 }