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 #ifndef WHIERARCHICALTREE_H 00026 #define WHIERARCHICALTREE_H 00027 00028 #include <utility> 00029 #include <vector> 00030 #include <queue> 00031 #include <list> 00032 00033 #include <boost/shared_ptr.hpp> 00034 00035 #include "WColor.h" 00036 00037 00038 /** 00039 * base class for hierarchical tree implementations 00040 */ 00041 class WHierarchicalTree // NOLINT 00042 { 00043 public: 00044 /** 00045 * standard constructor 00046 */ 00047 WHierarchicalTree(); 00048 00049 /** 00050 * destructor 00051 */ 00052 virtual ~WHierarchicalTree(); 00053 00054 /** 00055 * A leaf is at the very bottom of the tree, it represents a single fiber or voxel, for several purposes 00056 * a leaf also counts as a cluster 00057 */ 00058 virtual void addLeaf() = 0; 00059 00060 /** 00061 * getter 00062 * \return the number of leafes 00063 */ 00064 size_t getLeafCount(); 00065 00066 /** 00067 * getter 00068 * \return the number of clusters 00069 */ 00070 size_t getClusterCount(); 00071 00072 /** 00073 * getter 00074 * \return maxlevel, i.e. the level of the root cluster 00075 */ 00076 size_t getMaxLevel(); 00077 00078 /** 00079 * getter 00080 * \param cluster 00081 * \return the level of the selected cluster 00082 */ 00083 size_t getLevel( size_t cluster ); 00084 00085 /** 00086 * getter 00087 * \param cluster the cluster in question 00088 * \return the parent for the selected cluster 00089 */ 00090 size_t getParent( size_t cluster ); 00091 00092 /** 00093 * getter 00094 * \param cluster 00095 * \return the custom data for the selected cluster 00096 */ 00097 float getCustomData( size_t cluster ); 00098 00099 /** 00100 * setter sets the color for a single cluster 00101 * \param color 00102 * \param cluster 00103 */ 00104 void setColor( WColor color, size_t cluster ); 00105 00106 /** 00107 * getter 00108 * \param cluster 00109 * \return the color for the selected cluster 00110 */ 00111 WColor getColor( size_t cluster ); 00112 00113 /** 00114 * getter 00115 * \param cluster 00116 * \return children for the selected cluster 00117 */ 00118 std::pair<size_t, size_t>getChildren( size_t cluster ); 00119 00120 /** 00121 * getter 00122 * \param cluster 00123 * \return the leafes contained in the selected cluster 00124 */ 00125 std::vector<size_t>getLeafesForCluster( size_t cluster ); 00126 00127 /** 00128 * getter 00129 * \param cluster 00130 * \return number of leafes for the selected cluster 00131 */ 00132 size_t size( size_t cluster ); 00133 00134 /** 00135 * checks if a cluster is a leaf or a cluster 00136 * \param cluster 00137 * \return true if it is a leaf 00138 */ 00139 bool isLeaf( size_t cluster ); 00140 00141 /** 00142 * returns a number of clusters at a certain level down from top cluster 00143 * \param level how many levels to go down 00144 * \param hideOutliers true if clusters of size 1 should be ignored 00145 * \return vector containing the cluster id's 00146 */ 00147 std::vector< size_t >downXLevelsFromTop( size_t level, bool hideOutliers = false ); 00148 00149 /** 00150 * finds the X biggest clusters for a given cluster 00151 * \param cluster 00152 * \param number of sub clusters 00153 * 00154 * \return the biggest clusters 00155 */ 00156 std::vector< size_t >findXBiggestClusters( size_t cluster, size_t number = 10 ); 00157 00158 /** 00159 * sets the color for a selected cluster and all sub clusters 00160 * \param cluster 00161 * \param color 00162 */ 00163 void colorCluster( size_t cluster, WColor color ); 00164 00165 00166 protected: 00167 /** 00168 * overall number of cluster, counts both leafes ( clusters of size one ) and real clusters 00169 */ 00170 size_t m_clusterCount; 00171 00172 /** 00173 * number of leaf nodes 00174 */ 00175 size_t m_leafCount; 00176 00177 /** 00178 * the maximum level, naturally the level of the root node 00179 */ 00180 size_t m_maxLevel; 00181 00182 /** 00183 * to enforce valid datastructures there will be no leaf with an id higher than a cluster, thus when 00184 * the first cluster is inserted, no leafes may be added 00185 */ 00186 bool m_leafesLocked; 00187 00188 /** 00189 * vector that stores the level of each cluster, the level is the maximum of the levels of the child clusters +1 00190 */ 00191 std::vector<size_t>m_level; 00192 00193 /** 00194 * vector that stores the parent cluster for each cluster 00195 */ 00196 std::vector<size_t>m_parents; 00197 00198 /** 00199 * vector that stores the 2 children of each cluster, contains an empty pair for leafes 00200 */ 00201 std::vector< std::pair< size_t, size_t> >m_children; 00202 00203 /** 00204 * custom data for each cluster, this may some energy or similarity level generated by the clustering algorithm 00205 * or something completely different 00206 */ 00207 std::vector<float>m_customData; 00208 00209 /** 00210 * a color value for each cluster 00211 */ 00212 std::vector<WColor>m_colors; 00213 00214 /** 00215 *vector that stores the leaf id's for each cluster, this is quite memory intensive but speeds up selection 00216 * of leafes for nodes at higher levels 00217 */ 00218 std::vector< std::vector<size_t> >m_containsLeafes; 00219 00220 private: 00221 }; 00222 00223 inline size_t WHierarchicalTree::getLeafCount() 00224 { 00225 return m_leafCount; 00226 } 00227 00228 inline size_t WHierarchicalTree::getClusterCount() 00229 { 00230 return m_clusterCount; 00231 } 00232 00233 inline size_t WHierarchicalTree::getMaxLevel() 00234 { 00235 return m_maxLevel; 00236 } 00237 00238 inline size_t WHierarchicalTree::getLevel( size_t cluster ) 00239 { 00240 return m_level[cluster]; 00241 } 00242 00243 inline size_t WHierarchicalTree::getParent( size_t cluster ) 00244 { 00245 if( m_level[cluster] < m_maxLevel ) 00246 { 00247 return m_parents[cluster]; 00248 } 00249 else 00250 { 00251 // this is just to quiet the compiler, this branch should never be reached 00252 return cluster; 00253 } 00254 } 00255 00256 inline std::pair<size_t, size_t>WHierarchicalTree::getChildren( size_t cluster ) 00257 { 00258 if( m_level[cluster] > 0 ) 00259 { 00260 return m_children[cluster]; 00261 } 00262 else 00263 { 00264 // this is just to quiet the compiler, this branch should never be reached 00265 return std::pair<size_t, size_t>( cluster, cluster ); 00266 } 00267 } 00268 00269 inline float WHierarchicalTree::getCustomData( size_t cluster ) 00270 { 00271 return m_customData[cluster]; 00272 } 00273 00274 inline size_t WHierarchicalTree::size( size_t cluster ) 00275 { 00276 return getLeafesForCluster( cluster ).size(); 00277 } 00278 00279 inline void WHierarchicalTree::setColor( WColor color, size_t cluster ) 00280 { 00281 m_colors[cluster] = color; 00282 } 00283 00284 inline WColor WHierarchicalTree::getColor( size_t cluster ) 00285 { 00286 return m_colors[cluster]; 00287 } 00288 00289 inline bool WHierarchicalTree::isLeaf( size_t cluster ) 00290 { 00291 return ( cluster < m_leafCount ) ? true : false; 00292 } 00293 00294 inline std::vector<size_t>WHierarchicalTree::getLeafesForCluster( size_t cluster ) 00295 { 00296 return m_containsLeafes[cluster]; 00297 } 00298 /** 00299 * implements a compare operator for clusters, depending on leaf count 00300 */ 00301 struct compSize 00302 { 00303 WHierarchicalTree* m_tree; //!< stores pointer to tree we work on 00304 00305 /** 00306 * constructor 00307 * \param tree 00308 */ 00309 explicit compSize( WHierarchicalTree* tree ) : 00310 m_tree( tree ) 00311 { 00312 } 00313 00314 /** 00315 * compares two clusters 00316 * \param lhs 00317 * \param rhs 00318 * \return bool 00319 */ 00320 bool operator()( const size_t lhs, const size_t rhs ) const //NOLINT 00321 { 00322 return m_tree->size( lhs ) > m_tree->size( rhs ); //NOLINT 00323 } 00324 }; 00325 /** 00326 * implements a compare operator for clusters, depending on custom value of the cluster 00327 */ 00328 struct compValue 00329 { 00330 WHierarchicalTree* m_tree; //!< stores pointer to tree we work on 00331 00332 /** 00333 * constructor 00334 * \param tree 00335 */ 00336 explicit compValue( WHierarchicalTree* tree ) : 00337 m_tree( tree ) 00338 { 00339 } 00340 /** 00341 * compares two clusters 00342 * \param lhs 00343 * \param rhs 00344 * \return bool 00345 */ 00346 bool operator()( const size_t lhs, const size_t rhs ) const 00347 { 00348 return m_tree->getCustomData( lhs ) > m_tree->getCustomData( rhs ); 00349 } 00350 }; 00351 00352 #endif // WHIERARCHICALTREE_H