OpenWalnut
1.2.5
|
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