gtsam  4.1.0
gtsam
EliminationTree.h
Go to the documentation of this file.
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 
18 #pragma once
19 
20 #include <utility>
21 #include <boost/shared_ptr.hpp>
22 
23 #include <gtsam/base/Testable.h>
24 #include <gtsam/base/FastVector.h>
25 
26 class EliminationTreeTester; // for unit tests, see testEliminationTree
27 
28 namespace gtsam {
29 
30  class VariableIndex;
31  class Ordering;
32 
50  template<class BAYESNET, class GRAPH>
52  {
53  protected:
55  typedef boost::shared_ptr<This> shared_ptr;
56 
57  public:
58  typedef GRAPH FactorGraphType;
59  typedef typename GRAPH::FactorType FactorType;
60  typedef typename boost::shared_ptr<FactorType> sharedFactor;
61  typedef BAYESNET BayesNetType;
63  typedef typename boost::shared_ptr<ConditionalType> sharedConditional;
64  typedef typename GRAPH::Eliminate Eliminate;
65 
66  struct Node {
67  typedef FastVector<sharedFactor> Factors;
68  typedef FastVector<boost::shared_ptr<Node> > Children;
69 
70  Key key;
71  Factors factors;
72  Children children;
73 
74  sharedFactor eliminate(const boost::shared_ptr<BayesNetType>& output,
75  const Eliminate& function, const FastVector<sharedFactor>& childrenFactors) const;
76 
77  void print(const std::string& str, const KeyFormatter& keyFormatter) const;
78  };
79 
80  typedef boost::shared_ptr<Node> sharedNode;
81 
82  protected:
85 
86  FastVector<sharedNode> roots_;
87  FastVector<sharedFactor> remainingFactors_;
88 
91 
100  EliminationTree(const FactorGraphType& factorGraph,
101  const VariableIndex& structure, const Ordering& order);
102 
108  EliminationTree(const FactorGraphType& factorGraph, const Ordering& order);
109 
112  EliminationTree(const This& other) { *this = other; }
113 
116  This& operator=(const This& other);
117 
119 
120  public:
123 
129  std::pair<boost::shared_ptr<BayesNetType>, boost::shared_ptr<FactorGraphType> >
130  eliminate(Eliminate function) const;
131 
135 
137  void print(const std::string& name = "EliminationTree: ",
138  const KeyFormatter& formatter = DefaultKeyFormatter) const;
139 
140  protected:
142  bool equals(const This& other, double tol = 1e-9) const;
143 
145 
146  public:
149 
151  const FastVector<sharedNode>& roots() const { return roots_; }
152 
154  const FastVector<sharedFactor>& remainingFactors() const { return remainingFactors_; }
155 
157  void swap(This& other);
158 
159  protected:
162 
163  private:
165  friend class ::EliminationTreeTester;
166  };
167 
168 }
gtsam::EliminationTree::FactorType
GRAPH::FactorType FactorType
The type of factors.
Definition: EliminationTree.h:59
gtsam::GaussianFactorGraph
A Linear Factor Graph is a factor graph where all factors are Gaussian, i.e.
Definition: GaussianFactorGraph.h:68
FastVector.h
A thin wrapper around std::vector that uses a custom allocator.
gtsam::EliminationTree::equals
bool equals(const This &other, double tol=1e-9) const
Test whether the tree is equal to another.
Definition: EliminationTree-inst.h:215
Testable.h
Concept check for values that can be used in unit tests.
gtsam::EliminationTree::roots
const FastVector< sharedNode > & roots() const
Return the set of roots (one for a tree, multiple for a forest)
Definition: EliminationTree.h:151
gtsam::Ordering
Definition: Ordering.h:34
gtsam::EliminationTree::sharedFactor
boost::shared_ptr< FactorType > sharedFactor
Shared pointer to a factor.
Definition: EliminationTree.h:60
gtsam::GaussianConditional
A conditional Gaussian functions as the node in a Bayes network It has a set of parents y,...
Definition: GaussianConditional.h:39
gtsam::Key
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:61
gtsam::EliminationTree::GTSAM_CONCEPT_TESTABLE_TYPE
GTSAM_CONCEPT_TESTABLE_TYPE(FactorType)
concept check
gtsam::EliminationTree::Node::key
Key key
key associated with root
Definition: EliminationTree.h:70
gtsam::EliminationTree::BayesNetType
BAYESNET BayesNetType
The BayesNet corresponding to FACTOR.
Definition: EliminationTree.h:61
gtsam::EliminationTree::operator=
This & operator=(const This &other)
Assignment operator - makes a deep copy of the tree structure, but only pointers to factors are copie...
Definition: EliminationTree-inst.h:173
gtsam::EliminationTree::Node::factors
Factors factors
factors associated with root
Definition: EliminationTree.h:71
gtsam::EliminationTree::shared_ptr
boost::shared_ptr< This > shared_ptr
Shared pointer to this class.
Definition: EliminationTree.h:55
gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
gtsam::EliminationTree::sharedConditional
boost::shared_ptr< ConditionalType > sharedConditional
Shared pointer to a conditional.
Definition: EliminationTree.h:63
gtsam::EliminationTree::sharedNode
boost::shared_ptr< Node > sharedNode
Shared pointer to Node.
Definition: EliminationTree.h:80
gtsam::EliminationTree::Node::children
Children children
sub-trees
Definition: EliminationTree.h:72
gtsam::EliminationTree
An elimination tree is a data structure used intermediately during elimination.
Definition: EliminationTree.h:52
gtsam::EliminationTree::remainingFactors
const FastVector< sharedFactor > & remainingFactors() const
Return the remaining factors that are not pulled into elimination.
Definition: EliminationTree.h:154
gtsam::EliminationTree::eliminate
std::pair< boost::shared_ptr< BayesNetType >, boost::shared_ptr< FactorGraphType > > eliminate(Eliminate function) const
Eliminate the factors to a Bayes net and remaining factor graph.
Definition: EliminationTree-inst.h:188
gtsam::EliminationTree::swap
void swap(This &other)
Swap the data of this tree with another one, this operation is very fast.
Definition: EliminationTree-inst.h:284
gtsam::EliminationTree::print
void print(const std::string &name="EliminationTree: ", const KeyFormatter &formatter=DefaultKeyFormatter) const
Print the tree to cout.
Definition: EliminationTree-inst.h:208
gtsam::KeyFormatter
boost::function< std::string(Key)> KeyFormatter
Typedef for a function to format a key, i.e. to convert it to a string.
Definition: Key.h:35
gtsam::EliminationTree::This
EliminationTree< BAYESNET, GRAPH > This
This class.
Definition: EliminationTree.h:54
gtsam::EliminationTree::EliminationTree
EliminationTree(const This &other)
Copy constructor - makes a deep copy of the tree structure, but only pointers to factors are copied,...
Definition: EliminationTree.h:112
gtsam::EliminationTree::EliminationTree
EliminationTree()
Protected default constructor.
Definition: EliminationTree.h:161
gtsam::EliminationTree::FactorGraphType
GRAPH FactorGraphType
The factor graph type.
Definition: EliminationTree.h:58
gtsam::VariableIndex
The VariableIndex class computes and stores the block column structure of a factor graph.
Definition: VariableIndex.h:43
gtsam::EliminationTree::ConditionalType
BayesNetType::ConditionalType ConditionalType
The type of conditionals.
Definition: EliminationTree.h:62
gtsam::EliminationTree::Node
Definition: EliminationTree.h:66