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