OpenWalnut  1.2.5
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
WHierarchicalTree.cpp
1 //---------------------------------------------------------------------------
2 //
3 // Project: OpenWalnut ( http://www.openwalnut.org )
4 //
5 // Copyright 2009 OpenWalnut Community, BSV@Uni-Leipzig and CNCF@MPI-CBS
6 // For more information see http://www.openwalnut.org/copying
7 //
8 // This file is part of OpenWalnut.
9 //
10 // OpenWalnut is free software: you can redistribute it and/or modify
11 // it under the terms of the GNU Lesser General Public License as published by
12 // the Free Software Foundation, either version 3 of the License, or
13 // (at your option) any later version.
14 //
15 // OpenWalnut is distributed in the hope that it will be useful,
16 // but WITHOUT ANY WARRANTY; without even the implied warranty of
17 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 // GNU Lesser General Public License for more details.
19 //
20 // You should have received a copy of the GNU Lesser General Public License
21 // along with OpenWalnut. If not, see <http://www.gnu.org/licenses/>.
22 //
23 //---------------------------------------------------------------------------
24 
25 #include "WHierarchicalTree.h"
26 
28  m_clusterCount( 0 ),
29  m_leafCount( 0 ),
30  m_maxLevel( 0 ),
31  m_leafesLocked( false )
32 {
33 }
34 
36 {
37 }
38 
39 std::vector< size_t > WHierarchicalTree::findXBiggestClusters( size_t cluster, size_t number )
40 {
41  //std::cout << number << " largest clusters for cluster: " << cluster << std::endl;
42 
43  if( number > m_containsLeafes[cluster].size() )
44  {
45  number = m_containsLeafes[cluster].size();
46  }
47 
48  // init
49  std::list<size_t>worklist;
50  worklist.push_back( cluster );
51 
52  while( worklist.size() < number )
53  {
54  size_t current = worklist.front();
55  worklist.pop_front();
56  if( m_containsLeafes[current].size() > 1 )
57  {
58  size_t left = m_children[current].first;
59  size_t right = m_children[current].second;
60  worklist.push_back( left );
61  worklist.push_back( right );
62  }
63  else
64  {
65  worklist.push_back( current );
66  }
67  }
68 
69  worklist.sort( compSize( this ) );
70 
71  bool newSplit = true;
72 
73  while( newSplit )
74  {
75  newSplit = false;
76  size_t current = worklist.front();
77 
78  if( m_containsLeafes[current].size() > 1 )
79  {
80  size_t left = m_children[current].first;
81  size_t right = m_children[current].second;
82  size_t last = worklist.back();
83 
84  if( m_containsLeafes[left].size() > m_containsLeafes[last].size() )
85  {
86  worklist.pop_front();
87  worklist.push_back( left );
88  worklist.sort( compSize( this ) );
89  newSplit = true;
90  }
91 
92  last = worklist.back();
93  if( m_containsLeafes[right].size() > m_containsLeafes[last].size() )
94  {
95  if( !newSplit )
96  {
97  worklist.pop_front();
98  }
99  if( worklist.size() == number )
100  {
101  worklist.pop_back();
102  }
103  worklist.push_back( right );
104  worklist.sort( compSize( this ) );
105  newSplit = true;
106  }
107  }
108  }
109 
110  std::vector<size_t>returnVector;
111  std::list<size_t>::iterator it;
112  for( it = worklist.begin(); it != worklist.end(); ++it )
113  {
114  size_t current = *it;
115  //std::cout << "cluster:" << current << " size:" << m_containsLeafes[current].size() << std::endl;
116  returnVector.push_back( current );
117  }
118 
119  return returnVector;
120 }
121 
122 std::vector< size_t > WHierarchicalTree::downXLevelsFromTop( size_t level, bool hideOutliers )
123 {
124  if( level > m_maxLevel )
125  {
126  level = m_maxLevel -1;
127  }
128 
129  std::vector<size_t>returnVector;
130 
131  std::list<size_t>worklist;
132  worklist.push_back( m_clusterCount - 1 );
133 
134  for( size_t i = 0; i < level; ++i )
135  {
136  std::list<size_t>newChildList;
137  while( !worklist.empty() )
138  {
139  size_t current = worklist.front();
140  worklist.pop_front();
141  if( m_containsLeafes[current].size() > 1 )
142  {
143  size_t left = m_children[current].first;
144  size_t right = m_children[current].second;
145 
146  if( hideOutliers )
147  {
148  if( m_containsLeafes[left].size() > 1 )
149  {
150  newChildList.push_back( left );
151  }
152  if( m_containsLeafes[right].size() > 1 )
153  {
154  newChildList.push_back( right );
155  }
156  }
157  else
158  {
159  newChildList.push_back( left );
160  newChildList.push_back( right );
161  }
162  }
163  }
164  worklist = newChildList;
165  }
166 
167  worklist.sort( compSize( this ) );
168 
169  std::list<size_t>::iterator it;
170  for( it = worklist.begin(); it != worklist.end(); ++it )
171  {
172  size_t current = *it;
173  returnVector.push_back( current );
174  }
175 
176  return returnVector;
177 }
178 
179 void WHierarchicalTree::colorCluster( size_t cluster, WColor color )
180 {
181  m_colors[cluster] = color;
182  if( m_containsLeafes[cluster].size() > 1 )
183  {
184  colorCluster( m_children[cluster].first, color );
185  colorCluster( m_children[cluster].second, color );
186  }
187 }
188