26#include <boost/serialization/nvp.hpp>
27#include <boost/shared_ptr.hpp>
60 template<
typename L,
typename Y>
69 using LabelFormatter = std::function<std::string(L)>;
70 using ValueFormatter = std::function<std::string(Y)>;
71 using CompareFunc = std::function<bool(
const Y&,
const Y&)>;
74 using Unary = std::function<Y(
const Y&)>;
75 using UnaryAssignment = std::function<Y(
const Assignment<L>&,
const Y&)>;
76 using Binary = std::function<Y(
const Y&,
const Y&)>;
87 using Ptr = boost::shared_ptr<const Node>;
96 std::cout << ++nrNodes <<
" constructed " << id() << std::endl;
103#ifdef DT_DEBUG_MEMORY
104 std::cout << --nrNodes <<
" destructed " << id() << std::endl;
110 const void* id()
const {
return this; }
113 virtual void print(
const std::string& s,
114 const LabelFormatter& labelFormatter,
115 const ValueFormatter& valueFormatter)
const = 0;
116 virtual void dot(std::ostream& os,
const LabelFormatter& labelFormatter,
117 const ValueFormatter& valueFormatter,
118 bool showZero)
const = 0;
119 virtual bool sameLeaf(
const Leaf& q)
const = 0;
120 virtual bool sameLeaf(
const Node& q)
const = 0;
121 virtual bool equals(
const Node& other,
const CompareFunc& compare =
123 virtual const Y& operator()(
const Assignment<L>& x)
const = 0;
124 virtual Ptr apply(
const Unary& op)
const = 0;
125 virtual Ptr apply(
const UnaryAssignment& op,
127 virtual Ptr apply_f_op_g(
const Node&,
const Binary&)
const = 0;
128 virtual Ptr apply_g_op_fL(
const Leaf&,
const Binary&)
const = 0;
129 virtual Ptr apply_g_op_fC(
const Choice&,
const Binary&)
const = 0;
130 virtual Ptr choose(
const L& label,
size_t index)
const = 0;
131 virtual bool isLeaf()
const = 0;
136 template <
class ARCHIVE>
137 void serialize(ARCHIVE& ar,
const unsigned int ) {}
153 template<
typename It,
typename ValueIt>
154 NodePtr create(It begin, It end, ValueIt beginY, ValueIt endY)
const;
166 template <
typename M,
typename X>
168 std::function<L(
const M&)> L_of_M,
169 std::function<Y(
const X&)> Y_of_X)
const;
194 DecisionTree(
const std::vector<LabelC>& labelCs,
const std::vector<Y>& ys);
197 DecisionTree(
const std::vector<LabelC>& labelCs,
const std::string& table);
200 template<
typename Iterator>
201 DecisionTree(Iterator begin, Iterator end,
const L& label);
214 template <
typename X,
typename Func>
227 template <
typename M,
typename X,
typename Func>
242 void print(
const std::string& s,
const LabelFormatter& labelFormatter,
243 const ValueFormatter& valueFormatter)
const;
279 template <
typename Func>
280 void visit(Func f)
const;
296 template <
typename Func>
313 template <
typename Func>
334 template <
typename Func,
typename X>
335 X
fold(Func f, X x0)
const;
338 std::set<L>
labels()
const;
364 DecisionTree combine(
const L& label,
size_t cardinality,
365 const Binary& op)
const;
369 return combine(labelC.first, labelC.second, op);
373 void dot(std::ostream& os,
const LabelFormatter& labelFormatter,
374 const ValueFormatter& valueFormatter,
bool showZero =
true)
const;
377 void dot(
const std::string& name,
const LabelFormatter& labelFormatter,
378 const ValueFormatter& valueFormatter,
bool showZero =
true)
const;
381 std::string
dot(
const LabelFormatter& labelFormatter,
382 const ValueFormatter& valueFormatter,
383 bool showZero =
true)
const;
392 template<
typename Iterator>
NodePtr
393 compose(Iterator begin, Iterator end,
const L& label)
const;
400 template <
class ARCHIVE>
401 void serialize(ARCHIVE& ar,
const unsigned int ) {
402 ar& BOOST_SERIALIZATION_NVP(
root_);
406 template <
class L,
class Y>
412 template<
typename L,
typename Y>
419 template<
typename L,
typename Y>
421 const typename DecisionTree<L, Y>::UnaryAssignment& op) {
426 template<
typename L,
typename Y>
429 const typename DecisionTree<L, Y>::Binary& op) {
430 return f.
apply(g, op);
439 template <
typename L,
typename T1,
typename T2>
442 return std::make_pair(
445 [](std::pair<T1, T2> i) {
return i.second; }));
Typedefs for easier changing of types.
Concept check for values that can be used in unit tests.
An assignment from labels to a discrete value index (size_t)
Global functions in a separate testing namespace.
Definition chartTesting.h:28
std::pair< DecisionTree< L, T1 >, DecisionTree< L, T2 > > unzip(const DecisionTree< L, std::pair< T1, T2 > > &input)
unzip a DecisionTree with std::pair values.
Definition DecisionTree.h:440
DecisionTree< L, Y > apply(const DecisionTree< L, Y > &f, const typename DecisionTree< L, Y >::Unary &op)
free versions of apply
Definition DecisionTree.h:413
A manifold defines a space in which there is a notion of a linear tangent space that can be centered ...
Definition concepts.h:30
Template to create a binary predicate.
Definition Testable.h:111
A helper that implements the traits interface for GTSAM types.
Definition Testable.h:151
An assignment from labels to value index (size_t).
Definition Assignment.h:37
Definition DecisionTree-inl.h:52
Definition DecisionTree-inl.h:172
a decision tree is a function from assignments to values.
Definition DecisionTree.h:61
DecisionTree apply(const Unary &op) const
apply Unary operation "op" to f
Definition DecisionTree-inl.h:889
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:358
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) const
Convert from a DecisionTree<M, X> to DecisionTree<L, Y>.
Definition DecisionTree-inl.h:671
DecisionTree combine(const LabelC &labelC, const Binary &op) const
combine with LabelC for convenience
Definition DecisionTree.h:368
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:630
virtual ~DecisionTree()=default
Make virtual.
static bool DefaultCompare(const Y &a, const Y &b)
Default method for comparison of two objects of type Y.
Definition DecisionTree.h:64
typename Node::Ptr NodePtr
---------------------— Node base class ------------------------—
Definition DecisionTree.h:143
std::set< L > labels() const
Retrieve all unique labels as a set.
Definition DecisionTree-inl.h:853
bool empty() const
Check if tree is empty.
Definition DecisionTree.h:257
void visit(Func f) const
Visit all leaves in depth-first fashion.
Definition DecisionTree-inl.h:736
void visitLeaf(Func f) const
Visit all leaves in depth-first fashion.
Definition DecisionTree-inl.h:773
std::function< Y(const Y &)> Unary
Handy typedefs for unary and binary function types.
Definition DecisionTree.h:74
X fold(Func f, X x0) const
Fold a binary function over the tree, returning accumulator.
Definition DecisionTree-inl.h:833
NodePtr root_
A DecisionTree just contains the root. TODO(dellaert): make protected.
Definition DecisionTree.h:146
void print(const std::string &s, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter) const
GTSAM-style print.
Definition DecisionTree-inl.h:872
DecisionTree combine(const L &label, size_t cardinality, const Binary &op) const
combine subtrees on key with binary operation "op"
Definition DecisionTree-inl.h:937
void visitWith(Func f) const
Visit all leaves in depth-first fashion.
Definition DecisionTree-inl.h:816
const Y & operator()(const Assignment< L > &x) const
evaluate
Definition DecisionTree-inl.h:884
void dot(std::ostream &os, const LabelFormatter &labelFormatter, const ValueFormatter &valueFormatter, bool showZero=true) const
output to graphviz format, stream version
Definition DecisionTree-inl.h:949
friend class boost::serialization::access
Serialization function.
Definition DecisionTree.h:399
bool operator==(const DecisionTree &q) const
equality
Definition DecisionTree-inl.h:879
std::pair< L, size_t > LabelC
A label annotated with cardinality.
Definition DecisionTree.h:79
size_t nrLeaves() const
Return the number of leaves in the tree.
Definition DecisionTree-inl.h:823
DecisionTree()
Default constructor (for serialization)
Definition DecisionTree-inl.h:462
---------------------— Node base class ------------------------—
Definition DecisionTree.h:86
friend class boost::serialization::access
Serialization function.
Definition DecisionTree.h:135