OpenWalnut  1.4.0
WDendrogram.cpp
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 #include <algorithm>
26 #include <fstream>
27 #include <iterator>
28 #include <map>
29 #include <set>
30 #include <sstream>
31 #include <string>
32 #include <vector>
33 
34 #include "../exceptions/WOutOfBounds.h"
35 #include "../WAssert.h"
36 #include "../WLogger.h"
37 #include "../WStringUtils.h"
38 #include "WDendrogram.h"
39 
40 // init _static_ member variable and provide a linker reference to it
41 boost::shared_ptr< WPrototyped > WDendrogram::m_prototype = boost::shared_ptr< WPrototyped >();
42 
43 boost::shared_ptr< WPrototyped > WDendrogram::getPrototype()
44 {
45  if( !m_prototype )
46  {
47  m_prototype = boost::shared_ptr< WPrototyped >( new WDendrogram() );
48  }
49  return m_prototype;
50 }
51 
53  : WTransferable(),
54  m_parents( 0 ),
55  m_heights( 0 )
56 {
57 }
58 
60  : WTransferable()
61 {
62  reset( n );
63 }
64 
65 void WDendrogram::reset( size_t n )
66 {
67  WAssert( n > 0, "A Dendrogram for an empty set of objects was created which makes no sence, if your really need it implement it!" );
68  m_heights.resize( n - 1, 0.0 );
69  m_parents.reserve( 2 * n - 1 );
70  m_parents.resize( n, 0 );
71 }
72 
74 {
75  if( m_parents.empty() )
76  {
77  throw WOutOfBounds( "Accessed an empty WDendrogam via a call to a memeber function: " + caller + " which needs access to elements." );
78  }
79 }
80 
81 size_t WDendrogram::merge( size_t i, size_t j, double height )
82 {
84 
85 #ifdef DEBUG
86  std::stringstream errMsg;
87  errMsg << "Bug: n=" << m_heights.size() << " many leafs can lead maximal to 2n-1 many nodes in a tree but this was violated now!" << std::endl;
88  WAssert( m_parents.size() != 2 * m_heights.size() + 1, errMsg.str() );
89 #endif
90 
91  m_parents.push_back( m_parents.size() ); // the root s always self referencing
92 
93  m_heights[ m_parents.size() - 2 - m_heights.size() ] = height;
94  m_parents[i] = m_parents.back();
95  m_parents[j] = m_parents.back();
96 
97  return m_parents.size() - 1;
98 }
99 
100 std::string WDendrogram::toString() const
101 {
103 
104  std::stringstream result;
105  std::map< size_t, std::vector< size_t > > childsOfInnerNodes;
106  std::map< size_t, std::vector< size_t > > preds;
107  std::vector< size_t > level( 2 * m_heights.size() + 1, 0 );
108 
109  // For very insane debugging only:
110  // wlog::debug( "WDendrogram" ) << "nodes size: " << m_parents.size() << " and expeceted: " << 2 * m_heights.size() + 1;
111  // wlog::debug( "WDendrogram" ) << "Parents-ARRAY:";
112  // wlog::debug( "WDendrogram" ) << m_parents;
113  // wlog::debug( "WDendrogram" ) << "Heights-ARRAY:";
114  // wlog::debug( "WDendrogram" ) << m_heights;
115 
116  // first write out all fibers
117  for( size_t i = 0; i < m_heights.size() + 1; ++i )
118  {
119  result << "(0, (" << i << ",))" << std::endl;
120  childsOfInnerNodes[ m_parents[i] ].push_back( i );
121  preds[ m_parents[i] ].push_back( i );
122  }
123  for( size_t i = m_heights.size() + 1; i < 2 * m_heights.size() + 1; ++i )
124  {
125  // using string_utils::operator<<;
126  // wlog::debug( "WDendrogram" ) << "i: " << i;
127  // wlog::debug( "WDendrogram" ) << "pred[i]: " << preds[i];
128  // wlog::debug( "WDendrogram" ) << "childs[i]: " << childsOfInnerNodes[i];
129  // wlog::debug( "WDendrogram" ) << "parentchilds: " << childsOfInnerNodes[ m_parents[ i ] ];
130 
131  size_t left = *( preds[ i ].begin() );
132  size_t right = *( preds[ i ].rbegin() );
133  level[i] = std::max( level[left], level[right] ) + 1;
134  if( i != m_parents[i] )
135  {
136  preds[ m_parents[ i ] ].push_back( i );
137  childsOfInnerNodes[ m_parents[i] ].reserve( childsOfInnerNodes[ m_parents[i] ].size() + childsOfInnerNodes[i].size() );
138  childsOfInnerNodes[ m_parents[i] ].insert( childsOfInnerNodes[ m_parents[i] ].end(), childsOfInnerNodes[i].begin(),
139  childsOfInnerNodes[i].end() );
140  }
141  result << "(" << level[i] << ", (";
142  size_t numElements = childsOfInnerNodes[i].size();
143  for( std::vector< size_t >::const_iterator cit = childsOfInnerNodes[i].begin(); cit != childsOfInnerNodes[i].end(); ++cit )
144  {
145  if( numElements == 1 )
146  {
147  result << *cit << "), ";
148  }
149  else
150  {
151  result << *cit << ", ";
152  }
153  numElements -= 1;
154  }
155  // wlog::debug( "WDendrogram" ) << "i: " << i;
156  // wlog::debug( "WDendrogram" ) << "pred[i]: " << preds[i];
157  // wlog::debug( "WDendrogram" ) << "childs[i]: " << childsOfInnerNodes[i];
158  // wlog::debug( "WDendrogram" ) << "parentchilds: " << childsOfInnerNodes[ m_parents[ i ] ];
159  result << "(" << left << ", " << right << "), " << m_heights[ i - m_heights.size() - 1 ] << ")" << std::endl;
160  }
161 
162  return result.str();
163 }
164 
165 const std::vector< size_t >& WDendrogram::getParents() const
166 {
167  return m_parents;
168 }
169 
170 const std::vector< double >& WDendrogram::getHeights() const
171 {
172  return m_heights;
173 }
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:156
Indicates invalid element access of a container.
Definition: WOutOfBounds.h:36
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:161
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
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:134