gtsam  4.1.0
gtsam
ClusterTree.h
1 
10 #pragma once
11 
12 #include <gtsam/base/Testable.h>
13 #include <gtsam/base/FastVector.h>
15 
16 namespace gtsam {
17 
24 template <class GRAPH>
25 class ClusterTree {
26  public:
27  typedef GRAPH FactorGraphType;
29  typedef boost::shared_ptr<This> shared_ptr;
30 
31  typedef typename GRAPH::FactorType FactorType;
32  typedef boost::shared_ptr<FactorType> sharedFactor;
33 
35  // TODO(frank): re-factor JunctionTree so we can make members private
36  struct Cluster {
37  typedef FastVector<boost::shared_ptr<Cluster> > Children;
38  Children children;
39 
40  typedef Ordering Keys;
42 
44 
45  int problemSize_;
46 
47  Cluster() : problemSize_(0) {}
48 
49  virtual ~Cluster() {}
50 
51  const Cluster& operator[](size_t i) const {
52  return *(children[i]);
53  }
54 
56  template <class CONTAINER>
57  Cluster(Key key, const CONTAINER& factorsToAdd)
58  : problemSize_(0) {
59  addFactors(key, factorsToAdd);
60  }
61 
63  template <class CONTAINER>
64  void addFactors(Key key, const CONTAINER& factorsToAdd) {
65  orderedFrontalKeys.push_back(key);
66  factors.push_back(factorsToAdd);
67  problemSize_ += factors.size();
68  }
69 
71  void addChild(const boost::shared_ptr<Cluster>& cluster) {
72  children.push_back(cluster);
73  problemSize_ = std::max(problemSize_, cluster->problemSize_);
74  }
75 
76  size_t nrChildren() const {
77  return children.size();
78  }
79 
80  size_t nrFactors() const {
81  return factors.size();
82  }
83 
84  size_t nrFrontals() const {
85  return orderedFrontalKeys.size();
86  }
87 
88  int problemSize() const {
89  return problemSize_;
90  }
91 
93  virtual void print(const std::string& s = "",
94  const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
95 
97  std::vector<size_t> nrFrontalsOfChildren() const;
98 
100  void merge(const boost::shared_ptr<Cluster>& cluster);
101 
103  void mergeChildren(const std::vector<bool>& merge);
104  };
105 
106  typedef boost::shared_ptr<Cluster> sharedCluster;
107 
108  // Define Node=Cluster for compatibility with tree traversal functions
109  typedef Cluster Node;
110  typedef sharedCluster sharedNode;
111 
114 
115  protected:
116  FastVector<sharedNode> roots_;
117 
120 
123  ClusterTree(const This& other) {
124  *this = other;
125  }
126 
128 
129  public:
130 
133 
136 
138  void print(const std::string& s = "",
139  const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
140 
142 
145 
146  void addRoot(const boost::shared_ptr<Cluster>& cluster) {
147  roots_.push_back(cluster);
148  }
149 
150  void addChildrenAsRoots(const boost::shared_ptr<Cluster>& cluster) {
151  for (auto child : cluster->children)
152  this->addRoot(child);
153  }
154 
155  size_t nrRoots() const {
156  return roots_.size();
157  }
158 
160  const FastVector<sharedNode>& roots() const {
161  return roots_;
162  }
163 
164  const Cluster& operator[](size_t i) const {
165  return *(roots_[i]);
166  }
167 
169 
170  protected:
172 
175  This& operator=(const This& other);
176 
178 };
179 
183 template <class BAYESTREE, class GRAPH>
184 class EliminatableClusterTree : public ClusterTree<GRAPH> {
185  public:
186  typedef BAYESTREE BayesTreeType;
187  typedef GRAPH FactorGraphType;
189  typedef boost::shared_ptr<This> shared_ptr;
190 
191  typedef typename BAYESTREE::ConditionalType ConditionalType;
192  typedef boost::shared_ptr<ConditionalType>
194 
195  typedef typename GRAPH::Eliminate Eliminate;
196  typedef typename GRAPH::FactorType FactorType;
197  typedef boost::shared_ptr<FactorType> sharedFactor;
198 
199  protected:
200  FastVector<sharedFactor> remainingFactors_;
201 
204 
207  EliminatableClusterTree(const This& other) : ClusterTree<GRAPH>(other) {
208  *this = other;
209  }
210 
212 
213  public:
216 
222  std::pair<boost::shared_ptr<BayesTreeType>, boost::shared_ptr<FactorGraphType> > eliminate(
223  const Eliminate& function) const;
224 
226 
229 
231  const FastVector<sharedFactor>& remainingFactors() const {
232  return remainingFactors_;
233  }
234 
236 
237  protected:
239 
242  This& operator=(const This& other);
243 
246 
248 };
249 }
250 
251 #include <gtsam/inference/ClusterTree-inst.h>
gtsam::ClusterTree::Cluster::print
virtual void print(const std::string &s="", const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
print this node
Definition: ClusterTree-inst.h:22
gtsam::ClusterTree::Cluster::merge
void merge(const boost::shared_ptr< Cluster > &cluster)
Merge in given cluster.
Definition: ClusterTree-inst.h:40
FastVector.h
A thin wrapper around std::vector that uses a custom allocator.
Testable.h
Concept check for values that can be used in unit tests.
gtsam::EliminatableClusterTree::operator=
This & operator=(const This &other)
Assignment operator - makes a deep copy of the tree structure, but only pointers to factors are copie...
Definition: ClusterTree-inst.h:207
gtsam::Ordering
Definition: Ordering.h:34
gtsam::ClusterTree::This
ClusterTree< GRAPH > This
This class.
Definition: ClusterTree.h:28
gtsam::ClusterTree::operator=
This & operator=(const This &other)
Assignment operator - makes a deep copy of the tree structure, but only pointers to factors are copie...
Definition: ClusterTree-inst.h:100
gtsam::ClusterTree
A cluster-tree is associated with a factor graph and is defined as in Koller-Friedman: each node k re...
Definition: ClusterTree.h:25
gtsam::EliminatableClusterTree::Eliminate
GRAPH::Eliminate Eliminate
Typedef for an eliminate subroutine.
Definition: ClusterTree.h:195
gtsam::ClusterTree::sharedCluster
boost::shared_ptr< Cluster > sharedCluster
Shared pointer to Cluster.
Definition: ClusterTree.h:106
gtsam::ClusterTree::Cluster::orderedFrontalKeys
Keys orderedFrontalKeys
Frontal keys of this node.
Definition: ClusterTree.h:41
gtsam::Key
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:61
gtsam::ClusterTree::roots
const FastVector< sharedNode > & roots() const
Return the set of roots (one for a tree, multiple for a forest)
Definition: ClusterTree.h:160
gtsam::EliminatableClusterTree
A cluster-tree that eliminates to a Bayes tree.
Definition: ClusterTree.h:184
gtsam::EliminatableClusterTree::ConditionalType
BAYESTREE::ConditionalType ConditionalType
The type of conditionals.
Definition: ClusterTree.h:191
gtsam::EliminatableClusterTree::sharedConditional
boost::shared_ptr< ConditionalType > sharedConditional
Shared pointer to a conditional.
Definition: ClusterTree.h:193
gtsam::ClusterTree::ClusterTree
ClusterTree(const This &other)
Copy constructor - makes a deep copy of the tree structure, but only pointers to factors are copied,...
Definition: ClusterTree.h:123
gtsam::EliminatableClusterTree::sharedFactor
boost::shared_ptr< FactorType > sharedFactor
Shared pointer to a factor.
Definition: ClusterTree.h:197
gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
gtsam::ClusterTree::ClusterTree
ClusterTree()
Default constructor.
Definition: ClusterTree.h:132
gtsam::ClusterTree::print
void print(const std::string &s="", const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
Print the cluster tree.
Definition: ClusterTree-inst.h:94
gtsam::EliminatableClusterTree::shared_ptr
boost::shared_ptr< This > shared_ptr
Shared pointer to this class.
Definition: ClusterTree.h:189
gtsam::EliminatableClusterTree::This
EliminatableClusterTree< BAYESTREE, GRAPH > This
This class.
Definition: ClusterTree.h:188
gtsam::EliminatableClusterTree::FactorType
GRAPH::FactorType FactorType
The type of factors.
Definition: ClusterTree.h:196
gtsam::ClusterTree::Cluster::nrFrontalsOfChildren
std::vector< size_t > nrFrontalsOfChildren() const
Return a vector with nrFrontal keys for each child.
Definition: ClusterTree-inst.h:30
gtsam::ClusterTree::Cluster::addFactors
void addFactors(Key key, const CONTAINER &factorsToAdd)
Add factors associated with a single key.
Definition: ClusterTree.h:64
gtsam::ClusterTree::Cluster::addChild
void addChild(const boost::shared_ptr< Cluster > &cluster)
Add a child cluster.
Definition: ClusterTree.h:71
gtsam::EliminatableClusterTree::remainingFactors
const FastVector< sharedFactor > & remainingFactors() const
Return the remaining factors that are not pulled into elimination.
Definition: ClusterTree.h:231
gtsam::EliminatableClusterTree::EliminatableClusterTree
EliminatableClusterTree(const This &other)
Copy constructor - makes a deep copy of the tree structure, but only pointers to factors are copied,...
Definition: ClusterTree.h:207
gtsam::EliminatableClusterTree::eliminate
std::pair< boost::shared_ptr< BayesTreeType >, boost::shared_ptr< FactorGraphType > > eliminate(const Eliminate &function) const
Eliminate the factors to a Bayes tree and remaining factor graph.
Definition: ClusterTree-inst.h:221
gtsam::ClusterTree::Cluster::Cluster
Cluster(Key key, const CONTAINER &factorsToAdd)
Construct from factors associated with a single key.
Definition: ClusterTree.h:57
gtsam::EliminatableClusterTree::EliminatableClusterTree
EliminatableClusterTree()
Default constructor to be used in derived classes.
Definition: ClusterTree.h:245
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::ClusterTree::FactorGraphType
GRAPH FactorGraphType
The factor graph type.
Definition: ClusterTree.h:27
gtsam::ClusterTree::Cluster::mergeChildren
void mergeChildren(const std::vector< bool > &merge)
Merge all children for which bit is set into this node.
Definition: ClusterTree-inst.h:52
gtsam::ClusterTree::Cluster::children
Children children
sub-trees
Definition: ClusterTree.h:38
gtsam::ClusterTree::Cluster
A Cluster is just a collection of factors.
Definition: ClusterTree.h:36
Ordering.h
Variable ordering for the elimination algorithm.
gtsam::ClusterTree::Cluster::factors
FactorGraphType factors
Factors associated with this node.
Definition: ClusterTree.h:43
gtsam::EliminatableClusterTree::FactorGraphType
GRAPH FactorGraphType
The factor graph type.
Definition: ClusterTree.h:187
gtsam::EliminatableClusterTree::BayesTreeType
BAYESTREE BayesTreeType
The BayesTree type produced by elimination.
Definition: ClusterTree.h:186
gtsam::ClusterTree::GTSAM_CONCEPT_TESTABLE_TYPE
GTSAM_CONCEPT_TESTABLE_TYPE(FactorType)
concept check
gtsam::ClusterTree::shared_ptr
boost::shared_ptr< This > shared_ptr
Shared pointer to this class.
Definition: ClusterTree.h:29
gtsam::ClusterTree::sharedFactor
boost::shared_ptr< FactorType > sharedFactor
Shared pointer to a factor.
Definition: ClusterTree.h:32
gtsam::ClusterTree::FactorType
GRAPH::FactorType FactorType
The type of factors.
Definition: ClusterTree.h:31