Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
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 * *
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 * (see tmva/doc/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
50
51////////////////////////////////////////////////////////////////////////////////
52/// constructor for a yet "empty" tree. Needs to be filled afterwards
53
55: fRoot ( NULL ),
56 fNNodes( 0 ),
57 fDepth ( 0 )
58{
59}
60
61////////////////////////////////////////////////////////////////////////////////
62///destructor (deletes the nodes and "events" if owned by the tree
63
65{
66 this->DeleteNode( fRoot );
67 fRoot=0;
68}
69
70////////////////////////////////////////////////////////////////////////////////
71/// protected, recursive, function used by the class destructor and when Pruning
72
74{
75 if (node != NULL) { //If the node is not NULL...
76 this->DeleteNode(node->GetLeft()); //Delete its left node.
77 this->DeleteNode(node->GetRight()); //Delete its right node.
78
79 delete node; // Delete the node in memory
80 }
81}
82
83////////////////////////////////////////////////////////////////////////////////
84/// get left daughter node current node "n"
85
87{
88 return (Node*) n->GetLeft();
89}
90
91////////////////////////////////////////////////////////////////////////////////
92/// get right daughter node current node "n"
93
95{
96 return (Node*) n->GetRight();
97}
98
99////////////////////////////////////////////////////////////////////////////////
100/// return the number of nodes in the tree. (make a new count --> takes time)
101
103{
104 if (n == NULL){ //default, start at the tree top, then descend recursively
105 n = (Node*)this->GetRoot();
106 if (n == NULL) return 0 ;
107 }
108
110
111 if (this->GetLeftDaughter(n) != NULL){
112 countNodes += this->CountNodes( this->GetLeftDaughter(n) );
113 }
114 if (this->GetRightDaughter(n) != NULL) {
115 countNodes += this->CountNodes( this->GetRightDaughter(n) );
116 }
117
118 return fNNodes = countNodes;
119}
120
121////////////////////////////////////////////////////////////////////////////////
122/// recursively print the tree
123
124void TMVA::BinaryTree::Print(std::ostream & os) const
125{
126 this->GetRoot()->PrintRec(os);
127 os << "-1" << std::endl;
128}
129
130////////////////////////////////////////////////////////////////////////////////
131/// add attributes to XML
132
133void* TMVA::BinaryTree::AddXMLTo(void* parent) const {
134 void* bdt = gTools().AddChild(parent, "BinaryTree");
135 gTools().AddAttr( bdt, "type" , ClassName() );
136 this->GetRoot()->AddXMLTo(bdt);
137 return bdt;
138}
139
140////////////////////////////////////////////////////////////////////////////////
141/// read attributes from XML
142
144 this->DeleteNode( fRoot );
145 fRoot= CreateNode();
146
147 void* trnode = gTools().GetChild(node);
148 fRoot->ReadXML(trnode, tmva_Version_Code);
149
150 this->SetTotalTreeDepth();
151}
152
153
154////////////////////////////////////////////////////////////////////////////////
155/// print the tree recursively using the << operator
156
157std::ostream& TMVA::operator<< (std::ostream& os, const TMVA::BinaryTree& tree)
158{
159 tree.Print(os);
160 return os; // Return the output stream.
161}
162
163////////////////////////////////////////////////////////////////////////////////
164/// Read the binary tree from an input stream.
165/// The input stream format depends on the tree type,
166/// it is defined be the node of the tree
167
169{
170 Node * currentNode = GetRoot();
171 Node* parent = 0;
172
173 if(currentNode==0) {
174 currentNode=CreateNode();
175 SetRoot(currentNode);
176 }
177
178 while(1) {
179 if ( ! currentNode->ReadDataRecord(istr, tmva_Version_Code) ) {
180 delete currentNode;
181 this->SetTotalTreeDepth();
182 return;
183 }
184
185 // find parent node
186 while( parent!=0 && parent->GetDepth() != currentNode->GetDepth()-1) parent=parent->GetParent();
187
188 if (parent!=0) { // link new node to parent
189 currentNode->SetParent(parent);
190 if (currentNode->GetPos()=='l') parent->SetLeft(currentNode);
191 if (currentNode->GetPos()=='r') parent->SetRight(currentNode);
192 }
193
194 parent = currentNode; // latest node read might be parent of new one
195
196 currentNode = CreateNode(); // create a new node to be read next
197 }
198}
199
200////////////////////////////////////////////////////////////////////////////////
201/// read the tree from an std::istream
202
203std::istream& TMVA::operator>> (std::istream& istr, TMVA::BinaryTree& tree)
204{
205 tree.Read(istr);
206 return istr;
207}
208////////////////////////////////////////////////////////////////////////////////
209/// descend a tree to find all its leaf nodes, fill max depth reached in the
210/// tree at the same time.
211
213{
214 if (n == NULL){ //default, start at the tree top, then descend recursively
215 n = (Node*) this->GetRoot();
216 if (n == NULL) {
217 Log() << kFATAL << "SetTotalTreeDepth: started with undefined ROOT node" <<Endl;
218 return ;
219 }
220 }
221 if (this->GetLeftDaughter(n) != NULL){
222 this->SetTotalTreeDepth( this->GetLeftDaughter(n) );
223 }
224 if (this->GetRightDaughter(n) != NULL) {
225 this->SetTotalTreeDepth( this->GetRightDaughter(n) );
226 }
227 if (n->GetDepth() > this->GetTotalTreeDepth()) this->SetTotalTreeDepth(n->GetDepth());
228
229 return;
230}
231
232////////////////////////////////////////////////////////////////////////////////
233
static ROOT::Experimental::RTreeMapBase::Node CreateNode(const ROOT::Experimental::RNTupleInspector &insp, const ROOT::RFieldDescriptor &fldDesc, std::uint64_t childrenIdx, std::uint64_t nChildren, ROOT::DescriptorId_t rootId, size_t rootSize)
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
Base class for BinarySearch and Decision Trees.
Definition BinaryTree.h:62
UInt_t CountNodes(Node *n=nullptr)
return the number of nodes in the tree. (make a new count --> takes time)
Node * GetLeftDaughter(Node *n)
get left daughter node current node "n"
Node * GetRightDaughter(Node *n)
get right daughter node current node "n"
virtual void * AddXMLTo(void *parent) const
add attributes to XML
BinaryTree(void)
constructor for a yet "empty" tree. Needs to be filled afterwards
void DeleteNode(Node *)
protected, recursive, function used by the class destructor and when Pruning
void SetTotalTreeDepth(Int_t depth)
Definition BinaryTree.h:95
MsgLogger & Log() const
virtual void Print(std::ostream &os) const
recursively print the tree
virtual ~BinaryTree()
destructor (deletes the nodes and "events" if owned by the tree
virtual void ReadXML(void *node, UInt_t tmva_Version_Code=262657)
read attributes from XML
virtual void Read(std::istream &istr, UInt_t tmva_Version_Code=262657)
Read the binary tree from an input stream.
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 void SetParent(Node *p)
Definition Node.h:96
virtual Bool_t ReadDataRecord(std::istream &, UInt_t tmva_Version_Code=262657)=0
UInt_t GetDepth() const
Definition Node.h:116
virtual Node * GetRight() const
Definition Node.h:90
void * GetChild(void *parent, const char *childname=nullptr)
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
void * AddChild(void *parent, const char *childname, const char *content=nullptr, bool isRootNode=false)
add child node
Definition Tools.cxx:1124
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