OpenWalnut  1.4.0
WHierarchicalTree.h
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 #ifndef WHIERARCHICALTREE_H
26 #define WHIERARCHICALTREE_H
27 
28 #include <utility>
29 #include <vector>
30 #include <queue>
31 #include <list>
32 
33 #ifndef Q_MOC_RUN
34 #include <boost/shared_ptr.hpp>
35 #endif
36 
37 #include "WColor.h"
38 
39 
40 /**
41  * base class for hierarchical tree implementations
42  */
43 class WHierarchicalTree // NOLINT
44 {
45 public:
46  /**
47  * standard constructor
48  */
50 
51  /**
52  * destructor
53  */
54  virtual ~WHierarchicalTree();
55 
56  /**
57  * A leaf is at the very bottom of the tree, it represents a single fiber or voxel, for several purposes
58  * a leaf also counts as a cluster
59  */
60  virtual void addLeaf() = 0;
61 
62  /**
63  * getter
64  * \return the number of leafes
65  */
66  size_t getLeafCount();
67 
68  /**
69  * getter
70  * \return the number of clusters
71  */
72  size_t getClusterCount();
73 
74  /**
75  * getter
76  * \return maxlevel, i.e. the level of the root cluster
77  */
78  size_t getMaxLevel();
79 
80  /**
81  * getter
82  * \param cluster
83  * \return the level of the selected cluster
84  */
85  size_t getLevel( size_t cluster );
86 
87  /**
88  * getter
89  * \param cluster the cluster in question
90  * \return the parent for the selected cluster
91  */
92  size_t getParent( size_t cluster );
93 
94  /**
95  * getter
96  * \param cluster
97  * \return the custom data for the selected cluster
98  */
99  float getCustomData( size_t cluster );
100 
101  /**
102  * setter sets the color for a single cluster
103  * \param color
104  * \param cluster
105  */
106  void setColor( WColor color, size_t cluster );
107 
108  /**
109  * getter
110  * \param cluster
111  * \return the color for the selected cluster
112  */
113  WColor getColor( size_t cluster );
114 
115  /**
116  * getter
117  * \param cluster
118  * \return children for the selected cluster
119  */
120  std::pair<size_t, size_t>getChildren( size_t cluster );
121 
122  /**
123  * getter
124  * \param cluster
125  * \return the leafes contained in the selected cluster
126  */
127  std::vector<size_t>getLeafesForCluster( size_t cluster );
128 
129  /**
130  * getter
131  * \param cluster
132  * \return number of leafes for the selected cluster
133  */
134  size_t size( size_t cluster );
135 
136  /**
137  * checks if a cluster is a leaf or a cluster
138  * \param cluster
139  * \return true if it is a leaf
140  */
141  bool isLeaf( size_t cluster );
142 
143  /**
144  * returns a number of clusters at a certain level down from top cluster
145  * \param level how many levels to go down
146  * \param hideOutliers true if clusters of size 1 should be ignored
147  * \return vector containing the cluster id's
148  */
149  std::vector< size_t >downXLevelsFromTop( size_t level, bool hideOutliers = false );
150 
151  /**
152  * finds the X biggest clusters for a given cluster
153  * \param cluster
154  * \param number of sub clusters
155  *
156  * \return the biggest clusters
157  */
158  std::vector< size_t >findXBiggestClusters( size_t cluster, size_t number = 10 );
159 
160  /**
161  * sets the color for a selected cluster and all sub clusters
162  * \param cluster
163  * \param color
164  */
165  void colorCluster( size_t cluster, WColor color );
166 
167 
168 protected:
169  /**
170  * overall number of cluster, counts both leafes ( clusters of size one ) and real clusters
171  */
173 
174  /**
175  * number of leaf nodes
176  */
177  size_t m_leafCount;
178 
179  /**
180  * the maximum level, naturally the level of the root node
181  */
182  size_t m_maxLevel;
183 
184  /**
185  * to enforce valid datastructures there will be no leaf with an id higher than a cluster, thus when
186  * the first cluster is inserted, no leafes may be added
187  */
189 
190  /**
191  * vector that stores the level of each cluster, the level is the maximum of the levels of the child clusters +1
192  */
193  std::vector<size_t>m_level;
194 
195  /**
196  * vector that stores the parent cluster for each cluster
197  */
198  std::vector<size_t>m_parents;
199 
200  /**
201  * vector that stores the 2 children of each cluster, contains an empty pair for leafes
202  */
203  std::vector< std::pair< size_t, size_t> >m_children;
204 
205  /**
206  * custom data for each cluster, this may some energy or similarity level generated by the clustering algorithm
207  * or something completely different
208  */
209  std::vector<float>m_customData;
210 
211  /**
212  * a color value for each cluster
213  */
214  std::vector<WColor>m_colors;
215 
216  /**
217  *vector that stores the leaf id's for each cluster, this is quite memory intensive but speeds up selection
218  * of leafes for nodes at higher levels
219  */
220  std::vector< std::vector<size_t> >m_containsLeafes;
221 
222 private:
223 };
224 
226 {
227  return m_leafCount;
228 }
229 
231 {
232  return m_clusterCount;
233 }
234 
236 {
237  return m_maxLevel;
238 }
239 
240 inline size_t WHierarchicalTree::getLevel( size_t cluster )
241 {
242  return m_level[cluster];
243 }
244 
245 inline size_t WHierarchicalTree::getParent( size_t cluster )
246 {
247  if( m_level[cluster] < m_maxLevel )
248  {
249  return m_parents[cluster];
250  }
251  else
252  {
253  // this is just to quiet the compiler, this branch should never be reached
254  return cluster;
255  }
256 }
257 
258 inline std::pair<size_t, size_t>WHierarchicalTree::getChildren( size_t cluster )
259 {
260  if( m_level[cluster] > 0 )
261  {
262  return m_children[cluster];
263  }
264  else
265  {
266  // this is just to quiet the compiler, this branch should never be reached
267  return std::pair<size_t, size_t>( cluster, cluster );
268  }
269 }
270 
271 inline float WHierarchicalTree::getCustomData( size_t cluster )
272 {
273  return m_customData[cluster];
274 }
275 
276 inline size_t WHierarchicalTree::size( size_t cluster )
277 {
278  return getLeafesForCluster( cluster ).size();
279 }
280 
281 inline void WHierarchicalTree::setColor( WColor color, size_t cluster )
282 {
283  m_colors[cluster] = color;
284 }
285 
286 inline WColor WHierarchicalTree::getColor( size_t cluster )
287 {
288  return m_colors[cluster];
289 }
290 
291 inline bool WHierarchicalTree::isLeaf( size_t cluster )
292 {
293  return ( cluster < m_leafCount ) ? true : false;
294 }
295 
296 inline std::vector<size_t>WHierarchicalTree::getLeafesForCluster( size_t cluster )
297 {
298  return m_containsLeafes[cluster];
299 }
300 /**
301  * implements a compare operator for clusters, depending on leaf count
302  */
303 struct compSize
304 {
305  WHierarchicalTree* m_tree; //!< stores pointer to tree we work on
306 
307  /**
308  * constructor
309  * \param tree
310  */
311  explicit compSize( WHierarchicalTree* tree ) :
312  m_tree( tree )
313  {
314  }
315 
316  /**
317  * compares two clusters
318  * \param lhs
319  * \param rhs
320  * \return bool
321  */
322  bool operator()( const size_t lhs, const size_t rhs ) const //NOLINT
323  {
324  return m_tree->size( lhs ) > m_tree->size( rhs ); //NOLINT
325  }
326 };
327 /**
328  * implements a compare operator for clusters, depending on custom value of the cluster
329  */
330 struct compValue
331 {
332  WHierarchicalTree* m_tree; //!< stores pointer to tree we work on
333 
334  /**
335  * constructor
336  * \param tree
337  */
338  explicit compValue( WHierarchicalTree* tree ) :
339  m_tree( tree )
340  {
341  }
342  /**
343  * compares two clusters
344  * \param lhs
345  * \param rhs
346  * \return bool
347  */
348  bool operator()( const size_t lhs, const size_t rhs ) const
349  {
350  return m_tree->getCustomData( lhs ) > m_tree->getCustomData( rhs );
351  }
352 };
353 
354 #endif // WHIERARCHICALTREE_H
size_t m_maxLevel
the maximum level, naturally the level of the root node
virtual ~WHierarchicalTree()
destructor
virtual void addLeaf()=0
A leaf is at the very bottom of the tree, it represents a single fiber or voxel, for several purposes...
size_t m_leafCount
number of leaf nodes
compSize(WHierarchicalTree *tree)
constructor
implements a compare operator for clusters, depending on leaf count
WColor getColor(size_t cluster)
getter
size_t getParent(size_t cluster)
getter
implements a compare operator for clusters, depending on custom value of the cluster ...
compValue(WHierarchicalTree *tree)
constructor
std::pair< size_t, size_t > getChildren(size_t cluster)
getter
std::vector< std::vector< size_t > > m_containsLeafes
vector that stores the leaf id's for each cluster, this is quite memory intensive but speeds up selec...
std::vector< float > m_customData
custom data for each cluster, this may some energy or similarity level generated by the clustering al...
std::vector< std::pair< size_t, size_t > > m_children
vector that stores the 2 children of each cluster, contains an empty pair for leafes ...
std::vector< size_t > findXBiggestClusters(size_t cluster, size_t number=10)
finds the X biggest clusters for a given cluster
bool m_leafesLocked
to enforce valid datastructures there will be no leaf with an id higher than a cluster, thus when the first cluster is inserted, no leafes may be added
bool operator()(const size_t lhs, const size_t rhs) const
compares two clusters
std::vector< size_t > m_level
vector that stores the level of each cluster, the level is the maximum of the levels of the child clu...
size_t getLeafCount()
getter
WHierarchicalTree * m_tree
stores pointer to tree we work on
std::vector< size_t > downXLevelsFromTop(size_t level, bool hideOutliers=false)
returns a number of clusters at a certain level down from top cluster
std::vector< size_t > m_parents
vector that stores the parent cluster for each cluster
base class for hierarchical tree implementations
bool isLeaf(size_t cluster)
checks if a cluster is a leaf or a cluster
WHierarchicalTree * m_tree
stores pointer to tree we work on
float getCustomData(size_t cluster)
getter
std::vector< size_t > getLeafesForCluster(size_t cluster)
getter
size_t size(size_t cluster)
getter
size_t m_clusterCount
overall number of cluster, counts both leafes ( clusters of size one ) and real clusters ...
bool operator()(const size_t lhs, const size_t rhs) const
compares two clusters
WHierarchicalTree()
standard constructor
void setColor(WColor color, size_t cluster)
setter sets the color for a single cluster
size_t getClusterCount()
getter
void colorCluster(size_t cluster, WColor color)
sets the color for a selected cluster and all sub clusters
std::vector< WColor > m_colors
a color value for each cluster
size_t getMaxLevel()
getter
size_t getLevel(size_t cluster)
getter