Skip to content

Commit

Permalink
Merge pull request #1002 from borglab/feature/decision_tree_2
Browse files Browse the repository at this point in the history
  • Loading branch information
@dellaert
dellaert authored Jan 3, 2022
2 parents 6364254 + 022b719 commit 8a28ac2
Show file tree
Hide file tree
Showing 4 changed files with 89 additions and 48 deletions.
47 changes: 29 additions & 18 deletions gtsam/discrete/AlgebraicDecisionTree.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -29,7 +29,12 @@ namespace gtsam {
*/
template<typename L>
class GTSAM_EXPORT AlgebraicDecisionTree: public DecisionTree<L, double> {
/// Default method used by `formatter` when printing.
/**
* @brief Default method used by `labelFormatter` or `valueFormatter` when printing.
*
* @param x The value passed to format.
* @return std::string
*/
static std::string DefaultFormatter(const L& x) {
std::stringstream ss;
ss << x;
Expand All @@ -38,7 +43,7 @@ namespace gtsam {

public:

typedef DecisionTree<L, double> Super;
using Base = DecisionTree<L, double>;

/** The Real ring with addition and multiplication */
struct Ring {
Expand Down Expand Up @@ -66,55 +71,61 @@ namespace gtsam {
};

AlgebraicDecisionTree() :
Super(1.0) {
Base(1.0) {
}

AlgebraicDecisionTree(const Super& add) :
Super(add) {
AlgebraicDecisionTree(const Base& add) :
Base(add) {
}

/** Create a new leaf function splitting on a variable */
AlgebraicDecisionTree(const L& label, double y1, double y2) :
Super(label, y1, y2) {
Base(label, y1, y2) {
}

/** Create a new leaf function splitting on a variable */
AlgebraicDecisionTree(const typename Super::LabelC& labelC, double y1, double y2) :
Super(labelC, y1, y2) {
AlgebraicDecisionTree(const typename Base::LabelC& labelC, double y1, double y2) :
Base(labelC, y1, y2) {
}

/** Create from keys and vector table */
AlgebraicDecisionTree //
(const std::vector<typename Super::LabelC>& labelCs, const std::vector<double>& ys) {
this->root_ = Super::create(labelCs.begin(), labelCs.end(), ys.begin(),
(const std::vector<typename Base::LabelC>& labelCs, const std::vector<double>& ys) {
this->root_ = Base::create(labelCs.begin(), labelCs.end(), ys.begin(),
ys.end());
}

/** Create from keys and string table */
AlgebraicDecisionTree //
(const std::vector<typename Super::LabelC>& labelCs, const std::string& table) {
(const std::vector<typename Base::LabelC>& labelCs, const std::string& table) {
// Convert string to doubles
std::vector<double> ys;
std::istringstream iss(table);
std::copy(std::istream_iterator<double>(iss),
std::istream_iterator<double>(), std::back_inserter(ys));

// now call recursive Create
this->root_ = Super::create(labelCs.begin(), labelCs.end(), ys.begin(),
this->root_ = Base::create(labelCs.begin(), labelCs.end(), ys.begin(),
ys.end());
}

/** Create a new function splitting on a variable */
template<typename Iterator>
AlgebraicDecisionTree(Iterator begin, Iterator end, const L& label) :
Super(nullptr) {
Base(nullptr) {
this->root_ = compose(begin, end, label);
}

/** Convert */
/**
* Convert labels from type M to type L.
*
* @param other: The AlgebraicDecisionTree with label type M to convert.
* @param map: Map from label type M to label type L.
*/
template<typename M>
AlgebraicDecisionTree(const AlgebraicDecisionTree<M>& other,
const std::map<M, L>& map) {
// Functor for label conversion so we can use `convertFrom`.
std::function<L(const M&)> L_of_M = [&map](const M& label) -> L {
return map.at(label);
};
Expand Down Expand Up @@ -143,18 +154,18 @@ namespace gtsam {
}

/** sum out variable */
AlgebraicDecisionTree sum(const typename Super::LabelC& labelC) const {
AlgebraicDecisionTree sum(const typename Base::LabelC& labelC) const {
return this->combine(labelC, &Ring::add);
}

/// print method customized to node type `double`.
void print(const std::string& s,
const typename Super::LabelFormatter& labelFormatter =
const typename Base::LabelFormatter& labelFormatter =
&DefaultFormatter) const {
auto valueFormatter = [](const double& v) {
return (boost::format("%4.2g") % v).str();
};
Super::print(s, labelFormatter, valueFormatter);
Base::print(s, labelFormatter, valueFormatter);
}

/// Equality method customized to node type `double`.
Expand All @@ -163,7 +174,7 @@ namespace gtsam {
auto compare = [tol](double a, double b) {
return std::abs(a - b) < tol;
};
return Super::equals(other, compare);
return Base::equals(other, compare);
}
};
// AlgebraicDecisionTree
Expand Down
23 changes: 15 additions & 8 deletions gtsam/discrete/DecisionTree-inl.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -82,13 +82,19 @@ namespace gtsam {
return compare(this->constant_, other->constant_);
}

/** print */
/**
* @brief Print method.
*
* @param s Prefix string.
* @param labelFormatter Functor to format the node label.
* @param valueFormatter Functor to format the node value.
*/
void print(const std::string& s, const LabelFormatter& labelFormatter,
const ValueFormatter& valueFormatter) const override {
std::cout << s << " Leaf " << valueFormatter(constant_) << std::endl;
}

/** to graphviz file */
/** Write graphviz format to stream `os`. */
void dot(std::ostream& os, const LabelFormatter& labelFormatter,
const ValueFormatter& valueFormatter,
bool showZero) const override {
Expand Down Expand Up @@ -154,7 +160,7 @@ namespace gtsam {
/** incremental allSame */
size_t allSame_;

typedef boost::shared_ptr<const Choice> ChoicePtr;
using ChoicePtr = boost::shared_ptr<const Choice>;

public:

Expand Down Expand Up @@ -462,6 +468,7 @@ namespace gtsam {
template <typename X>
DecisionTree<L, Y>::DecisionTree(const DecisionTree<L, X>& other,
std::function<Y(const X&)> Y_of_X) {
// Define functor for identity mapping of node label.
auto L_of_L = [](const L& label) { return label; };
root_ = convertFrom<L, X>(Y_of_X, L_of_L);
}
Expand Down Expand Up @@ -594,11 +601,11 @@ namespace gtsam {
const typename DecisionTree<M, X>::NodePtr& f,
std::function<L(const M&)> L_of_M,
std::function<Y(const X&)> Y_of_X) const {
typedef DecisionTree<M, X> MX;
typedef typename MX::Leaf MXLeaf;
typedef typename MX::Choice MXChoice;
typedef typename MX::NodePtr MXNodePtr;
typedef DecisionTree<L, Y> LY;
using MX = DecisionTree<M, X>;
using MXLeaf = typename MX::Leaf;
using MXChoice = typename MX::Choice;
using MXNodePtr = typename MX::NodePtr;
using LY = DecisionTree<L, Y>;

// ugliness below because apparently we can't have templated virtual functions
// If leaf, apply unary conversion "op" and create a unique leaf
Expand Down
56 changes: 45 additions & 11 deletions gtsam/discrete/DecisionTree.h
View file
Original file line number Diff line number Diff line change
Expand Up @@ -39,6 +39,7 @@ namespace gtsam {
template<typename L, typename Y>
class GTSAM_EXPORT DecisionTree {

protected:
/// Default method for comparison of two objects of type Y.
static bool DefaultCompare(const Y& a, const Y& b) {
return a == b;
Expand All @@ -51,11 +52,11 @@ namespace gtsam {
using CompareFunc = std::function<bool(const Y&, const Y&)>;

/** Handy typedefs for unary and binary function types */
typedef std::function<Y(const Y&)> Unary;
typedef std::function<Y(const Y&, const Y&)> Binary;
using Unary = std::function<Y(const Y&)>;
using Binary = std::function<Y(const Y&, const Y&)>;

/** A label annotated with cardinality */
typedef std::pair<L,size_t> LabelC;
using LabelC = std::pair<L,size_t>;

/** DTs consist of Leaf and Choice nodes, both subclasses of Node */
class Leaf;
Expand All @@ -64,7 +65,7 @@ namespace gtsam {
/** ------------------------ Node base class --------------------------- */
class Node {
public:
typedef boost::shared_ptr<const Node> Ptr;
using Ptr = boost::shared_ptr<const Node>;

#ifdef DT_DEBUG_MEMORY
static int nrNodes;
Expand Down Expand Up @@ -111,9 +112,9 @@ namespace gtsam {
public:

/** A function is a shared pointer to the root of a DT */
typedef typename Node::Ptr NodePtr;
using NodePtr = typename Node::Ptr;

/// a DecisionTree just contains the root. TODO(dellaert): make protected.
/// A DecisionTree just contains the root. TODO(dellaert): make protected.
NodePtr root_;

protected:
Expand All @@ -122,7 +123,16 @@ namespace gtsam {
template<typename It, typename ValueIt>
NodePtr create(It begin, It end, ValueIt beginY, ValueIt endY) const;

/// Convert from a DecisionTree<M, X>.
/**
* @brief Convert from a DecisionTree<M, X> to DecisionTree<L, Y>.
*
* @tparam M The previous label type.
* @tparam X The previous node type.
* @param f The node pointer to the root of the previous DecisionTree.
* @param L_of_M Functor to convert from label type M to type L.
* @param Y_of_X Functor to convert from node type X to type Y.
* @return NodePtr
*/
template <typename M, typename X>
NodePtr convertFrom(const typename DecisionTree<M, X>::NodePtr& f,
std::function<L(const M&)> L_of_M,
Expand Down Expand Up @@ -159,12 +169,27 @@ namespace gtsam {
DecisionTree(const L& label, //
const DecisionTree& f0, const DecisionTree& f1);

/** Convert from a different type. */
/**
* @brief Convert from a different node type.
*
* @tparam X The previous node type.
* @param other The DecisionTree to convert from.
* @param Y_of_X Functor to convert from node type X to type Y.
*/
template <typename X>
DecisionTree(const DecisionTree<L, X>& other,
std::function<Y(const X&)> Y_of_X);

/** Convert from a different type, also transate labels via map. */
/**
* @brief Convert from a different node type X to node type Y, also transate
* labels via map from type M to L.
*
* @tparam M Previous label type.
* @tparam X Previous node type.
* @param other The decision tree to convert.
* @param L_of_M Map from label type M to type L.
* @param Y_of_X Functor to convert from type X to type Y.
*/
template <typename M, typename X>
DecisionTree(const DecisionTree<M, X>& other, const std::map<M, L>& L_of_M,
std::function<Y(const X&)> Y_of_X);
Expand All @@ -173,7 +198,13 @@ namespace gtsam {
/// @name Testable
/// @{

/** GTSAM-style print */
/**
* @brief GTSAM-style print
*
* @param s Prefix string.
* @param labelFormatter Functor to format the node label.
* @param valueFormatter Functor to format the node value.
*/
void print(const std::string& s, const LabelFormatter& labelFormatter,
const ValueFormatter& valueFormatter) const;

Expand All @@ -189,7 +220,7 @@ namespace gtsam {
virtual ~DecisionTree() {
}

/** empty tree? */
/// Check if tree is empty.
bool empty() const { return !root_; }

/** equality */
Expand Down Expand Up @@ -248,18 +279,21 @@ namespace gtsam {

/** free versions of apply */

/// Apply unary operator `op` to DecisionTree `f`.
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);
}

/// Apply unary operator `op` to DecisionTree `f` but with node type.
template<typename L, typename Y, typename X>
DecisionTree<L, Y> apply(const DecisionTree<L, Y>& f,
const std::function<Y(const X&)>& op) {
return f.apply(op);
}

/// Apply binary operator `op` to DecisionTree `f`.
template<typename L, typename Y>
DecisionTree<L, Y> apply(const DecisionTree<L, Y>& f,
const DecisionTree<L, Y>& g,
Expand Down
11 changes: 0 additions & 11 deletions gtsam/discrete/tests/testDecisionTree.cpp
View file
Original file line number Diff line number Diff line change
Expand Up @@ -45,15 +45,6 @@ struct Crazy {
double b;
};

// bool equals(const Crazy& other, double tol = 1e-12) const {
// return a == other.a && std::abs(b - other.b) < tol;
// }

// bool operator==(const Crazy& other) const {
// return this->equals(other);
// }
// };

struct CrazyDecisionTree : public DecisionTree<string, Crazy> {
/// print to stdout
void print(const std::string& s = "") const {
Expand Down Expand Up @@ -261,8 +252,6 @@ TEST(DT, conversion)
return y != 0;
};
BDT f2(f1, ordering, bool_of_int);
// f1.print("f1");
// f2.print("f2");

// create a value
Assignment<Label> x00, x01, x10, x11;
Expand Down

0 comments on commit 8a28ac2

Please sign in to comment.