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 <iterator>
00027 #include <fstream>
00028 #include <map>
00029 #include <set>
00030 #include <sstream>
00031 #include <vector>
00032
00033 #include "../exceptions/WOutOfBounds.h"
00034 #include "../WAssert.h"
00035 #include "../WLogger.h"
00036 #include "../WStringUtils.h"
00037 #include "WDendrogram.h"
00038
00039
00040 boost::shared_ptr< WPrototyped > WDendrogram::m_prototype = boost::shared_ptr< WPrototyped >();
00041
00042 boost::shared_ptr< WPrototyped > WDendrogram::getPrototype()
00043 {
00044 if( !m_prototype )
00045 {
00046 m_prototype = boost::shared_ptr< WPrototyped >( new WDendrogram() );
00047 }
00048 return m_prototype;
00049 }
00050
00051 WDendrogram::WDendrogram()
00052 : WTransferable(),
00053 m_parents( 0 ),
00054 m_heights( 0 )
00055 {
00056 }
00057
00058 WDendrogram::WDendrogram( size_t n )
00059 : WTransferable()
00060 {
00061 reset( n );
00062 }
00063
00064 void WDendrogram::reset( size_t n )
00065 {
00066 WAssert( n > 0, "A Dendrogram for an empty set of objects was created which makes no sence, if your really need it implement it!" );
00067 m_heights.resize( n - 1, 0.0 );
00068 m_parents.reserve( 2 * n - 1 );
00069 m_parents.resize( n, 0 );
00070 }
00071
00072 void WDendrogram::checkAndThrowExceptionIfUsedUninitialized( std::string caller ) const
00073 {
00074 if( m_parents.empty() )
00075 {
00076 throw WOutOfBounds( "Accessed an empty WDendrogam via a call to a memeber function: " + caller + " which needs access to elements." );
00077 }
00078 }
00079
00080 size_t WDendrogram::merge( size_t i, size_t j, double height )
00081 {
00082 checkAndThrowExceptionIfUsedUninitialized( "merge(...)" );
00083
00084 #ifdef DEBUG
00085 std::stringstream errMsg;
00086 errMsg << "Bug: n=" << m_heights.size() << " many leafs can lead maximal to 2n-1 many nodes in a tree but this was violated now!" << std::endl;
00087 WAssert( m_parents.size() != 2 * m_heights.size() + 1, errMsg.str() );
00088 #endif
00089
00090 m_parents.push_back( m_parents.size() );
00091
00092 m_heights[ m_parents.size() - 2 - m_heights.size() ] = height;
00093 m_parents[i] = m_parents.back();
00094 m_parents[j] = m_parents.back();
00095
00096 return m_parents.size() - 1;
00097 }
00098
00099 std::string WDendrogram::toString() const
00100 {
00101 checkAndThrowExceptionIfUsedUninitialized( "toString()" );
00102
00103 std::stringstream result;
00104 std::map< size_t, std::vector< size_t > > childsOfInnerNodes;
00105 std::map< size_t, std::vector< size_t > > preds;
00106 std::vector< size_t > level( 2 * m_heights.size() + 1, 0 );
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116 for( size_t i = 0; i < m_heights.size() + 1; ++i )
00117 {
00118 result << "(0, (" << i << ",))" << std::endl;
00119 childsOfInnerNodes[ m_parents[i] ].push_back( i );
00120 preds[ m_parents[i] ].push_back( i );
00121 }
00122 for( size_t i = m_heights.size() + 1; i < 2 * m_heights.size() + 1; ++i )
00123 {
00124
00125
00126
00127
00128
00129
00130 size_t left = *( preds[ i ].begin() );
00131 size_t right = *( preds[ i ].rbegin() );
00132 level[i] = std::max( level[left], level[right] ) + 1;
00133 if( i != m_parents[i] )
00134 {
00135 preds[ m_parents[ i ] ].push_back( i );
00136 childsOfInnerNodes[ m_parents[i] ].reserve( childsOfInnerNodes[ m_parents[i] ].size() + childsOfInnerNodes[i].size() );
00137 childsOfInnerNodes[ m_parents[i] ].insert( childsOfInnerNodes[ m_parents[i] ].end(), childsOfInnerNodes[i].begin(),
00138 childsOfInnerNodes[i].end() );
00139 }
00140 result << "(" << level[i] << ", (";
00141 size_t numElements = childsOfInnerNodes[i].size();
00142 for( std::vector< size_t >::const_iterator cit = childsOfInnerNodes[i].begin(); cit != childsOfInnerNodes[i].end(); ++cit )
00143 {
00144 if( numElements == 1 )
00145 {
00146 result << *cit << "), ";
00147 }
00148 else
00149 {
00150 result << *cit << ", ";
00151 }
00152 numElements -= 1;
00153 }
00154
00155
00156
00157
00158 result << "(" << left << ", " << right << "), " << m_heights[ i - m_heights.size() - 1 ] << ")" << std::endl;
00159 }
00160
00161 return result.str();
00162 }