gtsam  4.1.0
gtsam
BayesTree.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 // \callgraph
19 
20 #pragma once
21 
22 #include <gtsam/inference/Key.h>
23 #include <gtsam/base/FastList.h>
24 #include <gtsam/base/ConcurrentMap.h>
25 #include <gtsam/base/FastVector.h>
26 
27 #include <string>
28 
29 namespace gtsam {
30 
31  // Forward declarations
32  template<class FACTOR> class FactorGraph;
33  template<class BAYESTREE, class GRAPH> class EliminatableClusterTree;
34 
35  /* ************************************************************************* */
37  struct GTSAM_EXPORT BayesTreeCliqueStats {
38  double avgConditionalSize;
39  std::size_t maxConditionalSize;
40  double avgSeparatorSize;
41  std::size_t maxSeparatorSize;
42  void print(const std::string& s = "") const ;
43  };
44 
46  struct GTSAM_EXPORT BayesTreeCliqueData {
47  FastVector<std::size_t> conditionalSizes;
48  FastVector<std::size_t> separatorSizes;
49  BayesTreeCliqueStats getStats() const;
50  };
51 
52  /* ************************************************************************* */
63  template<class CLIQUE>
64  class BayesTree
65  {
66  protected:
67  typedef BayesTree<CLIQUE> This;
68  typedef boost::shared_ptr<This> shared_ptr;
69 
70  public:
71  typedef CLIQUE Clique;
72  typedef boost::shared_ptr<Clique> sharedClique;
73  typedef Clique Node;
75  typedef typename CLIQUE::ConditionalType ConditionalType;
76  typedef boost::shared_ptr<ConditionalType> sharedConditional;
77  typedef typename CLIQUE::BayesNetType BayesNetType;
78  typedef boost::shared_ptr<BayesNetType> sharedBayesNet;
79  typedef typename CLIQUE::FactorType FactorType;
80  typedef boost::shared_ptr<FactorType> sharedFactor;
81  typedef typename CLIQUE::FactorGraphType FactorGraphType;
82  typedef boost::shared_ptr<FactorGraphType> sharedFactorGraph;
83  typedef typename FactorGraphType::Eliminate Eliminate;
84  typedef typename CLIQUE::EliminationTraitsType EliminationTraitsType;
85 
88 
91 
93  typedef FastVector<sharedClique> Roots;
94 
95  protected:
96 
99 
102 
105 
108 
110  BayesTree(const This& other);
111 
113 
115  This& operator=(const This& other);
116 
119 
121  bool equals(const This& other, double tol = 1e-9) const;
122 
123  public:
125  void print(const std::string& s = "",
126  const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
128 
131 
133  size_t size() const;
134 
136  inline bool empty() const {
137  return nodes_.empty();
138  }
139 
141  const Nodes& nodes() const { return nodes_; }
142 
144  const sharedNode operator[](Key j) const { return nodes_.at(j); }
145 
147  const Roots& roots() const { return roots_; }
148 
150  const sharedClique& clique(Key j) const {
151  typename Nodes::const_iterator c = nodes_.find(j);
152  if(c == nodes_.end())
153  throw std::out_of_range("Requested the BayesTree clique for a key that is not in the BayesTree");
154  else
155  return c->second;
156  }
157 
160 
162  size_t numCachedSeparatorMarginals() const;
163 
169  sharedConditional marginalFactor(Key j, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
170 
175  sharedFactorGraph joint(Key j1, Key j2, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
176 
181  sharedBayesNet jointBayesNet(Key j1, Key j2, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
182 
188  void saveGraph(const std::string& s, const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
189 
193 
198  template<class CONTAINER>
199  Key findParentClique(const CONTAINER& parents) const;
200 
202  void clear();
203 
205  void deleteCachedShortcuts();
206 
211  void removePath(sharedClique clique, BayesNetType* bn, Cliques* orphans);
212 
217  void removeTop(const KeyVector& keys, BayesNetType* bn, Cliques* orphans);
218 
221  Cliques removeSubtree(const sharedClique& subtree);
222 
226  void insertRoot(const sharedClique& subtree);
227 
229  void addClique(const sharedClique& clique, const sharedClique& parent_clique = sharedClique());
230 
232  void addFactorsToGraph(FactorGraph<FactorType>* graph) const;
233 
234  protected:
235 
237  void saveGraph(std::ostream &s, sharedClique clique, const KeyFormatter& keyFormatter,
238  int parentnum = 0) const;
239 
242 
245 
247  void fillNodesIndex(const sharedClique& subtree);
248 
249  // Friend JunctionTree because it directly fills roots and nodes index.
250  template<class BAYESRTEE, class GRAPH> friend class EliminatableClusterTree;
251 
252  private:
254  friend class boost::serialization::access;
255  template<class ARCHIVE>
256  void serialize(ARCHIVE & ar, const unsigned int /*version*/) {
257  ar & BOOST_SERIALIZATION_NVP(nodes_);
258  ar & BOOST_SERIALIZATION_NVP(roots_);
259  }
260 
262 
263  }; // BayesTree
264 
265  /* ************************************************************************* */
266  template<class CLIQUE>
267  class BayesTreeOrphanWrapper : public CLIQUE::ConditionalType
268  {
269  public:
270  typedef CLIQUE CliqueType;
271  typedef typename CLIQUE::ConditionalType Base;
272 
273  boost::shared_ptr<CliqueType> clique;
274 
275  BayesTreeOrphanWrapper(const boost::shared_ptr<CliqueType>& clique) :
276  clique(clique)
277  {
278  // Store parent keys in our base type factor so that eliminating those parent keys will pull
279  // this subtree into the elimination.
280  this->keys_.assign(clique->conditional()->beginParents(), clique->conditional()->endParents());
281  }
282 
283  void print(const std::string& s="", const KeyFormatter& formatter = DefaultKeyFormatter) const override {
284  clique->print(s + "stored clique", formatter);
285  }
286  };
287 
288 }
gtsam::BayesTree::clear
void clear()
Remove all nodes.
Definition: BayesTree-inst.h:391
gtsam::BayesTree::removePath
void removePath(sharedClique clique, BayesNetType *bn, Cliques *orphans)
Remove path from clique to root and return that path as factors plus a list of orphaned subtree roots...
Definition: BayesTree-inst.h:431
gtsam::BayesTree::sharedClique
boost::shared_ptr< Clique > sharedClique
Shared pointer to a clique.
Definition: BayesTree.h:72
FastVector.h
A thin wrapper around std::vector that uses a custom allocator.
gtsam::BayesTree::numCachedSeparatorMarginals
size_t numCachedSeparatorMarginals() const
Collect number of cliques with cached separator marginals.
Definition: BayesTree-inst.h:58
gtsam::BayesTree::Cliques
FastList< sharedClique > Cliques
A convenience class for a list of shared cliques.
Definition: BayesTree.h:87
gtsam::ConcurrentMap< Key, sharedClique >
gtsam::BayesTree::Node
Clique Node
Synonym for Clique (TODO: remove)
Definition: BayesTree.h:73
gtsam::BayesTree
Definition: BayesTree.h:65
gtsam::BayesTree::marginalFactor
sharedConditional marginalFactor(Key j, const Eliminate &function=EliminationTraitsType::DefaultEliminate) const
Return marginal on any variable.
Definition: BayesTree-inst.h:253
gtsam::BayesTree::findParentClique
Key findParentClique(const CONTAINER &parents) const
Find parent clique of a conditional.
Definition: BayesTree-inst.h:221
gtsam::BayesTree::Clique
CLIQUE Clique
The clique type, normally BayesTreeClique.
Definition: BayesTree.h:71
gtsam::BayesTree::size
size_t size() const
number of cliques
Definition: BayesTree-inst.h:116
gtsam::Key
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:61
gtsam::BayesTree::insertRoot
void insertRoot(const sharedClique &subtree)
Insert a new subtree with known parent clique.
Definition: BayesTree-inst.h:243
gtsam::BayesTree::getCliqueData
BayesTreeCliqueData getCliqueData() const
Gather data on all cliques.
Definition: BayesTree-inst.h:38
gtsam::BayesTree::BayesTree
BayesTree()
Create an empty Bayes Tree.
Definition: BayesTree.h:107
gtsam::BayesTree::Nodes
ConcurrentMap< Key, sharedClique > Nodes
Map from keys to Clique.
Definition: BayesTree.h:90
gtsam::BayesTree::Roots
FastVector< sharedClique > Roots
Root cliques.
Definition: BayesTree.h:93
gtsam::EliminatableClusterTree
A cluster-tree that eliminates to a Bayes tree.
Definition: ClusterTree.h:184
gtsam::BayesTree::empty
bool empty() const
Check if there are any cliques in the tree.
Definition: BayesTree.h:136
gtsam::BayesTree::sharedNode
sharedClique sharedNode
Synonym for sharedClique (TODO: remove)
Definition: BayesTree.h:74
gtsam::FastList
Definition: FastList.h:38
gtsam
Global functions in a separate testing namespace.
Definition: chartTesting.h:28
gtsam::BayesTree::addFactorsToGraph
void addFactorsToGraph(FactorGraph< FactorType > *graph) const
Add all cliques in this BayesTree to the specified factor graph.
Definition: BayesTree-inst.h:151
gtsam::BayesTree::fillNodesIndex
void fillNodesIndex(const sharedClique &subtree)
Fill the nodes index for a subtree.
Definition: BayesTree-inst.h:229
gtsam::BayesTree::jointBayesNet
sharedBayesNet jointBayesNet(Key j1, Key j2, const Eliminate &function=EliminationTraitsType::DefaultEliminate) const
return joint on two variables as a BayesNet Limitation: can only calculate joint if cliques are disjo...
Definition: BayesTree-inst.h:285
gtsam::print
void print(const Matrix &A, const string &s, ostream &stream)
print without optional string, must specify cout yourself
Definition: Matrix.cpp:155
gtsam::BayesTree::nodes_
Nodes nodes_
Map from indices to Clique.
Definition: BayesTree.h:98
gtsam::BayesTree::operator=
This & operator=(const This &other)
Assignment operator.
Definition: BayesTree-inst.h:182
gtsam::GaussianBayesTreeClique
A clique in a GaussianBayesTree.
Definition: GaussianBayesTree.h:37
gtsam::BayesTreeOrphanWrapper
Definition: BayesTree.h:268
gtsam::BayesTree::removeSubtree
Cliques removeSubtree(const sharedClique &subtree)
Remove the requested subtree.
Definition: BayesTree-inst.h:479
gtsam::BayesTree::nodes
const Nodes & nodes() const
return nodes
Definition: BayesTree.h:141
gtsam::BayesTree::deleteCachedShortcuts
void deleteCachedShortcuts()
Clear all shortcut caches - use before timing on marginal calculation to avoid residual cache data.
Definition: BayesTree-inst.h:399
gtsam::BayesTreeCliqueData
store all the sizes
Definition: BayesTree.h:46
gtsam::BayesTree::joint
sharedFactorGraph joint(Key j1, Key j2, const Eliminate &function=EliminationTraitsType::DefaultEliminate) const
return joint on two variables Limitation: can only calculate joint if cliques are disjoint or one of ...
Definition: BayesTree-inst.h:276
gtsam::FactorGraph
A factor graph is a bipartite graph with factor nodes connected to variable nodes.
Definition: FactorGraph.h:94
Key.h
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::BayesTreeCliqueStats
clique statistics
Definition: BayesTree.h:37
FastList.h
A thin wrapper around std::list that uses boost's fast_pool_allocator.
gtsam::BayesTree::equals
bool equals(const This &other, double tol=1e-9) const
check equality
Definition: BayesTree-inst.h:213
gtsam::KeyVector
FastVector< Key > KeyVector
Define collection type once and for all - also used in wrappers.
Definition: Key.h:86
gtsam::BayesTree::roots_
Roots roots_
Root cliques.
Definition: BayesTree.h:101
gtsam::BayesTree::operator[]
const sharedNode operator[](Key j) const
Access node by variable.
Definition: BayesTree.h:144
gtsam::BayesTree::removeClique
void removeClique(sharedClique clique)
remove a clique: warning, can result in a forest
Definition: BayesTree-inst.h:407
gtsam::BayesTree::removeTop
void removeTop(const KeyVector &keys, BayesNetType *bn, Cliques *orphans)
Given a list of indices, turn "contaminated" part of the tree back into a factor graph.
Definition: BayesTree-inst.h:458
gtsam::BayesTree::roots
const Roots & roots() const
return root cliques
Definition: BayesTree.h:147
gtsam::BayesTree::saveGraph
void saveGraph(const std::string &s, const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
Read only with side effects.
Definition: BayesTree-inst.h:67
gtsam::BayesTree::clique
const sharedClique & clique(Key j) const
alternate syntax for matlab: find the clique that contains the variable with Key j
Definition: BayesTree.h:150
gtsam::BayesTree::print
void print(const std::string &s="", const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
print
Definition: BayesTree-inst.h:195
gtsam::BayesTree::addClique
void addClique(const sharedClique &clique, const sharedClique &parent_clique=sharedClique())
add a clique (top down)
Definition: BayesTree-inst.h:125