Logo ROOT  
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 /*! \class TMVA::BinaryTree
32 \ingroup TMVA
33 
34 Base class for BinarySearch and Decision Trees.
35 
36 */
37 
38 #include <string>
39 #include <stdexcept>
40 
41 #include "ThreadLocalStorage.h"
42 
43 #include "TMVA/BinaryTree.h"
44 #include "TMVA/MsgLogger.h"
45 #include "TMVA/Event.h"
46 #include "TMVA/Node.h"
47 #include "TMVA/Tools.h"
48 #include "TMVA/Types.h"
49 
51 
52 ////////////////////////////////////////////////////////////////////////////////
53 /// constructor for a yet "empty" tree. Needs to be filled afterwards
54 
56 : fRoot ( NULL ),
57  fNNodes( 0 ),
58  fDepth ( 0 )
59 {
60 }
61 
62 ////////////////////////////////////////////////////////////////////////////////
63 ///destructor (deletes the nodes and "events" if owned by the tree
64 
66 {
67  this->DeleteNode( fRoot );
68  fRoot=0;
69 }
70 
71 ////////////////////////////////////////////////////////////////////////////////
72 /// protected, recursive, function used by the class destructor and when Pruning
73 
75 {
76  if (node != NULL) { //If the node is not NULL...
77  this->DeleteNode(node->GetLeft()); //Delete its left node.
78  this->DeleteNode(node->GetRight()); //Delete its right node.
79 
80  delete node; // Delete the node in memory
81  }
82 }
83 
84 ////////////////////////////////////////////////////////////////////////////////
85 /// get left daughter node current node "n"
86 
88 {
89  return (Node*) n->GetLeft();
90 }
91 
92 ////////////////////////////////////////////////////////////////////////////////
93 /// get right daughter node current node "n"
94 
96 {
97  return (Node*) n->GetRight();
98 }
99 
100 ////////////////////////////////////////////////////////////////////////////////
101 /// return the number of nodes in the tree. (make a new count --> takes time)
102 
104 {
105  if (n == NULL){ //default, start at the tree top, then descend recursively
106  n = (Node*)this->GetRoot();
107  if (n == NULL) return 0 ;
108  }
109 
110  UInt_t countNodes=1;
111 
112  if (this->GetLeftDaughter(n) != NULL){
113  countNodes += this->CountNodes( this->GetLeftDaughter(n) );
114  }
115  if (this->GetRightDaughter(n) != NULL) {
116  countNodes += this->CountNodes( this->GetRightDaughter(n) );
117  }
118 
119  return fNNodes = countNodes;
120 }
121 
122 ////////////////////////////////////////////////////////////////////////////////
123 /// recursively print the tree
124 
125 void TMVA::BinaryTree::Print(std::ostream & os) const
126 {
127  this->GetRoot()->PrintRec(os);
128  os << "-1" << std::endl;
129 }
130 
131 ////////////////////////////////////////////////////////////////////////////////
132 /// add attributes to XML
133 
134 void* TMVA::BinaryTree::AddXMLTo(void* parent) const {
135  void* bdt = gTools().AddChild(parent, "BinaryTree");
136  gTools().AddAttr( bdt, "type" , ClassName() );
137  this->GetRoot()->AddXMLTo(bdt);
138  return bdt;
139 }
140 
141 ////////////////////////////////////////////////////////////////////////////////
142 /// read attributes from XML
143 
144 void TMVA::BinaryTree::ReadXML(void* node, UInt_t tmva_Version_Code ) {
145  this->DeleteNode( fRoot );
146  fRoot= CreateNode();
147 
148  void* trnode = gTools().GetChild(node);
149  fRoot->ReadXML(trnode, tmva_Version_Code);
150 
151  this->SetTotalTreeDepth();
152 }
153 
154 
155 ////////////////////////////////////////////////////////////////////////////////
156 /// print the tree recursively using the << operator
157 
158 std::ostream& TMVA::operator<< (std::ostream& os, const TMVA::BinaryTree& tree)
159 {
160  tree.Print(os);
161  return os; // Return the output stream.
162 }
163 
164 ////////////////////////////////////////////////////////////////////////////////
165 /// Read the binary tree from an input stream.
166 /// The input stream format depends on the tree type,
167 /// it is defined be the node of the tree
168 
169 void TMVA::BinaryTree::Read(std::istream & istr, UInt_t tmva_Version_Code )
170 {
171  Node * currentNode = GetRoot();
172  Node* parent = 0;
173 
174  if(currentNode==0) {
175  currentNode=CreateNode();
176  SetRoot(currentNode);
177  }
178 
179  while(1) {
180  if ( ! currentNode->ReadDataRecord(istr, tmva_Version_Code) ) {
181  delete currentNode;
182  this->SetTotalTreeDepth();
183  return;
184  }
185 
186  // find parent node
187  while( parent!=0 && parent->GetDepth() != currentNode->GetDepth()-1) parent=parent->GetParent();
188 
189  if (parent!=0) { // link new node to parent
190  currentNode->SetParent(parent);
191  if (currentNode->GetPos()=='l') parent->SetLeft(currentNode);
192  if (currentNode->GetPos()=='r') parent->SetRight(currentNode);
193  }
194 
195  parent = currentNode; // latest node read might be parent of new one
196 
197  currentNode = CreateNode(); // create a new node to be read next
198  }
199 }
200 
201 ////////////////////////////////////////////////////////////////////////////////
202 /// read the tree from an std::istream
203 
204 std::istream& TMVA::operator>> (std::istream& istr, TMVA::BinaryTree& tree)
205 {
206  tree.Read(istr);
207  return istr;
208 }
209 ////////////////////////////////////////////////////////////////////////////////
210 /// descend a tree to find all its leaf nodes, fill max depth reached in the
211 /// tree at the same time.
212 
214 {
215  if (n == NULL){ //default, start at the tree top, then descend recursively
216  n = (Node*) this->GetRoot();
217  if (n == NULL) {
218  Log() << kFATAL << "SetTotalTreeDepth: started with undefined ROOT node" <<Endl;
219  return ;
220  }
221  }
222  if (this->GetLeftDaughter(n) != NULL){
223  this->SetTotalTreeDepth( this->GetLeftDaughter(n) );
224  }
225  if (this->GetRightDaughter(n) != NULL) {
226  this->SetTotalTreeDepth( this->GetRightDaughter(n) );
227  }
228  if (n->GetDepth() > this->GetTotalTreeDepth()) this->SetTotalTreeDepth(n->GetDepth());
229 
230  return;
231 }
232 
233 ////////////////////////////////////////////////////////////////////////////////
234 
236  TTHREAD_TLS_DECL_ARG(MsgLogger,logger,"BinaryTree");
237  return logger;
238 }
n
const Int_t n
Definition: legend1.C:16
TMVA::BinaryTree::DeleteNode
void DeleteNode(Node *)
protected, recursive, function used by the class destructor and when Pruning
Definition: BinaryTree.cxx:74
TMVA::Node::SetParent
virtual void SetParent(Node *p)
Definition: Node.h:96
TMVA::Tools::GetChild
void * GetChild(void *parent, const char *childname=0)
get child node
Definition: Tools.cxx:1162
TMVA::BinaryTree::GetLeftDaughter
Node * GetLeftDaughter(Node *n)
get left daughter node current node "n"
Definition: BinaryTree.cxx:87
tree
Definition: tree.py:1
ClassImp
#define ClassImp(name)
Definition: Rtypes.h:364
TMVA::Node::GetRight
virtual Node * GetRight() const
Definition: Node.h:90
TMath::Log
Double_t Log(Double_t x)
Definition: TMath.h:760
TMVA::Tools::AddChild
void * AddChild(void *parent, const char *childname, const char *content=0, bool isRootNode=false)
add child node
Definition: Tools.cxx:1136
TMVA::Node::GetDepth
UInt_t GetDepth() const
Definition: Node.h:116
TMVA::Node::GetParent
virtual Node * GetParent() const
Definition: Node.h:91
TMVA::BinaryTree::SetTotalTreeDepth
void SetTotalTreeDepth(Int_t depth)
Definition: BinaryTree.h:95
TMVA::operator<<
std::ostream & operator<<(std::ostream &os, const BinaryTree &tree)
TMVA::operator>>
std::istream & operator>>(std::istream &istr, BinaryTree &tree)
TMVA::Node
Node for the BinarySearch or Decision Trees.
Definition: Node.h:58
TMVA::BinaryTree::GetRightDaughter
Node * GetRightDaughter(Node *n)
get right daughter node current node "n"
Definition: BinaryTree.cxx:95
TMVA::Tools::AddAttr
void AddAttr(void *node, const char *, const T &value, Int_t precision=16)
add attribute to xml
Definition: Tools.h:353
TMVA::BinaryTree::~BinaryTree
virtual ~BinaryTree()
destructor (deletes the nodes and "events" if owned by the tree
Definition: BinaryTree.cxx:65
MsgLogger.h
TMVA::Node::SetLeft
virtual void SetLeft(Node *l)
Definition: Node.h:94
Node.h
TMVA::BinaryTree
Base class for BinarySearch and Decision Trees.
Definition: BinaryTree.h:62
Event.h
TMVA::Node::ReadDataRecord
virtual Bool_t ReadDataRecord(std::istream &, UInt_t tmva_Version_Code=TMVA_VERSION_CODE)=0
TMVA::BinaryTree::Log
MsgLogger & Log() const
Definition: BinaryTree.cxx:235
TMVA::BinaryTree::CountNodes
UInt_t CountNodes(Node *n=NULL)
return the number of nodes in the tree. (make a new count --> takes time)
Definition: BinaryTree.cxx:103
TMVA::Node::GetLeft
virtual Node * GetLeft() const
Definition: Node.h:89
Types.h
TMVA::BinaryTree::Print
virtual void Print(std::ostream &os) const
recursively print the tree
Definition: BinaryTree.cxx:125
TMVA::Endl
MsgLogger & Endl(MsgLogger &ml)
Definition: MsgLogger.h:158
unsigned int
TMVA::BinaryTree::ReadXML
virtual void ReadXML(void *node, UInt_t tmva_Version_Code=TMVA_VERSION_CODE)
read attributes from XML
Definition: BinaryTree.cxx:144
BinaryTree.h
TMVA::MsgLogger
ostringstream derivative to redirect and format output
Definition: MsgLogger.h:59
RooFit::ClassName
RooCmdArg ClassName(const char *name)
Definition: RooGlobalFunc.cxx:300
TMVA::BinaryTree::BinaryTree
BinaryTree(void)
constructor for a yet "empty" tree. Needs to be filled afterwards
Definition: BinaryTree.cxx:55
Tools.h
TMVA::BinaryTree::Read
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:169
TMVA::Node::SetRight
virtual void SetRight(Node *r)
Definition: Node.h:95
TMVA::gTools
Tools & gTools()
TMVA::BinaryTree::AddXMLTo
virtual void * AddXMLTo(void *parent) const
add attributes to XML
Definition: BinaryTree.cxx:134
ThreadLocalStorage.h
TMVA::Node::GetPos
char GetPos() const
Definition: Node.h:122