OpenWalnut
1.2.5
|
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 <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 // init _static_ member variable and provide a linker reference to it 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() ); // the root s always self referencing 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 // For very insane debugging only: 00109 // wlog::debug( "WDendrogram" ) << "nodes size: " << m_parents.size() << " and expeceted: " << 2 * m_heights.size() + 1; 00110 // wlog::debug( "WDendrogram" ) << "Parents-ARRAY:"; 00111 // wlog::debug( "WDendrogram" ) << m_parents; 00112 // wlog::debug( "WDendrogram" ) << "Heights-ARRAY:"; 00113 // wlog::debug( "WDendrogram" ) << m_heights; 00114 00115 // first write out all fibers 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 // using string_utils::operator<<; 00125 // wlog::debug( "WDendrogram" ) << "i: " << i; 00126 // wlog::debug( "WDendrogram" ) << "pred[i]: " << preds[i]; 00127 // wlog::debug( "WDendrogram" ) << "childs[i]: " << childsOfInnerNodes[i]; 00128 // wlog::debug( "WDendrogram" ) << "parentchilds: " << childsOfInnerNodes[ m_parents[ i ] ]; 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 // wlog::debug( "WDendrogram" ) << "i: " << i; 00155 // wlog::debug( "WDendrogram" ) << "pred[i]: " << preds[i]; 00156 // wlog::debug( "WDendrogram" ) << "childs[i]: " << childsOfInnerNodes[i]; 00157 // wlog::debug( "WDendrogram" ) << "parentchilds: " << childsOfInnerNodes[ m_parents[ i ] ]; 00158 result << "(" << left << ", " << right << "), " << m_heights[ i - m_heights.size() - 1 ] << ")" << std::endl; 00159 } 00160 00161 return result.str(); 00162 }