DecisionTree.h

Go to the documentation of this file.

/* ----------------------------------------------------------------------------
 
 * GTSAM Copyright 2010, Georgia Tech Research Corporation,
 * Atlanta, Georgia 30332-0415
 * All Rights Reserved
 * Authors: Frank Dellaert, et al. (see THANKS for the full author list)
 
 * See LICENSE for the license information
 
 * -------------------------------------------------------------------------- */
 
#pragma once
 
#include <gtsam/base/Testable.h>
#include <gtsam/base/types.h>
#include <gtsam/discrete/Assignment.h>
 
#ifdef GTSAM_ENABLE_BOOST_SERIALIZATION
#include <boost/serialization/nvp.hpp>
#endif
#include <memory>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
 
namespace gtsam {
 
  template<typename L, typename Y>
  class DecisionTree {
   protected:
    static bool DefaultCompare(const Y& a, const Y& b) {
      return a == b;
    }
 
   public:
    using LabelFormatter = std::function<std::string(L)>;
    using ValueFormatter = std::function<std::string(Y)>;
    using CompareFunc = std::function<bool(const Y&, const Y&)>;
 
    using Unary = std::function<Y(const Y&)>;
    using UnaryAssignment = std::function<Y(const Assignment<L>&, const Y&)>;
    using Binary = std::function<Y(const Y&, const Y&)>;
 
    using LabelC = std::pair<L, size_t>;
 
    struct Leaf;
    struct Choice;
 
    struct Node {
      using Ptr = std::shared_ptr<Node>;
 
#ifdef DT_DEBUG_MEMORY
      static int nrNodes;
#endif
 
      // Constructor
      Node() {
#ifdef DT_DEBUG_MEMORY
        std::cout << ++nrNodes << " constructed " << id() << std::endl;
        std::cout.flush();
#endif
      }
 
      // Destructor
      virtual ~Node() {
#ifdef DT_DEBUG_MEMORY
        std::cout << --nrNodes << " destructed " << id() << std::endl;
        std::cout.flush();
#endif
      }
 
      // Unique ID for dot files
      const void* id() const { return this; }
 
      // everything else is virtual, no documentation here as internal
      virtual void print(const std::string& s,
                         const LabelFormatter& labelFormatter,
                         const ValueFormatter& valueFormatter) const = 0;
      virtual void dot(std::ostream& os, const LabelFormatter& labelFormatter,
                       const ValueFormatter& valueFormatter,
                       bool showZero) const = 0;
      virtual bool sameLeaf(const Leaf& q) const = 0;
      virtual bool sameLeaf(const Node& q) const = 0;
      virtual bool equals(const Node& other, const CompareFunc& compare =
                                                 &DefaultCompare) const = 0;
      virtual const Y& operator()(const Assignment<L>& x) const = 0;
      virtual Ptr apply(const Unary& op) const = 0;
      virtual Ptr apply(const UnaryAssignment& op,
                        const Assignment<L>& assignment) const = 0;
      virtual Ptr apply_f_op_g(const Node&, const Binary&) const = 0;
      virtual Ptr apply_g_op_fL(const Leaf&, const Binary&) const = 0;
      virtual Ptr apply_g_op_fC(const Choice&, const Binary&) const = 0;
      virtual Ptr choose(const L& label, size_t index) const = 0;
      virtual bool isLeaf() const = 0;
 
     private:
#ifdef GTSAM_ENABLE_BOOST_SERIALIZATION
 
      friend class boost::serialization::access;
      template <class ARCHIVE>
      void serialize(ARCHIVE& ar, const unsigned int /*version*/) {}
#endif
    };
   public:
    using NodePtr = typename Node::Ptr;
 
    NodePtr root_;
 
   protected:
    template <typename It, typename ValueIt>
    static NodePtr build(It begin, It end, ValueIt beginY, ValueIt endY);
 
    template <typename It, typename ValueIt>
    static NodePtr create(It begin, It end, ValueIt beginY, ValueIt endY);
 
    template <typename X>
    static NodePtr convertFrom(const typename DecisionTree<L, X>::NodePtr& f,
                               std::function<Y(const X&)> Y_of_X);
 
    template <typename M, typename X>
    static NodePtr convertFrom(const typename DecisionTree<M, X>::NodePtr& f,
                               std::function<L(const M&)> L_of_M,
                               std::function<Y(const X&)> Y_of_X);
 
   public:
 
    DecisionTree();
 
    explicit DecisionTree(const Y& y);
 
    DecisionTree(const L& label, const Y& y1, const Y& y2);
 
    DecisionTree(const LabelC& label, const Y& y1, const Y& y2);
 
    DecisionTree(const std::vector<LabelC>& labelCs, const std::vector<Y>& ys);
 
    DecisionTree(const std::vector<LabelC>& labelCs, const std::string& table);
 
    template<typename Iterator>
    DecisionTree(Iterator begin, Iterator end, const L& label);
 
    DecisionTree(const L& label, const DecisionTree& f0,
                 const DecisionTree& f1);
 
    DecisionTree(const Unary& op, DecisionTree&& other) noexcept;
 
    template <typename X, typename Func>
    DecisionTree(const DecisionTree<L, X>& other, Func Y_of_X);
 
    template <typename M, typename X, typename Func>
    DecisionTree(const DecisionTree<M, X>& other, const std::map<M, L>& map,
                 Func Y_of_X);
 
 
    void print(const std::string& s, const LabelFormatter& labelFormatter,
               const ValueFormatter& valueFormatter) const;
 
    // Testable
    bool equals(const DecisionTree& other,
                const CompareFunc& compare = &DefaultCompare) const;
 
 
    virtual ~DecisionTree() = default;
 
    bool empty() const { return !root_; }
 
    bool operator==(const DecisionTree& q) const;
 
    const Y& operator()(const Assignment<L>& x) const;
 
    template <typename Func>
    void visit(Func f) const;
 
    template <typename Func>
    void visitLeaf(Func f) const;
 
    template <typename Func>
    void visitWith(Func f) const;
 
    size_t nrLeaves() const;
 
    template <typename Func, typename X>
    X fold(Func f, X x0) const;
 
    std::set<L> labels() const;
 
    DecisionTree apply(const Unary& op) const;
 
    DecisionTree apply(const UnaryAssignment& op) const;
 
    DecisionTree apply(const DecisionTree& g, const Binary& op) const;
 
    DecisionTree choose(const L& label, size_t index) const {
      NodePtr newRoot = root_->choose(label, index);
      return DecisionTree(newRoot);
    }
 
    DecisionTree combine(const L& label, size_t cardinality,
                         const Binary& op) const;
 
    DecisionTree combine(const LabelC& labelC, const Binary& op) const {
      return combine(labelC.first, labelC.second, op);
    }
 
    void dot(std::ostream& os, const LabelFormatter& labelFormatter,
             const ValueFormatter& valueFormatter, bool showZero = true) const;
 
    void dot(const std::string& name, const LabelFormatter& labelFormatter,
             const ValueFormatter& valueFormatter, bool showZero = true) const;
 
    std::string dot(const LabelFormatter& labelFormatter,
                    const ValueFormatter& valueFormatter,
                    bool showZero = true) const;
 
    template <typename A, typename B>
    std::pair<DecisionTree<L, A>, DecisionTree<L, B>> split(
        std::function<std::pair<A, B>(const Y&)> AB_of_Y) const;
 
 
    // internal use only
    explicit DecisionTree(const NodePtr& root);
 
    // internal use only
    template<typename Iterator> NodePtr
    static compose(Iterator begin, Iterator end, const L& label);
 
 
   private:
#ifdef GTSAM_ENABLE_BOOST_SERIALIZATION
 
    friend class boost::serialization::access;
    template <class ARCHIVE>
    void serialize(ARCHIVE& ar, const unsigned int /*version*/) {
      ar& BOOST_SERIALIZATION_NVP(root_);
    }
#endif
  };  // DecisionTree
 
  template <class L, class Y>
  struct traits<DecisionTree<L, Y>> : public Testable<DecisionTree<L, Y>> {};
 
  template<typename L, typename Y>
  DecisionTree<L, Y> apply(const DecisionTree<L, Y>& f,
      const typename DecisionTree<L, Y>::Unary& op) {
    return f.apply(op);
  }
 
  template<typename L, typename Y>
  DecisionTree<L, Y> apply(const DecisionTree<L, Y>& f,
      const typename DecisionTree<L, Y>::UnaryAssignment& op) {
    return f.apply(op);
  }
 
  template<typename L, typename Y>
  DecisionTree<L, Y> apply(const DecisionTree<L, Y>& f,
      const DecisionTree<L, Y>& g,
      const typename DecisionTree<L, Y>::Binary& op) {
    return f.apply(g, op);
  }
 
  template <typename L, typename T1, typename T2>
  std::pair<DecisionTree<L, T1>, DecisionTree<L, T2> > unzip(
      const DecisionTree<L, std::pair<T1, T2> >& input) {
    return {
        DecisionTree<L, T1>(input, [](std::pair<T1, T2> i) { return i.first; }),
        DecisionTree<L, T2>(input, [](std::pair<T1, T2> i) { return i.second; })
    };
  }
 
}  // namespace gtsam