OpenWalnut  1.4.0
WDendrogram.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 WDENDROGRAM_H
00026 #define WDENDROGRAM_H
00027 
00028 #include <sstream>
00029 #include <string>
00030 #include <vector>
00031 
00032 #include <boost/shared_ptr.hpp>
00033 
00034 #include "../WTransferable.h"
00035 
00036 
00037 
00038 /**
00039  * Hirachical binary tree datastructure with spatial layout information called dendrogram. Please note that there are some
00040  * limitations of this implementation: First of all there are exactly <dfn>n-1</dfn> many inner nodes, and only inner nodes may
00041  * have a height. In order to use this class for your objects ensure that the objects are labeled from <dfn>0,...,n-1</dfn>.
00042  *
00043  * The following description is taken from: http://en.wikipedia.org/wiki/Dendrogram A dendrogram (from Greek
00044  * dendron "tree", -gramma "drawing") is a tree diagram frequently used to illustrate the arrangement of
00045  * clusters produced by hierarchical clustering. Please note that each level has its height.
00046  *
00047    \verbatim
00048                      |
00049               ,------'--.     --- 4th level
00050               |         |
00051           |```````|     |     --- 3rd level
00052           |       |     |
00053           |       |  ...'...  --- 2nd level
00054           |       |  |     |
00055      |''''''''|   |  |     |  --- 1st level
00056      |        |   |  |     |
00057      |        |   |  |     |
00058      o        o   o  o     o  --- 0   level
00059    \endverbatim
00060  *
00061  */
00062 class WDendrogram : public WTransferable // NOLINT
00063 {
00064 friend class WDendrogramTest;
00065 public:
00066     /**
00067      * Gets the name of this prototype.
00068      *
00069      * \return the name.
00070      */
00071     virtual const std::string getName() const;
00072 
00073     /**
00074      * Gets the description for this prototype.
00075      *
00076      * \return the description
00077      */
00078     virtual const std::string getDescription() const;
00079 
00080     /**
00081      * Returns a prototype instantiated with the true type of the deriving class.
00082      *
00083      * \return the prototype.
00084      */
00085     static boost::shared_ptr< WPrototyped > getPrototype();
00086 
00087 
00088     /**
00089      * Constructs a new dendrogram for \c n many objects.
00090      *
00091      * \param n The number of leafs.
00092      */
00093     explicit WDendrogram( size_t n );
00094 
00095     /**
00096      * Default constructs an empty dendrogram.
00097      */
00098     WDendrogram();
00099 
00100     /**
00101      * Merges two elements (either inner nodes or leafs) given via the indices \e i and \e j.
00102      *
00103      * \param i The index referring either to an inner node or to a leaf.
00104      * \param j The other index of a leaf or inner node.
00105      * \param height The height at which those to elements join.
00106      *
00107      * \return The number of the inner node now representing now the parent of \e i and \e j.
00108      */
00109     size_t merge( size_t i, size_t j, double height );
00110 
00111     /**
00112      * Transform this dendrogram into a string, where each leaf or inner node is mapped to a special string.
00113      * <dfn>"(level, (all leafs incorporated by this node), (the two direct predecessors), height if available )"</dfn>
00114      *
00115      * \return The special string as constructed from the scheme above.
00116      */
00117     std::string toString() const;
00118 
00119     /**
00120      * Returns const reference to the internal parents array.
00121      *
00122      * \return const ref to the parents array.
00123      */
00124     const std::vector< size_t >& getParents() const;
00125 
00126     /**
00127      * Const reference to the heights array.
00128      *
00129      * \return const reference to the heights array.
00130      */
00131     const std::vector< double >& getHeights() const;
00132 
00133 protected:
00134     static boost::shared_ptr< WPrototyped > m_prototype; //!< The prototype as singleton.
00135 
00136 private:
00137     /**
00138      * Resets the whole dendrogram to the number of elements it should be used for.
00139      *
00140      * \param n number of leafs
00141      */
00142     void reset( size_t n );
00143 
00144     /**
00145      * Checks if this instance is initialized. If not, it throws an exception.
00146      * \throw WOutOfBounds
00147      * \param caller A string identifying the class member function.
00148      */
00149     void checkAndThrowExceptionIfUsedUninitialized( std::string caller ) const;
00150 
00151     /**
00152      * Stores the parents of leafs as well as of inner nodes. The first half of the arrary corresponds to the
00153      * parents of the leafs and the second of the inner nodes. The last inner node is the top of the
00154      * dendrogram.
00155      */
00156     std::vector< size_t > m_parents;
00157 
00158     /**
00159      * Stores only for the inner nodes their heights.
00160      */
00161     std::vector< double > m_heights;
00162 };
00163 
00164 inline const std::string WDendrogram::getName() const
00165 {
00166     return "WDendrogram";
00167 }
00168 
00169 inline const std::string WDendrogram::getDescription() const
00170 {
00171     return "A Dendrogram as a array with additional heights for each inner node.";
00172 }
00173 
00174 
00175 #endif  // WDENDROGRAM_H