OpenWalnut  1.3.1
Public Member Functions | Static Public Member Functions | Static Protected Attributes | Private Member Functions | Private Attributes | Friends | List of all members
WDendrogram Class Reference

Hirachical binary tree datastructure with spatial layout information called dendrogram. More...

#include <WDendrogram.h>

+ Inheritance diagram for WDendrogram:

Public Member Functions

virtual const std::string getName () const
 Gets the name of this prototype.
virtual const std::string getDescription () const
 Gets the description for this prototype.
 WDendrogram (size_t n)
 Constructs a new dendrogram for n many objects.
 WDendrogram ()
 Default constructs an empty dendrogram.
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.
std::string toString () const
 Transform this dendrogram into a string, where each leaf or inner node is mapped to a special string.
- Public Member Functions inherited from WTransferable
 WTransferable ()
 Default constructor.
virtual ~WTransferable ()
 Destructor.
- Public Member Functions inherited from WPrototyped
 WPrototyped ()
 Default constructor.
virtual ~WPrototyped ()
 Destructor.
template<typename T >
bool isA ()
 Checks whether the actual prototype has the specified runtime type.

Static Public Member Functions

static boost::shared_ptr
< WPrototyped
getPrototype ()
 Returns a prototype instantiated with the true type of the deriving class.

Static Protected Attributes

static boost::shared_ptr
< WPrototyped
m_prototype = boost::shared_ptr< WPrototyped >()
 The prototype as singleton.

Private Member Functions

void reset (size_t n)
 Resets the whole dendrogram to the number of elements it should be used for.
void checkAndThrowExceptionIfUsedUninitialized (std::string caller) const
 Checks if this instance is initialized.

Private Attributes

std::vector< size_t > m_parents
 Stores the parents of leafs as well as of inner nodes.
std::vector< double > m_heights
 Stores only for the inner nodes their heights.

Friends

class WDendrogramTest

Detailed Description

Hirachical binary tree datastructure with spatial layout information called dendrogram.

Please note that there are some limitations of this implementation: First of all there are exactly n-1 many inner nodes, and only inner nodes may have a height. In order to use this class for your objects ensure that the objects are labeled from 0,...,n-1.

The following description is taken from: http://en.wikipedia.org/wiki/Dendrogram A dendrogram (from Greek dendron "tree", -gramma "drawing") is a tree diagram frequently used to illustrate the arrangement of clusters produced by hierarchical clustering. Please note that each level has its height.

                  |
           ,------'--.     --- 4th level
           |         |
       |```````|     |     --- 3rd level
       |       |     |
       |       |  ...'...  --- 2nd level
       |       |  |     |
  |''''''''|   |  |     |  --- 1st level
  |        |   |  |     |
  |        |   |  |     |
  o        o   o  o     o  --- 0   level

Definition at line 62 of file WDendrogram.h.

Constructor & Destructor Documentation

WDendrogram::WDendrogram ( size_t  n)
explicit

Constructs a new dendrogram for n many objects.

Parameters
nThe number of leafs.

Definition at line 59 of file WDendrogram.cpp.

References reset().

WDendrogram::WDendrogram ( )

Default constructs an empty dendrogram.

Definition at line 52 of file WDendrogram.cpp.

Referenced by getPrototype().

Member Function Documentation

void WDendrogram::checkAndThrowExceptionIfUsedUninitialized ( std::string  caller) const
private

Checks if this instance is initialized.

If not, it throws an exception.

Exceptions
WOutOfBounds
Parameters
callerA string identifying the class member function.

Definition at line 73 of file WDendrogram.cpp.

References m_parents.

Referenced by merge(), and toString().

const std::string WDendrogram::getDescription ( ) const
inlinevirtual

Gets the description for this prototype.

Returns
the description

Implements WPrototyped.

Definition at line 155 of file WDendrogram.h.

const std::string WDendrogram::getName ( ) const
inlinevirtual

Gets the name of this prototype.

Returns
the name.

Implements WPrototyped.

Definition at line 150 of file WDendrogram.h.

boost::shared_ptr< WPrototyped > WDendrogram::getPrototype ( )
static

Returns a prototype instantiated with the true type of the deriving class.

Returns
the prototype.

Definition at line 43 of file WDendrogram.cpp.

References m_prototype, and WDendrogram().

size_t WDendrogram::merge ( size_t  i,
size_t  j,
double  height 
)

Merges two elements (either inner nodes or leafs) given via the indices i and j.

Parameters
iThe index referring either to an inner node or to a leaf.
jThe other index of a leaf or inner node.
heightThe height at which those to elements join.
Returns
The number of the inner node now representing now the parent of i and j.

Definition at line 81 of file WDendrogram.cpp.

References checkAndThrowExceptionIfUsedUninitialized(), m_heights, and m_parents.

Referenced by WDendrogramTest::testStringCreation().

void WDendrogram::reset ( size_t  n)
private

Resets the whole dendrogram to the number of elements it should be used for.

Parameters
nnumber of leafs

Definition at line 65 of file WDendrogram.cpp.

References m_heights, and m_parents.

Referenced by WDendrogram().

std::string WDendrogram::toString ( ) const

Transform this dendrogram into a string, where each leaf or inner node is mapped to a special string.

"(level, (all leafs incorporated by this node), (the two direct predecessors), height if available )"

Returns
The special string as constructed from the scheme above.

Definition at line 100 of file WDendrogram.cpp.

References checkAndThrowExceptionIfUsedUninitialized(), m_heights, and m_parents.

Referenced by WDendrogramTest::testStringCreation().

Member Data Documentation

std::vector< double > WDendrogram::m_heights
private

Stores only for the inner nodes their heights.

Definition at line 147 of file WDendrogram.h.

Referenced by merge(), reset(), and toString().

std::vector< size_t > WDendrogram::m_parents
private

Stores the parents of leafs as well as of inner nodes.

The first half of the arrary corresponds to the parents of the leafs and the second of the inner nodes. The last inner node is the top of the dendrogram.

Definition at line 142 of file WDendrogram.h.

Referenced by checkAndThrowExceptionIfUsedUninitialized(), merge(), reset(), and toString().

boost::shared_ptr< WPrototyped > WDendrogram::m_prototype = boost::shared_ptr< WPrototyped >()
staticprotected

The prototype as singleton.

Definition at line 120 of file WDendrogram.h.

Referenced by getPrototype().


The documentation for this class was generated from the following files: