Loading...
Searching...
No Matches
BayesTree.h
Go to the documentation of this file.
/* ----------------------------------------------------------------------------
* GTSAM Copyright 2010, Georgia Tech Research Corporation,
* Atlanta, Georgia 30332-0415
* All Rights Reserved
* Authors: Frank Dellaert, et al. (see THANKS for the full author list)
* See LICENSE for the license information
* -------------------------------------------------------------------------- */
// \callgraph
#pragma once
#include <boost/shared_ptr.hpp>
#include <gtsam/inference/Key.h>
#include <gtsam/base/FastList.h>
#include <gtsam/base/ConcurrentMap.h>
#include <gtsam/base/FastVector.h>
#include <string>
namespace gtsam {
// Forward declarations
template<class FACTOR> class FactorGraph;
template<class BAYESTREE, class GRAPH> class EliminatableClusterTree;
/* ************************************************************************* */
struct GTSAM_EXPORT BayesTreeCliqueStats {
double avgConditionalSize;
std::size_t maxConditionalSize;
double avgSeparatorSize;
std::size_t maxSeparatorSize;
void print(const std::string& s = "") const ;
};
struct GTSAM_EXPORT BayesTreeCliqueData {
FastVector<std::size_t> conditionalSizes;
FastVector<std::size_t> separatorSizes;
BayesTreeCliqueStats getStats() const;
};
/* ************************************************************************* */
template<class CLIQUE>
class BayesTree
{
protected:
typedef BayesTree<CLIQUE> This;
typedef boost::shared_ptr<This> shared_ptr;
public:
typedef CLIQUE Clique;
typedef boost::shared_ptr<Clique> sharedClique;
typedef Clique Node;
typedef sharedClique sharedNode;
typedef typename CLIQUE::ConditionalType ConditionalType;
typedef boost::shared_ptr<ConditionalType> sharedConditional;
typedef typename CLIQUE::BayesNetType BayesNetType;
typedef boost::shared_ptr<BayesNetType> sharedBayesNet;
typedef typename CLIQUE::FactorType FactorType;
typedef boost::shared_ptr<FactorType> sharedFactor;
typedef typename CLIQUE::FactorGraphType FactorGraphType;
typedef boost::shared_ptr<FactorGraphType> sharedFactorGraph;
typedef typename FactorGraphType::Eliminate Eliminate;
typedef typename CLIQUE::EliminationTraitsType EliminationTraitsType;
typedef FastList<sharedClique> Cliques;
typedef ConcurrentMap<Key, sharedClique> Nodes;
typedef FastVector<sharedClique> Roots;
protected:
Nodes nodes_;
Roots roots_;
BayesTree() {}
BayesTree(const This& other);
This& operator=(const This& other);
bool equals(const This& other, double tol = 1e-9) const;
public:
void print(const std::string& s = "",
const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
size_t size() const;
inline bool empty() const {
return nodes_.empty();
}
const Nodes& nodes() const { return nodes_; }
sharedClique operator[](Key j) const { return nodes_.at(j); }
const Roots& roots() const { return roots_; }
const sharedClique& clique(Key j) const {
typename Nodes::const_iterator c = nodes_.find(j);
if(c == nodes_.end())
throw std::out_of_range("Requested the BayesTree clique for a key that is not in the BayesTree");
else
return c->second;
}
BayesTreeCliqueData getCliqueData() const;
size_t numCachedSeparatorMarginals() const;
sharedConditional marginalFactor(Key j, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
sharedFactorGraph joint(Key j1, Key j2, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
sharedBayesNet jointBayesNet(Key j1, Key j2, const Eliminate& function = EliminationTraitsType::DefaultEliminate) const;
void dot(std::ostream& os, const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
std::string dot(
const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
void saveGraph(const std::string& filename,
const KeyFormatter& keyFormatter = DefaultKeyFormatter) const;
template<class CONTAINER>
Key findParentClique(const CONTAINER& parents) const;
void clear();
void deleteCachedShortcuts();
void removePath(sharedClique clique, BayesNetType* bn, Cliques* orphans);
void removeTop(const KeyVector& keys, BayesNetType* bn, Cliques* orphans);
Cliques removeSubtree(const sharedClique& subtree);
void insertRoot(const sharedClique& subtree);
void addClique(const sharedClique& clique, const sharedClique& parent_clique = sharedClique());
void addFactorsToGraph(FactorGraph<FactorType>* graph) const;
protected:
void dot(std::ostream &s, sharedClique clique, const KeyFormatter& keyFormatter,
int parentnum = 0) const;
void getCliqueData(sharedClique clique, BayesTreeCliqueData* stats) const;
void removeClique(sharedClique clique);
void fillNodesIndex(const sharedClique& subtree);
// Friend JunctionTree because it directly fills roots and nodes index.
template<class BAYESTREE, class GRAPH> friend class EliminatableClusterTree;
private:
friend class boost::serialization::access;
template<class ARCHIVE>
void serialize(ARCHIVE & ar, const unsigned int /*version*/) {
ar & BOOST_SERIALIZATION_NVP(nodes_);
ar & BOOST_SERIALIZATION_NVP(roots_);
}
}; // BayesTree
/* ************************************************************************* */
template <class CLIQUE, typename = void>
class BayesTreeOrphanWrapper : public CLIQUE::ConditionalType {
public:
typedef CLIQUE CliqueType;
typedef typename CLIQUE::ConditionalType Base;
boost::shared_ptr<CliqueType> clique;
BayesTreeOrphanWrapper(const boost::shared_ptr<CliqueType>& clique)
: clique(clique) {
this->keys_.assign(clique->conditional()->beginParents(),
clique->conditional()->endParents());
}
void print(
const std::string& s = "",
const KeyFormatter& formatter = DefaultKeyFormatter) const override {
clique->print(s + "stored clique", formatter);
}
};
}
FastVector.h
A thin wrapper around std::vector that uses a custom allocator.
FastList.h
A thin wrapper around std::list that uses boost's fast_pool_allocator.
Key.h
gtsam::FastVector
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:33
gtsam
Global functions in a separate testing namespace.
Definition chartTesting.h:28
gtsam::KeyVector
FastVector< Key > KeyVector
Define collection type once and for all - also used in wrappers.
Definition Key.h:86
gtsam::print
void print(const Matrix &A, const string &s, ostream &stream)
print without optional string, must specify cout yourself
Definition Matrix.cpp:156
gtsam::KeyFormatter
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
gtsam::Key
std::uint64_t Key
Integer nonlinear key type.
Definition types.h:100
gtsam::ConcurrentMap
FastMap is a thin wrapper around std::map that uses the boost fast_pool_allocator instead of the defa...
Definition ConcurrentMap.h:68
gtsam::FastList
FastList is a thin wrapper around std::list that uses the boost fast_pool_allocator instead of the de...
Definition FastList.h:40
gtsam::EliminationTraits< DiscreteFactorGraph >::DefaultEliminate
static std::pair< boost::shared_ptr< ConditionalType >, boost::shared_ptr< FactorType > > DefaultEliminate(const FactorGraphType &factors, const Ordering &keys)
The default dense elimination function.
Definition DiscreteFactorGraph.h:82
gtsam::FactorGraph
A factor graph is a bipartite graph with factor nodes connected to variable nodes.
Definition FactorGraph.h:97
gtsam::EliminatableClusterTree
A cluster-tree that eliminates to a Bayes tree.
Definition ClusterTree.h:184
gtsam::BayesTreeCliqueStats
clique statistics
Definition BayesTree.h:39
gtsam::BayesTreeCliqueData
store all the sizes
Definition BayesTree.h:48
gtsam::BayesTree< DiscreteBayesTreeClique >::nodes_
Nodes nodes_
Definition BayesTree.h:100
gtsam::BayesTree::removeClique
void removeClique(sharedClique clique)
remove a clique: warning, can result in a forest
Definition BayesTree-inst.h:424
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:293
gtsam::BayesTree::fillNodesIndex
void fillNodesIndex(const sharedClique &subtree)
Fill the nodes index for a subtree.
Definition BayesTree-inst.h:246
gtsam::BayesTree::dot
void dot(std::ostream &s, sharedClique clique, const KeyFormatter &keyFormatter, int parentnum=0) const
private helper method for saving the Tree to a text file in GraphViz format
Definition BayesTree-inst.h:94
gtsam::BayesTree::dot
void dot(std::ostream &os, const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
Output to graphviz format, stream version.
Definition BayesTree-inst.h:64
gtsam::BayesTree::addFactorsToGraph
void addFactorsToGraph(FactorGraph< FactorType > *graph) const
Add all cliques in this BayesTree to the specified factor graph.
Definition BayesTree-inst.h:168
gtsam::BayesTree::equals
bool equals(const This &other, double tol=1e-9) const
check equality
Definition BayesTree-inst.h:230
gtsam::BayesTree::operator[]
sharedClique operator[](Key j) const
Access node by variable.
Definition BayesTree.h:146
gtsam::BayesTree::operator=
This & operator=(const This &other)
Assignment operator.
Definition BayesTree-inst.h:199
gtsam::BayesTree< DiscreteBayesTreeClique >::sharedClique
boost::shared_ptr< Clique > sharedClique
Definition BayesTree.h:74
gtsam::BayesTree::BayesTree
BayesTree()
Create an empty Bayes Tree.
Definition BayesTree.h:109
gtsam::BayesTree< DiscreteBayesTreeClique >::Node
Clique Node
Definition BayesTree.h:75
gtsam::BayesTree::clear
void clear()
Remove all nodes.
Definition BayesTree-inst.h:408
gtsam::BayesTree< DiscreteBayesTreeClique >::roots_
Roots roots_
Definition BayesTree.h:103
gtsam::BayesTree::addClique
void addClique(const sharedClique &clique, const sharedClique &parent_clique=sharedClique())
add a clique (top down)
Definition BayesTree-inst.h:142
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:302
gtsam::BayesTree::dot
std::string dot(const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
Output to graphviz format string.
Definition BayesTree-inst.h:77
gtsam::BayesTree< DiscreteBayesTreeClique >::sharedNode
sharedClique sharedNode
Definition BayesTree.h:76
gtsam::BayesTree::findParentClique
Key findParentClique(const CONTAINER &parents) const
Find parent clique of a conditional.
Definition BayesTree-inst.h:238
gtsam::BayesTree::size
size_t size() const
number of cliques
Definition BayesTree-inst.h:133
gtsam::BayesTree::getCliqueData
void getCliqueData(sharedClique clique, BayesTreeCliqueData *stats) const
Gather data on a single clique.
Definition BayesTree-inst.h:43
gtsam::BayesTree::deleteCachedShortcuts
void deleteCachedShortcuts()
Clear all shortcut caches - use before timing on marginal calculation to avoid residual cache data.
Definition BayesTree-inst.h:416
gtsam::BayesTree::BayesTree
BayesTree(const This &other)
Copy constructor.
Definition BayesTree-inst.h:178
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:448
gtsam::BayesTree::nodes
const Nodes & nodes() const
Return nodes.
Definition BayesTree.h:143
gtsam::BayesTree< DiscreteBayesTreeClique >::Cliques
FastList< sharedClique > Cliques
Definition BayesTree.h:89
gtsam::BayesTree< DiscreteBayesTreeClique >::Clique
DiscreteBayesTreeClique Clique
Definition BayesTree.h:73
gtsam::BayesTree::marginalFactor
sharedConditional marginalFactor(Key j, const Eliminate &function=EliminationTraitsType::DefaultEliminate) const
Return marginal on any variable.
Definition BayesTree-inst.h:270
gtsam::BayesTree::roots
const Roots & roots() const
return root cliques
Definition BayesTree.h:149
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:152
gtsam::BayesTree< DiscreteBayesTreeClique >::Nodes
ConcurrentMap< Key, sharedClique > Nodes
Definition BayesTree.h:92
gtsam::BayesTree::numCachedSeparatorMarginals
size_t numCachedSeparatorMarginals() const
Collect number of cliques with cached separator marginals.
Definition BayesTree-inst.h:55
gtsam::BayesTree::getCliqueData
BayesTreeCliqueData getCliqueData() const
Gather data on all cliques.
Definition BayesTree-inst.h:35
gtsam::BayesTree::removeSubtree
Cliques removeSubtree(const sharedClique &subtree)
Remove the requested subtree.
Definition BayesTree-inst.h:496
gtsam::BayesTree::empty
bool empty() const
Check if there are any cliques in the tree.
Definition BayesTree.h:138
gtsam::BayesTree::print
void print(const std::string &s="", const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
print
Definition BayesTree-inst.h:212
gtsam::BayesTree::insertRoot
void insertRoot(const sharedClique &subtree)
Insert a new subtree with known parent clique.
Definition BayesTree-inst.h:260
gtsam::BayesTree::saveGraph
void saveGraph(const std::string &filename, const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
output to file with graphviz format.
Definition BayesTree-inst.h:85
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:475
gtsam::BayesTree< DiscreteBayesTreeClique >::Roots
FastVector< sharedClique > Roots
Definition BayesTree.h:95
gtsam::BayesTreeOrphanWrapper::BayesTreeOrphanWrapper
BayesTreeOrphanWrapper(const boost::shared_ptr< CliqueType > &clique)
Construct a new Bayes Tree Orphan Wrapper object.
Definition BayesTree.h:293
gtsam::EliminateableFactorGraph< DiscreteFactorGraph >::Eliminate
std::function< EliminationResult(const FactorGraphType &, const Ordering &)> Eliminate
Definition EliminateableFactorGraph.h:89