OpenWalnut  1.4.0
WHierarchicalTree.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 <list>
00026 #include <vector>
00027 
00028 #include "WHierarchicalTree.h"
00029 
00030 WHierarchicalTree::WHierarchicalTree() :
00031     m_clusterCount( 0 ),
00032     m_leafCount( 0 ),
00033     m_maxLevel( 0 ),
00034     m_leafesLocked( false )
00035 {
00036 }
00037 
00038 WHierarchicalTree::~WHierarchicalTree()
00039 {
00040 }
00041 
00042 std::vector< size_t > WHierarchicalTree::findXBiggestClusters( size_t cluster, size_t number )
00043 {
00044     //std::cout << number << " largest clusters for cluster: " << cluster << std::endl;
00045 
00046     if( number > m_containsLeafes[cluster].size() )
00047     {
00048         number = m_containsLeafes[cluster].size();
00049     }
00050 
00051     // init
00052     std::list<size_t>worklist;
00053     worklist.push_back( cluster );
00054 
00055     while( worklist.size() < number )
00056     {
00057         size_t current = worklist.front();
00058         worklist.pop_front();
00059         if( m_containsLeafes[current].size() > 1 )
00060         {
00061             size_t left = m_children[current].first;
00062             size_t right = m_children[current].second;
00063             worklist.push_back( left );
00064             worklist.push_back( right );
00065         }
00066         else
00067         {
00068             worklist.push_back( current );
00069         }
00070     }
00071 
00072     worklist.sort( compSize( this ) );
00073 
00074     bool newSplit = true;
00075 
00076     while( newSplit )
00077     {
00078         newSplit = false;
00079         size_t current = worklist.front();
00080 
00081         if( m_containsLeafes[current].size() > 1 )
00082         {
00083             size_t left = m_children[current].first;
00084             size_t right = m_children[current].second;
00085             size_t last = worklist.back();
00086 
00087             if( m_containsLeafes[left].size() > m_containsLeafes[last].size() )
00088             {
00089                 worklist.pop_front();
00090                 worklist.push_back( left );
00091                 worklist.sort( compSize( this ) );
00092                 newSplit = true;
00093             }
00094 
00095             last = worklist.back();
00096             if( m_containsLeafes[right].size() > m_containsLeafes[last].size() )
00097             {
00098                 if( !newSplit )
00099                 {
00100                     worklist.pop_front();
00101                 }
00102                 if( worklist.size() == number )
00103                 {
00104                     worklist.pop_back();
00105                 }
00106                 worklist.push_back( right );
00107                 worklist.sort( compSize( this ) );
00108                 newSplit = true;
00109             }
00110         }
00111     }
00112 
00113     std::vector<size_t>returnVector;
00114     std::list<size_t>::iterator it;
00115     for( it = worklist.begin(); it != worklist.end(); ++it )
00116     {
00117         size_t current = *it;
00118         //std::cout << "cluster:" << current << "  size:" << m_containsLeafes[current].size() << std::endl;
00119         returnVector.push_back( current );
00120     }
00121 
00122     return returnVector;
00123 }
00124 
00125 std::vector< size_t > WHierarchicalTree::downXLevelsFromTop( size_t level, bool hideOutliers )
00126 {
00127     if( level > m_maxLevel )
00128     {
00129         level = m_maxLevel -1;
00130     }
00131 
00132     std::vector< size_t > returnVector;
00133 
00134     std::list< size_t > worklist;
00135     worklist.push_back( m_clusterCount - 1 );
00136 
00137     for( size_t i = 0; i < level; ++i )
00138     {
00139         std::list<size_t>newChildList;
00140         while( !worklist.empty() )
00141         {
00142             size_t current = worklist.front();
00143             worklist.pop_front();
00144             if( m_containsLeafes[current].size() > 1 )
00145             {
00146                 size_t left = m_children[current].first;
00147                 size_t right = m_children[current].second;
00148 
00149                 if( hideOutliers )
00150                 {
00151                     if( m_containsLeafes[left].size() > 1 )
00152                     {
00153                         newChildList.push_back( left );
00154                     }
00155                     if( m_containsLeafes[right].size() > 1 )
00156                     {
00157                         newChildList.push_back( right );
00158                     }
00159                 }
00160                 else
00161                 {
00162                     newChildList.push_back( left );
00163                     newChildList.push_back( right );
00164                 }
00165             }
00166         }
00167         worklist = newChildList;
00168     }
00169 
00170     worklist.sort( compSize( this ) );
00171 
00172     std::list<size_t>::iterator it;
00173     for( it = worklist.begin(); it != worklist.end(); ++it )
00174     {
00175         size_t current = *it;
00176         returnVector.push_back( current );
00177     }
00178 
00179     return returnVector;
00180 }
00181 
00182 void WHierarchicalTree::colorCluster( size_t cluster, WColor color )
00183 {
00184     m_colors[cluster] = color;
00185     if( m_containsLeafes[cluster].size() > 1 )
00186     {
00187         colorCluster( m_children[cluster].first, color );
00188         colorCluster( m_children[cluster].second, color );
00189     }
00190 }
00191