OpenWalnut  1.2.5
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
WDendrogram.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 WDENDROGRAM_H
26 #define WDENDROGRAM_H
27 
28 #include <sstream>
29 #include <string>
30 #include <vector>
31 
32 #include <boost/shared_ptr.hpp>
33 
34 #include "../WTransferable.h"
35 
36 #include "../WExportCommon.h"
37 
38 /**
39  * Hirachical binary tree datastructure with spatial layout information called dendrogram. Please note that there are some
40  * limitations of this implementation: First of all there are exactly <dfn>n-1</dfn> many inner nodes, and only inner nodes may
41  * have a height. In order to use this class for your objects ensure that the objects are labeled from <dfn>0,...,n-1</dfn>.
42  *
43  * The following description is taken from: http://en.wikipedia.org/wiki/Dendrogram A dendrogram (from Greek
44  * dendron "tree", -gramma "drawing") is a tree diagram frequently used to illustrate the arrangement of
45  * clusters produced by hierarchical clustering. Please note that each level has its height.
46  *
47  \verbatim
48  |
49  ,------'--. --- 4th level
50  | |
51  |```````| | --- 3rd level
52  | | |
53  | | ...'... --- 2nd level
54  | | | |
55  |''''''''| | | | --- 1st level
56  | | | | |
57  | | | | |
58  o o o o o --- 0 level
59  \endverbatim
60  *
61  */
62 class OWCOMMON_EXPORT WDendrogram : public WTransferable // NOLINT
63 {
64 friend class WDendrogramTest;
65 public:
66  /**
67  * Gets the name of this prototype.
68  *
69  * \return the name.
70  */
71  virtual const std::string getName() const;
72 
73  /**
74  * Gets the description for this prototype.
75  *
76  * \return the description
77  */
78  virtual const std::string getDescription() const;
79 
80  /**
81  * Returns a prototype instantiated with the true type of the deriving class.
82  *
83  * \return the prototype.
84  */
85  static boost::shared_ptr< WPrototyped > getPrototype();
86 
87 
88  /**
89  * Constructs a new dendrogram for \c n many objects.
90  *
91  * \param n The number of leafs.
92  */
93  explicit WDendrogram( size_t n );
94 
95  /**
96  * Default constructs an empty dendrogram.
97  */
98  WDendrogram();
99 
100  /**
101  * Merges two elements (either inner nodes or leafs) given via the indices \e i and \e j.
102  *
103  * \param i The index referring either to an inner node or to a leaf.
104  * \param j The other index of a leaf or inner node.
105  * \param height The height at which those to elements join.
106  *
107  * \return The number of the inner node now representing now the parent of \e i and \e j.
108  */
109  size_t merge( size_t i, size_t j, double height );
110 
111  /**
112  * Transform this dendrogram into a string, where each leaf or inner node is mapped to a special string.
113  * <dfn>"(level, (all leafs incorporated by this node), (the two direct predecessors), height if available )"</dfn>
114  *
115  * \return The special string as constructed from the scheme above.
116  */
117  std::string toString() const;
118 
119 protected:
120  static boost::shared_ptr< WPrototyped > m_prototype; //!< The prototype as singleton.
121 
122 private:
123  /**
124  * Resets the whole dendrogram to the number of elements it should be used for.
125  *
126  * \param n number of leafs
127  */
128  void reset( size_t n );
129 
130  /**
131  * Checks if this instance is initialized. If not, it throws an exception.
132  * \throw WOutOfBounds
133  * \param caller A string identifying the class member function.
134  */
135  void checkAndThrowExceptionIfUsedUninitialized( std::string caller ) const;
136 
137  /**
138  * Stores the parents of leafs as well as of inner nodes. The first half of the arrary corresponds to the
139  * parents of the leafs and the second of the inner nodes. The last inner node is the top of the
140  * dendrogram.
141  */
142  std::vector< size_t > m_parents;
143 
144  /**
145  * Stores only for the inner nodes their heights.
146  */
147  std::vector< double > m_heights;
148 };
149 
150 inline const std::string WDendrogram::getName() const
151 {
152  return "WDendrogram";
153 }
154 
155 inline const std::string WDendrogram::getDescription() const
156 {
157  return "A Dendrogram as a array with additional heights for each inner node.";
158 }
159 
160 
161 #endif // WDENDROGRAM_H