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