OpenWalnut 1.2.5

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 <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 }
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends