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
34Base 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
125void 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
134void* 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
144void 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
158std::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
169void 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
204std::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}
unsigned int UInt_t
Definition: RtypesCore.h:46
#define ClassImp(name)
Definition: Rtypes.h:364
Base class for BinarySearch and Decision Trees.
Definition: BinaryTree.h:62
Node * GetLeftDaughter(Node *n)
get left daughter node current node "n"
Definition: BinaryTree.cxx:87
Node * GetRightDaughter(Node *n)
get right daughter node current node "n"
Definition: BinaryTree.cxx:95
virtual void * AddXMLTo(void *parent) const
add attributes to XML
Definition: BinaryTree.cxx:134
virtual void ReadXML(void *node, UInt_t tmva_Version_Code=TMVA_VERSION_CODE)
read attributes from XML
Definition: BinaryTree.cxx:144
BinaryTree(void)
constructor for a yet "empty" tree. Needs to be filled afterwards
Definition: BinaryTree.cxx:55
void DeleteNode(Node *)
protected, recursive, function used by the class destructor and when Pruning
Definition: BinaryTree.cxx:74
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
UInt_t CountNodes(Node *n=NULL)
return the number of nodes in the tree. (make a new count --> takes time)
Definition: BinaryTree.cxx:103
void SetTotalTreeDepth(Int_t depth)
Definition: BinaryTree.h:95
MsgLogger & Log() const
Definition: BinaryTree.cxx:235
virtual void Print(std::ostream &os) const
recursively print the tree
Definition: BinaryTree.cxx:125
virtual ~BinaryTree()
destructor (deletes the nodes and "events" if owned by the tree
Definition: BinaryTree.cxx:65
ostringstream derivative to redirect and format output
Definition: MsgLogger.h:57
Node for the BinarySearch or Decision Trees.
Definition: Node.h:58
virtual Node * GetLeft() const
Definition: Node.h:89
virtual Node * GetParent() const
Definition: Node.h:91
virtual void SetRight(Node *r)
Definition: Node.h:95
char GetPos() const
Definition: Node.h:122
virtual void SetLeft(Node *l)
Definition: Node.h:94
virtual Bool_t ReadDataRecord(std::istream &, UInt_t tmva_Version_Code=TMVA_VERSION_CODE)=0
virtual void SetParent(Node *p)
Definition: Node.h:96
UInt_t GetDepth() const
Definition: Node.h:116
virtual Node * GetRight() const
Definition: Node.h:90
void * AddChild(void *parent, const char *childname, const char *content=0, bool isRootNode=false)
add child node
Definition: Tools.cxx:1124
void * GetChild(void *parent, const char *childname=0)
get child node
Definition: Tools.cxx:1150
void AddAttr(void *node, const char *, const T &value, Int_t precision=16)
add attribute to xml
Definition: Tools.h:347
@ kFATAL
Definition: Types.h:61
RooCmdArg ClassName(const char *name)
const Int_t n
Definition: legend1.C:16
std::istream & operator>>(std::istream &istr, BinaryTree &tree)
Tools & gTools()
std::ostream & operator<<(std::ostream &os, const BinaryTree &tree)
MsgLogger & Endl(MsgLogger &ml)
Definition: MsgLogger.h:148
Double_t Log(Double_t x)
Definition: TMath.h:710
Definition: tree.py:1