Logo ROOT   6.08/07
Reference Guide
BinaryTree.cxx
Go to the documentation of this file.
1 // @(#)root/tmva $Id$
2 // Author: Andreas Hoecker, Joerg Stelzer, Helge Voss, Kai Voss, Eckhard von Toerne
3 
4 /**********************************************************************************
5  * Project: TMVA - a Root-integrated toolkit for multivariate data analysis *
6  * Package: TMVA *
7  * Class : TMVA::BinaryTree *
8  * Web : http://tmva.sourceforge.net *
9  * *
10  * Description: *
11  * Implementation (see header file for description) *
12  * *
13  * Authors (alphabetical): *
14  * Andreas Hoecker <Andreas.Hocker@cern.ch> - CERN, Switzerland *
15  * Joerg Stelzer <stelzer@cern.ch> - DESY, Germany *
16  * Helge Voss <Helge.Voss@cern.ch> - MPI-K Heidelberg, Germany *
17  * Kai Voss <Kai.Voss@cern.ch> - U. of Victoria, Canada *
18  * Eckhard v. Toerne <evt@uni-bonn.de> - U of Bonn, Germany *
19  * *
20  * Copyright (c) 2005-2011: *
21  * CERN, Switzerland *
22  * U. of Victoria, Canada *
23  * MPI-K Heidelberg, Germany *
24  * U. of Bonn, Germany *
25  * *
26  * Redistribution and use in source and binary forms, with or without *
27  * modification, are permitted according to the terms listed in LICENSE *
28  * (http://tmva.sourceforge.net/LICENSE) *
29  **********************************************************************************/
30 
31 //////////////////////////////////////////////////////////////////////////
32 // //
33 // BinaryTree //
34 // //
35 // Base class for BinarySearch and Decision Trees //
36 // //
37 //////////////////////////////////////////////////////////////////////////
38 
39 #include <string>
40 #include <stdexcept>
41 
42 #include "ThreadLocalStorage.h"
43 
44 #include "TMVA/BinaryTree.h"
45 #include "TMVA/MsgLogger.h"
46 #include "TMVA/Event.h"
47 #include "TMVA/Node.h"
48 #include "TMVA/Tools.h"
49 #include "TMVA/Types.h"
50 
52 
53 ////////////////////////////////////////////////////////////////////////////////
54 /// constructor for a yet "empty" tree. Needs to be filled afterwards
55 
57 : fRoot ( NULL ),
58  fNNodes( 0 ),
59  fDepth ( 0 )
60 {
61 }
62 
63 ////////////////////////////////////////////////////////////////////////////////
64 ///destructor (deletes the nodes and "events" if owned by the tree
65 
67 {
68  this->DeleteNode( fRoot );
69  fRoot=0;
70 }
71 
72 ////////////////////////////////////////////////////////////////////////////////
73 /// protected, recursive, function used by the class destructor and when Pruning
74 
76 {
77  if (node != NULL) { //If the node is not NULL...
78  this->DeleteNode(node->GetLeft()); //Delete its left node.
79  this->DeleteNode(node->GetRight()); //Delete its right node.
80 
81  delete node; // Delete the node in memory
82  }
83 }
84 
85 ////////////////////////////////////////////////////////////////////////////////
86 /// get left daughter node current node "n"
87 
89 {
90  return (Node*) n->GetLeft();
91 }
92 
93 ////////////////////////////////////////////////////////////////////////////////
94 /// get right daughter node current node "n"
95 
97 {
98  return (Node*) n->GetRight();
99 }
100 
101 ////////////////////////////////////////////////////////////////////////////////
102 /// return the number of nodes in the tree. (make a new count --> takes time)
103 
105 {
106  if (n == NULL){ //default, start at the tree top, then descend recursively
107  n = (Node*)this->GetRoot();
108  if (n == NULL) return 0 ;
109  }
110 
111  UInt_t countNodes=1;
112 
113  if (this->GetLeftDaughter(n) != NULL){
114  countNodes += this->CountNodes( this->GetLeftDaughter(n) );
115  }
116  if (this->GetRightDaughter(n) != NULL) {
117  countNodes += this->CountNodes( this->GetRightDaughter(n) );
118  }
119 
120  return fNNodes = countNodes;
121 }
122 
123 ////////////////////////////////////////////////////////////////////////////////
124 /// recursively print the tree
125 
126 void TMVA::BinaryTree::Print(std::ostream & os) const
127 {
128  this->GetRoot()->PrintRec(os);
129  os << "-1" << std::endl;
130 }
131 
132 ////////////////////////////////////////////////////////////////////////////////
133 /// add attributes to XML
134 
135 void* TMVA::BinaryTree::AddXMLTo(void* parent) const {
136  void* bdt = gTools().AddChild(parent, "BinaryTree");
137  gTools().AddAttr( bdt, "type" , ClassName() );
138  this->GetRoot()->AddXMLTo(bdt);
139  return bdt;
140 }
141 
142 ////////////////////////////////////////////////////////////////////////////////
143 /// read attributes from XML
144 
145 void TMVA::BinaryTree::ReadXML(void* node, UInt_t tmva_Version_Code ) {
146  this->DeleteNode( fRoot );
147  fRoot= CreateNode();
148 
149  void* trnode = gTools().GetChild(node);
150  fRoot->ReadXML(trnode, tmva_Version_Code);
151 
152  this->SetTotalTreeDepth();
153 }
154 
155 
156 ////////////////////////////////////////////////////////////////////////////////
157 /// print the tree recursinvely using the << operator
158 
159 std::ostream& TMVA::operator<< (std::ostream& os, const TMVA::BinaryTree& tree)
160 {
161  tree.Print(os);
162  return os; // Return the output stream.
163 }
164 
165 ////////////////////////////////////////////////////////////////////////////////
166 /// Read the binary tree from an input stream.
167 /// The input stream format depends on the tree type,
168 /// it is defined be the node of the tree
169 
170 void TMVA::BinaryTree::Read(std::istream & istr, UInt_t tmva_Version_Code )
171 {
172  Node * currentNode = GetRoot();
173  Node* parent = 0;
174 
175  if(currentNode==0) {
176  currentNode=CreateNode();
177  SetRoot(currentNode);
178  }
179 
180  while(1) {
181  if ( ! currentNode->ReadDataRecord(istr, tmva_Version_Code) ) {
182  delete currentNode;
183  this->SetTotalTreeDepth();
184  return;
185  }
186 
187  // find parent node
188  while( parent!=0 && parent->GetDepth() != currentNode->GetDepth()-1) parent=parent->GetParent();
189 
190  if (parent!=0) { // link new node to parent
191  currentNode->SetParent(parent);
192  if (currentNode->GetPos()=='l') parent->SetLeft(currentNode);
193  if (currentNode->GetPos()=='r') parent->SetRight(currentNode);
194  }
195 
196  parent = currentNode; // latest node read might be parent of new one
197 
198  currentNode = CreateNode(); // create a new node to be read next
199  }
200 }
201 
202 ////////////////////////////////////////////////////////////////////////////////
203 /// read the tree from an std::istream
204 
205 std::istream& TMVA::operator>> (std::istream& istr, TMVA::BinaryTree& tree)
206 {
207  tree.Read(istr);
208  return istr;
209 }
210 ////////////////////////////////////////////////////////////////////////////////
211 /// descend a tree to find all its leaf nodes, fill max depth reached in the
212 /// tree at the same time.
213 
215 {
216  if (n == NULL){ //default, start at the tree top, then descend recursively
217  n = (Node*) this->GetRoot();
218  if (n == NULL) {
219  Log() << kFATAL << "SetTotalTreeDepth: started with undefined ROOT node" <<Endl;
220  return ;
221  }
222  }
223  if (this->GetLeftDaughter(n) != NULL){
224  this->SetTotalTreeDepth( this->GetLeftDaughter(n) );
225  }
226  if (this->GetRightDaughter(n) != NULL) {
227  this->SetTotalTreeDepth( this->GetRightDaughter(n) );
228  }
229  if (n->GetDepth() > this->GetTotalTreeDepth()) this->SetTotalTreeDepth(n->GetDepth());
230 
231  return;
232 }
233 
234 ////////////////////////////////////////////////////////////////////////////////
235 
237  TTHREAD_TLS_DECL_ARG(MsgLogger,logger,"BinaryTree");
238  return logger;
239 }
virtual void * AddXMLTo(void *parent) const
add attributes to XML
Definition: BinaryTree.cxx:135
virtual void PrintRec(std::ostream &os) const =0
void * AddXMLTo(void *parent) const
add attributes to XML
Definition: Node.cxx:149
virtual const char * ClassName() const =0
MsgLogger & Endl(MsgLogger &ml)
Definition: MsgLogger.h:162
virtual void Read(std::istream &istr, UInt_t tmva_Version_Code=TMVA_VERSION_CODE)
Read the binary tree from an input stream.
Definition: BinaryTree.cxx:170
virtual ~BinaryTree()
destructor (deletes the nodes and "events" if owned by the tree
Definition: BinaryTree.cxx:66
UInt_t GetDepth() const
Definition: Node.h:118
virtual void SetRight(Node *r)
Definition: Node.h:97
void AddAttr(void *node, const char *, const T &value, Int_t precision=16)
Definition: Tools.h:309
void DeleteNode(Node *)
protected, recursive, function used by the class destructor and when Pruning
Definition: BinaryTree.cxx:75
void * AddChild(void *parent, const char *childname, const char *content=0, bool isRootNode=false)
add child node
Definition: Tools.cxx:1134
virtual Bool_t ReadDataRecord(std::istream &, UInt_t tmva_Version_Code=TMVA_VERSION_CODE)=0
Tools & gTools()
Definition: Tools.cxx:79
MsgLogger & Log() const
Definition: BinaryTree.cxx:236
virtual void SetLeft(Node *l)
Definition: Node.h:96
virtual Node * GetRight() const
Definition: Node.h:92
virtual Node * GetLeft() const
Definition: Node.h:91
void * GetChild(void *parent, const char *childname=0)
get child node
Definition: Tools.cxx:1158
void SetTotalTreeDepth(Int_t depth)
Definition: BinaryTree.h:101
void ReadXML(void *node, UInt_t tmva_Version_Code=TMVA_VERSION_CODE)
read attributes from XML
Definition: Node.cxx:165
virtual void Print(std::ostream &os) const
recursively print the tree
Definition: BinaryTree.cxx:126
virtual Node * GetParent() const
Definition: Node.h:93
unsigned int UInt_t
Definition: RtypesCore.h:42
virtual void ReadXML(void *node, UInt_t tmva_Version_Code=TMVA_VERSION_CODE)
read attributes from XML
Definition: BinaryTree.cxx:145
std::ostream & operator<<(std::ostream &os, const BinaryTree &tree)
print the tree recursinvely using the << operator
Definition: BinaryTree.cxx:159
std::istream & operator>>(std::istream &istr, BinaryTree &tree)
read the tree from an std::istream
Definition: BinaryTree.cxx:205
virtual void SetParent(Node *p)
Definition: Node.h:98
#define ClassImp(name)
Definition: Rtypes.h:279
UInt_t GetTotalTreeDepth() const
Definition: BinaryTree.h:99
virtual Node * CreateNode(UInt_t size=0) const =0
UInt_t CountNodes(Node *n=NULL)
return the number of nodes in the tree. (make a new count –> takes time)
Definition: BinaryTree.cxx:104
Abstract ClassifierFactory template that handles arbitrary types.
Node * GetRightDaughter(Node *n)
get right daughter node current node "n"
Definition: BinaryTree.cxx:96
char GetPos() const
Definition: Node.h:124
#define NULL
Definition: Rtypes.h:82
Node * GetLeftDaughter(Node *n)
get left daughter node current node "n"
Definition: BinaryTree.cxx:88
Definition: tree.py:1
virtual Node * GetRoot() const
Definition: BinaryTree.h:89
void SetRoot(Node *r)
Definition: BinaryTree.h:86
return
Definition: HLFactory.cxx:514
const Int_t n
Definition: legend1.C:16