gtsam 4.2.0
gtsam
Loading...
Searching...
No Matches
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 <boost/shared_ptr.hpp>
23
24#include <gtsam/inference/Key.h>
25#include <gtsam/base/FastList.h>
26#include <gtsam/base/ConcurrentMap.h>
28
29#include <string>
30
31namespace gtsam {
32
33 // Forward declarations
34 template<class FACTOR> class FactorGraph;
35 template<class BAYESTREE, class GRAPH> class EliminatableClusterTree;
36
37 /* ************************************************************************* */
39 struct GTSAM_EXPORT BayesTreeCliqueStats {
40 double avgConditionalSize;
41 std::size_t maxConditionalSize;
42 double avgSeparatorSize;
43 std::size_t maxSeparatorSize;
44 void print(const std::string& s = "") const ;
45 };
46
48 struct GTSAM_EXPORT BayesTreeCliqueData {
49 FastVector<std::size_t> conditionalSizes;
50 FastVector<std::size_t> separatorSizes;
51 BayesTreeCliqueStats getStats() const;
52 };
53
54 /* ************************************************************************* */
65 template<class CLIQUE>
67 {
68 protected:
69 typedef BayesTree<CLIQUE> This;
70 typedef boost::shared_ptr<This> shared_ptr;
71
72 public:
73 typedef CLIQUE Clique;
74 typedef boost::shared_ptr<Clique> sharedClique;
75 typedef Clique Node;
77 typedef typename CLIQUE::ConditionalType ConditionalType;
78 typedef boost::shared_ptr<ConditionalType> sharedConditional;
79 typedef typename CLIQUE::BayesNetType BayesNetType;
80 typedef boost::shared_ptr<BayesNetType> sharedBayesNet;
81 typedef typename CLIQUE::FactorType FactorType;
82 typedef boost::shared_ptr<FactorType> sharedFactor;
83 typedef typename CLIQUE::FactorGraphType FactorGraphType;
84 typedef boost::shared_ptr<FactorGraphType> sharedFactorGraph;
85 typedef typename FactorGraphType::Eliminate Eliminate;
86 typedef typename CLIQUE::EliminationTraitsType EliminationTraitsType;
87
90
93
96
97 protected:
98
101
104
107
110
112 BayesTree(const This& other);
113
115
117 This& operator=(const This& other);
118
121
123 bool equals(const This& other, double tol = 1e-9) const;
124
125 public:
127 void print(const std::string& s = "",
128 const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
130
133
135 size_t size() const;
136
138 inline bool empty() const {
139 return nodes_.empty();
140 }
141
143 const Nodes& nodes() const { return nodes_; }
144
146 sharedClique operator[](Key j) const { return nodes_.at(j); }
147
149 const Roots& roots() const { return roots_; }
150
152 const sharedClique& clique(Key j) const {
153 typename Nodes::const_iterator c = nodes_.find(j);
154 if(c == nodes_.end())
155 throw std::out_of_range("Requested the BayesTree clique for a key that is not in the BayesTree");
156 else
157 return c->second;
158 }
159
162
164 size_t numCachedSeparatorMarginals() const;
165
171 sharedConditional marginalFactor(Key j, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
172
177 sharedFactorGraph joint(Key j1, Key j2, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
178
183 sharedBayesNet jointBayesNet(Key j1, Key j2, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
184
187
189 void dot(std::ostream& os, const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
190
192 std::string dot(
193 const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
194
196 void saveGraph(const std::string& filename,
197 const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
198
202
207 template<class CONTAINER>
208 Key findParentClique(const CONTAINER& parents) const;
209
211 void clear();
212
215
220 void removePath(sharedClique clique, BayesNetType* bn, Cliques* orphans);
221
226 void removeTop(const KeyVector& keys, BayesNetType* bn, Cliques* orphans);
227
230 Cliques removeSubtree(const sharedClique& subtree);
231
235 void insertRoot(const sharedClique& subtree);
236
238 void addClique(const sharedClique& clique, const sharedClique& parent_clique = sharedClique());
239
242
243 protected:
244
246 void dot(std::ostream &s, sharedClique clique, const KeyFormatter& keyFormatter,
247 int parentnum = 0) const;
248
251
254
256 void fillNodesIndex(const sharedClique& subtree);
257
258 // Friend JunctionTree because it directly fills roots and nodes index.
259 template<class BAYESTREE, class GRAPH> friend class EliminatableClusterTree;
260
261 private:
264 template<class ARCHIVE>
265 void serialize(ARCHIVE & ar, const unsigned int /*version*/) {
266 ar & BOOST_SERIALIZATION_NVP(nodes_);
267 ar & BOOST_SERIALIZATION_NVP(roots_);
268 }
269
271
272 }; // BayesTree
273
274 /* ************************************************************************* */
275 template <class CLIQUE, typename = void>
276 class BayesTreeOrphanWrapper : public CLIQUE::ConditionalType {
277 public:
278 typedef CLIQUE CliqueType;
279 typedef typename CLIQUE::ConditionalType Base;
280
281 boost::shared_ptr<CliqueType> clique;
282
293 BayesTreeOrphanWrapper(const boost::shared_ptr<CliqueType>& clique)
294 : clique(clique) {
295 this->keys_.assign(clique->conditional()->beginParents(),
296 clique->conditional()->endParents());
297 }
298
299 void print(
300 const std::string& s = "",
301 const KeyFormatter& formatter = DefaultKeyFormatter) const override {
302 clique->print(s + "stored clique", formatter);
303 }
304 };
305
306}
A thin wrapper around std::vector that uses a custom allocator.
A thin wrapper around std::list that uses boost's fast_pool_allocator.
std::vector< T, typename internal::FastDefaultVectorAllocator< T >::type > FastVector
FastVector is a type alias to a std::vector with a custom memory allocator.
Definition FastVector.h:34
Global functions in a separate testing namespace.
Definition chartTesting.h:28
FastVector< Key > KeyVector
Define collection type once and for all - also used in wrappers.
Definition Key.h:86
void print(const Matrix &A, const string &s, ostream &stream)
print without optional string, must specify cout yourself
Definition Matrix.cpp:156
std::uint64_t Key
Integer nonlinear key type.
Definition types.h:100
std::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
FastMap is a thin wrapper around std::map that uses the boost fast_pool_allocator instead of the defa...
Definition ConcurrentMap.h:68
FastList is a thin wrapper around std::list that uses the boost fast_pool_allocator instead of the de...
Definition FastList.h:40
Template to create a binary predicate.
Definition Testable.h:111
A factor graph is a bipartite graph with factor nodes connected to variable nodes.
Definition FactorGraph.h:97
A cluster-tree that eliminates to a Bayes tree.
Definition ClusterTree.h:184
clique statistics
Definition BayesTree.h:39
store all the sizes
Definition BayesTree.h:48
Bayes tree.
Definition BayesTree.h:67
Nodes nodes_
Map from indices to Clique.
Definition BayesTree.h:100
void removeClique(sharedClique clique)
remove a clique: warning, can result in a forest
Definition BayesTree-inst.h:424
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:293
void fillNodesIndex(const sharedClique &subtree)
Fill the nodes index for a subtree.
Definition BayesTree-inst.h:246
void dot(std::ostream &os, const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
Output to graphviz format, stream version.
Definition BayesTree-inst.h:64
void addFactorsToGraph(FactorGraph< FactorType > *graph) const
Add all cliques in this BayesTree to the specified factor graph.
Definition BayesTree-inst.h:168
sharedClique operator[](Key j) const
Access node by variable.
Definition BayesTree.h:146
This & operator=(const This &other)
Assignment operator.
Definition BayesTree-inst.h:199
boost::shared_ptr< Clique > sharedClique
Shared pointer to a clique.
Definition BayesTree.h:74
BayesTree()
Create an empty Bayes Tree.
Definition BayesTree.h:109
Clique Node
Synonym for Clique (TODO: remove)
Definition BayesTree.h:75
void clear()
Remove all nodes.
Definition BayesTree-inst.h:408
Roots roots_
Root cliques.
Definition BayesTree.h:103
void addClique(const sharedClique &clique, const sharedClique &parent_clique=sharedClique())
add a clique (top down)
Definition BayesTree-inst.h:142
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:302
sharedClique sharedNode
Synonym for sharedClique (TODO: remove)
Definition BayesTree.h:76
Key findParentClique(const CONTAINER &parents) const
Find parent clique of a conditional.
Definition BayesTree-inst.h:238
size_t size() const
number of cliques
Definition BayesTree-inst.h:133
void deleteCachedShortcuts()
Clear all shortcut caches - use before timing on marginal calculation to avoid residual cache data.
Definition BayesTree-inst.h:416
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:448
const Nodes & nodes() const
Return nodes.
Definition BayesTree.h:143
FastList< sharedClique > Cliques
A convenience class for a list of shared cliques.
Definition BayesTree.h:89
CLIQUE Clique
The clique type, normally BayesTreeClique.
Definition BayesTree.h:73
sharedConditional marginalFactor(Key j, const Eliminate &function=EliminationTraitsType::DefaultEliminate) const
Return marginal on any variable.
Definition BayesTree-inst.h:270
const Roots & roots() const
return root cliques
Definition BayesTree.h:149
const sharedClique & clique(Key j) const
alternate syntax for matlab: find the clique that contains the variable with Key j
Definition BayesTree.h:152
ConcurrentMap< Key, sharedClique > Nodes
Map from keys to Clique.
Definition BayesTree.h:92
friend class boost::serialization::access
Serialization function.
Definition BayesTree.h:263
size_t numCachedSeparatorMarginals() const
Collect number of cliques with cached separator marginals.
Definition BayesTree-inst.h:55
BayesTreeCliqueData getCliqueData() const
Gather data on all cliques.
Definition BayesTree-inst.h:35
Cliques removeSubtree(const sharedClique &subtree)
Remove the requested subtree.
Definition BayesTree-inst.h:496
bool empty() const
Check if there are any cliques in the tree.
Definition BayesTree.h:138
void print(const std::string &s="", const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
print
Definition BayesTree-inst.h:212
void insertRoot(const sharedClique &subtree)
Insert a new subtree with known parent clique.
Definition BayesTree-inst.h:260
void saveGraph(const std::string &filename, const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
output to file with graphviz format.
Definition BayesTree-inst.h:85
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:475
FastVector< sharedClique > Roots
Root cliques.
Definition BayesTree.h:95
Definition BayesTree.h:276
BayesTreeOrphanWrapper(const boost::shared_ptr< CliqueType > &clique)
Construct a new Bayes Tree Orphan Wrapper object.
Definition BayesTree.h:293