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 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