OpenWalnut  1.4.0
WHierarchicalTree.h
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