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