gtsam  4.1.0
gtsam
DecisionTree-inl.h
1 /* ----------------------------------------------------------------------------
2 
3  * GTSAM Copyright 2010, Georgia Tech Research Corporation,
4  * Atlanta, Georgia 30332-0415
5  * All Rights Reserved
6  * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
7 
8  * See LICENSE for the license information
9 
10  * -------------------------------------------------------------------------- */
11 
20 #pragma once
21 
23 #include <gtsam/base/Testable.h>
24 
25 #include <boost/format.hpp>
26 #include <boost/optional.hpp>
27 #include <boost/tuple/tuple.hpp>
28 #include <boost/assign/std/vector.hpp>
29 using boost::assign::operator+=;
30 #include <boost/unordered_set.hpp>
31 #include <boost/noncopyable.hpp>
32 
33 #include <list>
34 #include <cmath>
35 #include <fstream>
36 #include <sstream>
37 
38 namespace gtsam {
39 
40  /*********************************************************************************/
41  // Node
42  /*********************************************************************************/
43 #ifdef DT_DEBUG_MEMORY
44  template<typename L, typename Y>
45  int DecisionTree<L, Y>::Node::nrNodes = 0;
46 #endif
47 
48  /*********************************************************************************/
49  // Leaf
50  /*********************************************************************************/
51  template<typename L, typename Y>
52  class DecisionTree<L, Y>::Leaf: public DecisionTree<L, Y>::Node {
53 
55  Y constant_;
56 
57  public:
58 
60  Leaf(const Y& constant) :
61  constant_(constant) {}
62 
64  const Y& constant() const {
65  return constant_;
66  }
67 
69  bool sameLeaf(const Leaf& q) const override {
70  return constant_ == q.constant_;
71  }
72 
74  bool sameLeaf(const Node& q) const override {
75  return (q.isLeaf() && q.sameLeaf(*this));
76  }
77 
79  bool equals(const Node& q, double tol) const override {
80  const Leaf* other = dynamic_cast<const Leaf*> (&q);
81  if (!other) return false;
82  return std::abs(double(this->constant_ - other->constant_)) < tol;
83  }
84 
86  void print(const std::string& s) const override {
87  bool showZero = true;
88  if (showZero || constant_) std::cout << s << " Leaf " << constant_ << std::endl;
89  }
90 
92  void dot(std::ostream& os, bool showZero) const override {
93  if (showZero || constant_) os << "\"" << this->id() << "\" [label=\""
94  << boost::format("%4.2g") % constant_
95  << "\", shape=box, rank=sink, height=0.35, fixedsize=true]\n"; // width=0.55,
96  }
97 
99  const Y& operator()(const Assignment<L>& x) const override {
100  return constant_;
101  }
102 
104  NodePtr apply(const Unary& op) const override {
105  NodePtr f(new Leaf(op(constant_)));
106  return f;
107  }
108 
109  // Apply binary operator "h = f op g" on Leaf node
110  // Note op is not assumed commutative so we need to keep track of order
111  // Simply calls apply on argument to call correct virtual method:
112  // fL.apply_f_op_g(gL) -> gL.apply_g_op_fL(fL) (below)
113  // fL.apply_f_op_g(gC) -> gC.apply_g_op_fL(fL) (Choice)
114  NodePtr apply_f_op_g(const Node& g, const Binary& op) const override {
115  return g.apply_g_op_fL(*this, op);
116  }
117 
118  // Applying binary operator to two leaves results in a leaf
119  NodePtr apply_g_op_fL(const Leaf& fL, const Binary& op) const override {
120  NodePtr h(new Leaf(op(fL.constant_, constant_))); // fL op gL
121  return h;
122  }
123 
124  // If second argument is a Choice node, call it's apply with leaf as second
125  NodePtr apply_g_op_fC(const Choice& fC, const Binary& op) const override {
126  return fC.apply_fC_op_gL(*this, op); // operand order back to normal
127  }
128 
130  NodePtr choose(const L& label, size_t index) const override {
131  return NodePtr(new Leaf(constant()));
132  }
133 
134  bool isLeaf() const override { return true; }
135 
136  }; // Leaf
137 
138  /*********************************************************************************/
139  // Choice
140  /*********************************************************************************/
141  template<typename L, typename Y>
142  class DecisionTree<L, Y>::Choice: public DecisionTree<L, Y>::Node {
143 
145  L label_;
146 
148  std::vector<NodePtr> branches_;
149 
150  private:
152  size_t allSame_;
153 
154  typedef boost::shared_ptr<const Choice> ChoicePtr;
155 
156  public:
157 
158  virtual ~Choice() {
159 #ifdef DT_DEBUG_MEMORY
160  std::std::cout << Node::nrNodes << " destructing (Choice) " << this->id() << std::std::endl;
161 #endif
162  }
163 
165  static NodePtr Unique(const ChoicePtr& f) {
166 #ifndef DT_NO_PRUNING
167  if (f->allSame_) {
168  assert(f->branches().size() > 0);
169  NodePtr f0 = f->branches_[0];
170  assert(f0->isLeaf());
171  NodePtr newLeaf(new Leaf(boost::dynamic_pointer_cast<const Leaf>(f0)->constant()));
172  return newLeaf;
173  } else
174 #endif
175  return f;
176  }
177 
178  bool isLeaf() const override { return false; }
179 
181  Choice(const L& label, size_t count) :
182  label_(label), allSame_(true) {
183  branches_.reserve(count);
184  }
185 
189  Choice(const Choice& f, const Choice& g, const Binary& op) :
190  allSame_(true) {
191 
192  // Choose what to do based on label
193  if (f.label() > g.label()) {
194  // f higher than g
195  label_ = f.label();
196  size_t count = f.nrChoices();
197  branches_.reserve(count);
198  for (size_t i = 0; i < count; i++)
199  push_back(f.branches_[i]->apply_f_op_g(g, op));
200  } else if (g.label() > f.label()) {
201  // f lower than g
202  label_ = g.label();
203  size_t count = g.nrChoices();
204  branches_.reserve(count);
205  for (size_t i = 0; i < count; i++)
206  push_back(g.branches_[i]->apply_g_op_fC(f, op));
207  } else {
208  // f same level as g
209  label_ = f.label();
210  size_t count = f.nrChoices();
211  branches_.reserve(count);
212  for (size_t i = 0; i < count; i++)
213  push_back(f.branches_[i]->apply_f_op_g(*g.branches_[i], op));
214  }
215  }
216 
217  const L& label() const {
218  return label_;
219  }
220 
221  size_t nrChoices() const {
222  return branches_.size();
223  }
224 
225  const std::vector<NodePtr>& branches() const {
226  return branches_;
227  }
228 
230  void push_back(const NodePtr& node) {
231  // allSame_ is restricted to leaf nodes in a decision tree
232  if (allSame_ && !branches_.empty()) {
233  allSame_ = node->sameLeaf(*branches_.back());
234  }
235  branches_.push_back(node);
236  }
237 
239  void print(const std::string& s) const override {
240  std::cout << s << " Choice(";
241  // std::cout << this << ",";
242  std::cout << label_ << ") " << std::endl;
243  for (size_t i = 0; i < branches_.size(); i++)
244  branches_[i]->print((boost::format("%s %d") % s % i).str());
245  }
246 
248  void dot(std::ostream& os, bool showZero) const override {
249  os << "\"" << this->id() << "\" [shape=circle, label=\"" << label_
250  << "\"]\n";
251  for (size_t i = 0; i < branches_.size(); i++) {
252  NodePtr branch = branches_[i];
253 
254  // Check if zero
255  if (!showZero) {
256  const Leaf* leaf = dynamic_cast<const Leaf*> (branch.get());
257  if (leaf && !leaf->constant()) continue;
258  }
259 
260  os << "\"" << this->id() << "\" -> \"" << branch->id() << "\"";
261  if (i == 0) os << " [style=dashed]";
262  if (i > 1) os << " [style=bold]";
263  os << std::endl;
264  branch->dot(os, showZero);
265  }
266  }
267 
269  bool sameLeaf(const Leaf& q) const override {
270  return false;
271  }
272 
274  bool sameLeaf(const Node& q) const override {
275  return (q.isLeaf() && q.sameLeaf(*this));
276  }
277 
279  bool equals(const Node& q, double tol) const override {
280  const Choice* other = dynamic_cast<const Choice*> (&q);
281  if (!other) return false;
282  if (this->label_ != other->label_) return false;
283  if (branches_.size() != other->branches_.size()) return false;
284  // we don't care about shared pointers being equal here
285  for (size_t i = 0; i < branches_.size(); i++)
286  if (!(branches_[i]->equals(*(other->branches_[i]), tol))) return false;
287  return true;
288  }
289 
291  const Y& operator()(const Assignment<L>& x) const override {
292 #ifndef NDEBUG
293  typename Assignment<L>::const_iterator it = x.find(label_);
294  if (it == x.end()) {
295  std::cout << "Trying to find value for " << label_ << std::endl;
296  throw std::invalid_argument(
297  "DecisionTree::operator(): value undefined for a label");
298  }
299 #endif
300  size_t index = x.at(label_);
301  NodePtr child = branches_[index];
302  return (*child)(x);
303  }
304 
308  Choice(const L& label, const Choice& f, const Unary& op) :
309  label_(label), allSame_(true) {
310 
311  branches_.reserve(f.branches_.size()); // reserve space
312  for (const NodePtr& branch: f.branches_)
313  push_back(branch->apply(op));
314  }
315 
317  NodePtr apply(const Unary& op) const override {
318  boost::shared_ptr<Choice> r(new Choice(label_, *this, op));
319  return Unique(r);
320  }
321 
322  // Apply binary operator "h = f op g" on Choice node
323  // Note op is not assumed commutative so we need to keep track of order
324  // Simply calls apply on argument to call correct virtual method:
325  // fC.apply_f_op_g(gL) -> gL.apply_g_op_fC(fC) -> (Leaf)
326  // fC.apply_f_op_g(gC) -> gC.apply_g_op_fC(fC) -> (below)
327  NodePtr apply_f_op_g(const Node& g, const Binary& op) const override {
328  return g.apply_g_op_fC(*this, op);
329  }
330 
331  // If second argument of binary op is Leaf node, recurse on branches
332  NodePtr apply_g_op_fL(const Leaf& fL, const Binary& op) const override {
333  boost::shared_ptr<Choice> h(new Choice(label(), nrChoices()));
334  for(NodePtr branch: branches_)
335  h->push_back(fL.apply_f_op_g(*branch, op));
336  return Unique(h);
337  }
338 
339  // If second argument of binary op is Choice, call constructor
340  NodePtr apply_g_op_fC(const Choice& fC, const Binary& op) const override {
341  boost::shared_ptr<Choice> h(new Choice(fC, *this, op));
342  return Unique(h);
343  }
344 
345  // If second argument of binary op is Leaf
346  template<typename OP>
347  NodePtr apply_fC_op_gL(const Leaf& gL, OP op) const {
348  boost::shared_ptr<Choice> h(new Choice(label(), nrChoices()));
349  for(const NodePtr& branch: branches_)
350  h->push_back(branch->apply_f_op_g(gL, op));
351  return Unique(h);
352  }
353 
355  NodePtr choose(const L& label, size_t index) const override {
356  if (label_ == label)
357  return branches_[index]; // choose branch
358 
359  // second case, not label of interest, just recurse
360  boost::shared_ptr<Choice> r(new Choice(label_, branches_.size()));
361  for(const NodePtr& branch: branches_)
362  r->push_back(branch->choose(label, index));
363  return Unique(r);
364  }
365 
366  }; // Choice
367 
368  /*********************************************************************************/
369  // DecisionTree
370  /*********************************************************************************/
371  template<typename L, typename Y>
373  }
374 
375  template<typename L, typename Y>
376  DecisionTree<L, Y>::DecisionTree(const NodePtr& root) :
377  root_(root) {
378  }
379 
380  /*********************************************************************************/
381  template<typename L, typename Y>
383  root_ = NodePtr(new Leaf(y));
384  }
385 
386  /*********************************************************************************/
387  template<typename L, typename Y>
389  const L& label, const Y& y1, const Y& y2) {
390  boost::shared_ptr<Choice> a(new Choice(label, 2));
391  NodePtr l1(new Leaf(y1)), l2(new Leaf(y2));
392  a->push_back(l1);
393  a->push_back(l2);
394  root_ = Choice::Unique(a);
395  }
396 
397  /*********************************************************************************/
398  template<typename L, typename Y>
400  const LabelC& labelC, const Y& y1, const Y& y2) {
401  if (labelC.second != 2) throw std::invalid_argument(
402  "DecisionTree: binary constructor called with non-binary label");
403  boost::shared_ptr<Choice> a(new Choice(labelC.first, 2));
404  NodePtr l1(new Leaf(y1)), l2(new Leaf(y2));
405  a->push_back(l1);
406  a->push_back(l2);
407  root_ = Choice::Unique(a);
408  }
409 
410  /*********************************************************************************/
411  template<typename L, typename Y>
412  DecisionTree<L, Y>::DecisionTree(const std::vector<LabelC>& labelCs,
413  const std::vector<Y>& ys) {
414  // call recursive Create
415  root_ = create(labelCs.begin(), labelCs.end(), ys.begin(), ys.end());
416  }
417 
418  /*********************************************************************************/
419  template<typename L, typename Y>
420  DecisionTree<L, Y>::DecisionTree(const std::vector<LabelC>& labelCs,
421  const std::string& table) {
422 
423  // Convert std::string to values of type Y
424  std::vector<Y> ys;
425  std::istringstream iss(table);
426  copy(std::istream_iterator<Y>(iss), std::istream_iterator<Y>(),
427  back_inserter(ys));
428 
429  // now call recursive Create
430  root_ = create(labelCs.begin(), labelCs.end(), ys.begin(), ys.end());
431  }
432 
433  /*********************************************************************************/
434  template<typename L, typename Y>
435  template<typename Iterator> DecisionTree<L, Y>::DecisionTree(
436  Iterator begin, Iterator end, const L& label) {
437  root_ = compose(begin, end, label);
438  }
439 
440  /*********************************************************************************/
441  template<typename L, typename Y>
443  const DecisionTree& f0, const DecisionTree& f1) {
444  std::vector<DecisionTree> functions;
445  functions += f0, f1;
446  root_ = compose(functions.begin(), functions.end(), label);
447  }
448 
449  /*********************************************************************************/
450  template<typename L, typename Y>
451  template<typename M, typename X>
453  const std::map<M, L>& map, boost::function<Y(const X&)> op) {
454  root_ = convert(other.root_, map, op);
455  }
456 
457  /*********************************************************************************/
458  // Called by two constructors above.
459  // Takes a label and a corresponding range of decision trees, and creates a new
460  // decision tree. However, the order of the labels needs to be respected, so we
461  // cannot just create a root Choice node on the label: if the label is not the
462  // highest label, we need to do a complicated and expensive recursive call.
463  template<typename L, typename Y> template<typename Iterator>
465  Iterator end, const L& label) const {
466 
467  // find highest label among branches
468  boost::optional<L> highestLabel;
469  size_t nrChoices = 0;
470  for (Iterator it = begin; it != end; it++) {
471  if (it->root_->isLeaf())
472  continue;
473  boost::shared_ptr<const Choice> c =
474  boost::dynamic_pointer_cast<const Choice>(it->root_);
475  if (!highestLabel || c->label() > *highestLabel) {
476  highestLabel.reset(c->label());
477  nrChoices = c->nrChoices();
478  }
479  }
480 
481  // if label is already in correct order, just put together a choice on label
482  if (!nrChoices || !highestLabel || label > *highestLabel) {
483  boost::shared_ptr<Choice> choiceOnLabel(new Choice(label, end - begin));
484  for (Iterator it = begin; it != end; it++)
485  choiceOnLabel->push_back(it->root_);
486  return Choice::Unique(choiceOnLabel);
487  } else {
488  // Set up a new choice on the highest label
489  boost::shared_ptr<Choice> choiceOnHighestLabel(new Choice(*highestLabel, nrChoices));
490  // now, for all possible values of highestLabel
491  for (size_t index = 0; index < nrChoices; index++) {
492  // make a new set of functions for composing by iterating over the given
493  // functions, and selecting the appropriate branch.
494  std::vector<DecisionTree> functions;
495  for (Iterator it = begin; it != end; it++) {
496  // by restricting the input functions to value i for labelBelow
497  DecisionTree chosen = it->choose(*highestLabel, index);
498  functions.push_back(chosen);
499  }
500  // We then recurse, for all values of the highest label
501  NodePtr fi = compose(functions.begin(), functions.end(), label);
502  choiceOnHighestLabel->push_back(fi);
503  }
504  return Choice::Unique(choiceOnHighestLabel);
505  }
506  }
507 
508  /*********************************************************************************/
509  // "create" is a bit of a complicated thing, but very useful.
510  // It takes a range of labels and a corresponding range of values,
511  // and creates a decision tree, as follows:
512  // - if there is only one label, creates a choice node with values in leaves
513  // - otherwise, it evenly splits up the range of values and creates a tree for
514  // each sub-range, and assigns that tree to first label's choices
515  // Example:
516  // create([B A],[1 2 3 4]) would call
517  // create([A],[1 2])
518  // create([A],[3 4])
519  // and produce
520  // B=0
521  // A=0: 1
522  // A=1: 2
523  // B=1
524  // A=0: 3
525  // A=1: 4
526  // Note, through the magic of "compose", create([A B],[1 2 3 4]) will produce
527  // exactly the same tree as above: the highest label is always the root.
528  // However, it will be *way* faster if labels are given highest to lowest.
529  template<typename L, typename Y>
530  template<typename It, typename ValueIt>
532  It begin, It end, ValueIt beginY, ValueIt endY) const {
533 
534  // get crucial counts
535  size_t nrChoices = begin->second;
536  size_t size = endY - beginY;
537 
538  // Find the next key to work on
539  It labelC = begin + 1;
540  if (labelC == end) {
541  // Base case: only one key left
542  // Create a simple choice node with values as leaves.
543  if (size != nrChoices) {
544  std::cout << "Trying to create DD on " << begin->first << std::endl;
545  std::cout << boost::format("DecisionTree::create: expected %d values but got %d instead") % nrChoices % size << std::endl;
546  throw std::invalid_argument("DecisionTree::create invalid argument");
547  }
548  boost::shared_ptr<Choice> choice(new Choice(begin->first, endY - beginY));
549  for (ValueIt y = beginY; y != endY; y++)
550  choice->push_back(NodePtr(new Leaf(*y)));
551  return Choice::Unique(choice);
552  }
553 
554  // Recursive case: perform "Shannon expansion"
555  // Creates one tree (i.e.,function) for each choice of current key
556  // by calling create recursively, and then puts them all together.
557  std::vector<DecisionTree> functions;
558  size_t split = size / nrChoices;
559  for (size_t i = 0; i < nrChoices; i++, beginY += split) {
560  NodePtr f = create<It, ValueIt>(labelC, end, beginY, beginY + split);
561  functions += DecisionTree(f);
562  }
563  return compose(functions.begin(), functions.end(), begin->first);
564  }
565 
566  /*********************************************************************************/
567  template<typename L, typename Y>
568  template<typename M, typename X>
570  const typename DecisionTree<M, X>::NodePtr& f, const std::map<M, L>& map,
571  boost::function<Y(const X&)> op) {
572 
573  typedef DecisionTree<M, X> MX;
574  typedef typename MX::Leaf MXLeaf;
575  typedef typename MX::Choice MXChoice;
576  typedef typename MX::NodePtr MXNodePtr;
577  typedef DecisionTree<L, Y> LY;
578 
579  // ugliness below because apparently we can't have templated virtual functions
580  // If leaf, apply unary conversion "op" and create a unique leaf
581  const MXLeaf* leaf = dynamic_cast<const MXLeaf*> (f.get());
582  if (leaf) return NodePtr(new Leaf(op(leaf->constant())));
583 
584  // Check if Choice
585  boost::shared_ptr<const MXChoice> choice = boost::dynamic_pointer_cast<const MXChoice> (f);
586  if (!choice) throw std::invalid_argument(
587  "DecisionTree::Convert: Invalid NodePtr");
588 
589  // get new label
590  M oldLabel = choice->label();
591  L newLabel = map.at(oldLabel);
592 
593  // put together via Shannon expansion otherwise not sorted.
594  std::vector<LY> functions;
595  for(const MXNodePtr& branch: choice->branches()) {
596  LY converted(convert<M, X>(branch, map, op));
597  functions += converted;
598  }
599  return LY::compose(functions.begin(), functions.end(), newLabel);
600  }
601 
602  /*********************************************************************************/
603  template<typename L, typename Y>
604  bool DecisionTree<L, Y>::equals(const DecisionTree& other, double tol) const {
605  return root_->equals(*other.root_, tol);
606  }
607 
608  template<typename L, typename Y>
609  void DecisionTree<L, Y>::print(const std::string& s) const {
610  root_->print(s);
611  }
612 
613  template<typename L, typename Y>
614  bool DecisionTree<L, Y>::operator==(const DecisionTree& other) const {
615  return root_->equals(*other.root_);
616  }
617 
618  template<typename L, typename Y>
620  return root_->operator ()(x);
621  }
622 
623  template<typename L, typename Y>
625  return DecisionTree(root_->apply(op));
626  }
627 
628  /*********************************************************************************/
629  template<typename L, typename Y>
631  const Binary& op) const {
632  // apply the operaton on the root of both diagrams
633  NodePtr h = root_->apply_f_op_g(*g.root_, op);
634  // create a new class with the resulting root "h"
635  DecisionTree result(h);
636  return result;
637  }
638 
639  /*********************************************************************************/
640  // The way this works:
641  // We have an ADT, picture it as a tree.
642  // At a certain depth, we have a branch on "label".
643  // The function "choose(label,index)" will return a tree of one less depth,
644  // where there is no more branch on "label": only the subtree under that
645  // branch point corresponding to the value "index" is left instead.
646  // The function below get all these smaller trees and "ops" them together.
647  // This implements marginalization in Darwiche09book, pg 330
648  template<typename L, typename Y>
650  size_t cardinality, const Binary& op) const {
651  DecisionTree result = choose(label, 0);
652  for (size_t index = 1; index < cardinality; index++) {
653  DecisionTree chosen = choose(label, index);
654  result = result.apply(chosen, op);
655  }
656  return result;
657  }
658 
659  /*********************************************************************************/
660  template<typename L, typename Y>
661  void DecisionTree<L, Y>::dot(std::ostream& os, bool showZero) const {
662  os << "digraph G {\n";
663  root_->dot(os, showZero);
664  os << " [ordering=out]}" << std::endl;
665  }
666 
667  template<typename L, typename Y>
668  void DecisionTree<L, Y>::dot(const std::string& name, bool showZero) const {
669  std::ofstream os((name + ".dot").c_str());
670  dot(os, showZero);
671  int result = system(
672  ("dot -Tpdf " + name + ".dot -o " + name + ".pdf >& /dev/null").c_str());
673  if (result==-1) throw std::runtime_error("DecisionTree::dot system call failed");
674 }
675 
676 /*********************************************************************************/
677 
678 } // namespace gtsam
679 
680 
gtsam::DecisionTree::Choice::sameLeaf
bool sameLeaf(const Node &q) const override
polymorphic equality: if q is a leaf, could be...
Definition: DecisionTree-inl.h:274
gtsam::DecisionTree::Choice::Choice
Choice(const Choice &f, const Choice &g, const Binary &op)
Construct from applying binary op to two Choice nodes.
Definition: DecisionTree-inl.h:189
DecisionTree.h
Decision Tree for use in DiscreteFactors.
Testable.h
Concept check for values that can be used in unit tests.
gtsam::DecisionTree::DecisionTree
DecisionTree()
Default constructor.
Definition: DecisionTree-inl.h:372
gtsam::equals
Template to create a binary predicate.
Definition: Testable.h:110
gtsam::DecisionTree::choose
DecisionTree choose(const L &label, size_t index) const
create a new function where value(label)==index It's like "restrict" in Darwiche09book pg329,...
Definition: DecisionTree.h:180
gtsam::DecisionTree::LabelC
std::pair< L, size_t > LabelC
A label annotated with cardinality.
Definition: DecisionTree.h:45
gtsam::DecisionTree::apply
DecisionTree apply(const Unary &op) const
apply Unary operation "op" to f
Definition: DecisionTree-inl.h:624
gtsam::DecisionTree
Decision Tree L = label for variables Y = function range (any algebra), e.g., bool,...
Definition: DecisionTree.h:36
gtsam::Assignment
An assignment from labels to value index (size_t).
Definition: Assignment.h:34
gtsam::DecisionTree::dot
void dot(std::ostream &os, bool showZero=true) const
output to graphviz format, stream version
Definition: DecisionTree-inl.h:661
gtsam::DecisionTree::Choice::push_back
void push_back(const NodePtr &node)
add a branch: TODO merge into constructor
Definition: DecisionTree-inl.h:230
gtsam::DecisionTree::Choice::equals
bool equals(const Node &q, double tol) const override
equality up to tolerance
Definition: DecisionTree-inl.h:279
gtsam::DecisionTree::Choice::Choice
Choice(const L &label, const Choice &f, const Unary &op)
Construct from applying unary op to a Choice node.
Definition: DecisionTree-inl.h:308
gtsam::DecisionTree::Leaf::sameLeaf
bool sameLeaf(const Node &q) const override
polymorphic equality: is q is a leaf, could be
Definition: DecisionTree-inl.h:74
gtsam::DecisionTree::Choice::choose
NodePtr choose(const L &label, size_t index) const override
choose a branch, recursively
Definition: DecisionTree-inl.h:355
gtsam::DecisionTree::Choice::Choice
Choice(const L &label, size_t count)
Constructor, given choice label and mandatory expected branch count.
Definition: DecisionTree-inl.h:181
gtsam::DecisionTree::Leaf::print
void print(const std::string &s) const override
print
Definition: DecisionTree-inl.h:86
gtsam::DecisionTree::Choice
Definition: DecisionTree-inl.h:142
gtsam::DecisionTree::Leaf::equals
bool equals(const Node &q, double tol) const override
equality up to tolerance
Definition: DecisionTree-inl.h:79
gtsam::DecisionTree::Leaf::constant
const Y & constant() const
return the constant
Definition: DecisionTree-inl.h:64
gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
gtsam::DecisionTree::print
void print(const std::string &s="DecisionTree") const
GTSAM-style print.
Definition: DecisionTree-inl.h:609
gtsam::DecisionTree::Choice::apply
NodePtr apply(const Unary &op) const override
apply unary operator
Definition: DecisionTree-inl.h:317
gtsam::DecisionTree::operator()
const Y & operator()(const Assignment< L > &x) const
evaluate
Definition: DecisionTree-inl.h:619
gtsam::DecisionTree::Choice::Unique
static NodePtr Unique(const ChoicePtr &f)
If all branches of a choice node f are the same, just return a branch.
Definition: DecisionTree-inl.h:165
gtsam::split
void split(const G &g, const PredecessorMap< KEY > &tree, G &Ab1, G &Ab2)
Split the graph into two parts: one corresponds to the given spanning tree, and the other corresponds...
Definition: graph-inl.h:255
gtsam::DecisionTree::convert
NodePtr convert(const typename DecisionTree< M, X >::NodePtr &f, const std::map< M, L > &map, boost::function< Y(const X &)> op)
Convert to a different type.
Definition: DecisionTree-inl.h:569
gtsam::DecisionTree::combine
DecisionTree combine(const L &label, size_t cardinality, const Binary &op) const
combine subtrees on key with binary operation "op"
Definition: DecisionTree-inl.h:649
gtsam::DecisionTree::operator==
bool operator==(const DecisionTree &q) const
equality
Definition: DecisionTree-inl.h:614
gtsam::DecisionTree::Leaf::Leaf
Leaf(const Y &constant)
Constructor from constant.
Definition: DecisionTree-inl.h:60
gtsam::DecisionTree::Choice::print
void print(const std::string &s) const override
print (as a tree)
Definition: DecisionTree-inl.h:239
gtsam::DecisionTree::Leaf::apply
NodePtr apply(const Unary &op) const override
apply unary operator
Definition: DecisionTree-inl.h:104
gtsam::DecisionTree::Node
---------------------— Node base class ------------------------—
Definition: DecisionTree.h:52
gtsam::DecisionTree::NodePtr
Node::Ptr NodePtr
---------------------— Node base class ------------------------—
Definition: DecisionTree.h:96
gtsam::DecisionTree::Choice::sameLeaf
bool sameLeaf(const Leaf &q) const override
Choice-Leaf equality: always false.
Definition: DecisionTree-inl.h:269
gtsam::DecisionTree::Unary
boost::function< Y(const Y &)> Unary
Handy typedefs for unary and binary function types.
Definition: DecisionTree.h:41
gtsam::DecisionTree::create
NodePtr create(It begin, It end, ValueIt beginY, ValueIt endY) const
Internal recursive function to create from keys, cardinalities, and Y values.
Definition: DecisionTree-inl.h:531
gtsam::DecisionTree::Choice::dot
void dot(std::ostream &os, bool showZero) const override
output to graphviz (as a a graph)
Definition: DecisionTree-inl.h:248
gtsam::DecisionTree::Leaf::dot
void dot(std::ostream &os, bool showZero) const override
to graphviz file
Definition: DecisionTree-inl.h:92
gtsam::DecisionTree::Leaf
Definition: DecisionTree-inl.h:52
gtsam::dot
double dot(const V1 &a, const V2 &b)
Dot product.
Definition: Vector.h:194
gtsam::DecisionTree::Leaf::sameLeaf
bool sameLeaf(const Leaf &q) const override
Leaf-Leaf equality.
Definition: DecisionTree-inl.h:69