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