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