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