28#include <boost/optional.hpp>
34 template<
class CLIQUE>
37 for (
const sharedClique& root : roots_) getCliqueData(root, &stats);
42 template <
class CLIQUE>
45 const auto conditional = clique->conditional();
46 stats->conditionalSizes.push_back(conditional->nrFrontals());
47 stats->separatorSizes.push_back(conditional->nrParents());
49 getCliqueData(c, stats);
54 template<
class CLIQUE>
58 count += root->numCachedSeparatorMarginals();
63 template <
class CLIQUE>
67 throw std::invalid_argument(
68 "the root of Bayes tree has not been initialized!");
76 template <
class CLIQUE>
79 dot(ss, keyFormatter);
84 template <
class CLIQUE>
87 std::ofstream of(filename.c_str());
88 dot(of, keyFormatter);
93 template <
class CLIQUE>
96 int parentnum)
const {
99 std::stringstream out;
101 std::string parent = out.str();
102 parent +=
"[label=\"";
104 for (
Key key : clique->conditional_->frontals()) {
105 if (!first) parent +=
", ";
107 parent += keyFormatter(key);
110 if (clique->parent()) {
112 s << parentnum <<
"->" << num <<
"\n";
116 for (
Key parentKey : clique->conditional_->parents()) {
117 if (!first) parent +=
", ";
119 parent += keyFormatter(parentKey);
127 dot(s, c, keyFormatter, parentnum);
132 template<
class CLIQUE>
136 size += clique->treeSize();
141 template<
class CLIQUE>
143 for(
Key j: clique->conditional()->frontals())
145 if (parent_clique !=
nullptr) {
146 clique->parent_ = parent_clique;
147 parent_clique->children.push_back(clique);
149 roots_.push_back(clique);
155 template <
class FACTOR,
class CLIQUE>
156 struct _pushCliqueFunctor {
158 FactorGraph<FACTOR>* graph;
159 int operator()(
const boost::shared_ptr<CLIQUE>& clique,
int dummy) {
160 graph->push_back(clique->conditional_);
167 template <
class CLIQUE>
172 _pushCliqueFunctor<FactorType, CLIQUE> functor(graph);
177 template<
class CLIQUE>
184 template<
typename NODE>
185 boost::shared_ptr<NODE>
186 BayesTreeCloneForestVisitorPre(
const boost::shared_ptr<NODE>& node,
const boost::shared_ptr<NODE>& parentPointer)
189 boost::shared_ptr<NODE> clone = boost::make_shared<NODE>(*node);
190 clone->children.clear();
191 clone->parent_ = parentPointer;
192 parentPointer->children.push_back(clone);
198 template<
class CLIQUE>
201 boost::shared_ptr<Clique> rootContainer = boost::make_shared<Clique>();
203 for(
const sharedClique& root: rootContainer->children) {
204 root->parent_ =
typename Clique::weak_ptr();
211 template<
class CLIQUE>
213 std::cout << s <<
": cliques: " << size() <<
", variables: " << nodes_.size() << std::endl;
219 template<
class CLIQUE>
220 bool check_sharedCliques(
224 return v1.first == v2.first &&
225 ((!v1.second && !v2.second) || (v1.second && v2.second && v1.second->equals(*v2.second)));
229 template<
class CLIQUE>
231 return size()==other.
size() &&
232 std::equal(nodes_.begin(), nodes_.end(), other.
nodes_.begin(), &check_sharedCliques<CLIQUE>);
236 template<
class CLIQUE>
237 template<
class CONTAINER>
239 typename CONTAINER::const_iterator lowestOrderedParent = min_element(parents.begin(), parents.end());
240 assert(lowestOrderedParent != parents.end());
241 return *lowestOrderedParent;
245 template<
class CLIQUE>
248 for(
const Key& j: subtree->conditional()->frontals()) {
249 bool inserted = nodes_.insert(std::make_pair(j, subtree)).second;
250 assert(inserted); (void)inserted;
255 fillNodesIndex(child); }
259 template<
class CLIQUE>
261 roots_.push_back(subtree);
262 fillNodesIndex(subtree);
268 template<
class CLIQUE>
269 typename BayesTree<CLIQUE>::sharedConditional
272 gttic(BayesTree_marginalFactor);
278 FactorGraphType cliqueMarginal = clique->marginal2(function);
281 BayesNetType marginalBN =
282 *cliqueMarginal.marginalMultifrontalBayesNet(
Ordering{j}, function);
285 return marginalBN.front();
291 template<
class CLIQUE>
292 typename BayesTree<CLIQUE>::sharedFactorGraph
295 gttic(BayesTree_joint);
296 return boost::make_shared<FactorGraphType>(*jointBayesNet(j1, j2, function));
300 template<
class CLIQUE>
301 typename BayesTree<CLIQUE>::sharedBayesNet
304 gttic(BayesTree_jointBayesNet);
308 gttic(Lowest_common_ancestor);
329 while(p1 != path1.end() && p2 != path2.end() && *p1 == *p2) {
335 gttoc(Lowest_common_ancestor);
338 FactorGraphType p_BC1C2;
344 FactorGraphType p_B = B->marginal2(function);
348 gttic(Clique_shortcuts);
349 BayesNetType p_C1_Bred = C1->shortcut(B, function);
350 BayesNetType p_C2_Bred = C2->shortcut(B, function);
351 gttoc(Clique_shortcuts);
355 gttic(Full_root_factoring);
356 boost::shared_ptr<typename EliminationTraitsType::BayesTreeType> p_C1_B; {
358 KeySet C1_minus_B_set(C1->conditional()->beginParents(), C1->conditional()->endParents());
359 for(
const Key j: *B->conditional()) {
360 C1_minus_B_set.erase(j); }
361 C1_minus_B.assign(C1_minus_B_set.begin(), C1_minus_B_set.end());
364 sharedFactorGraph temp_remaining;
365 boost::tie(p_C1_B, temp_remaining) =
366 FactorGraphType(p_C1_Bred).eliminatePartialMultifrontal(
Ordering(C1_minus_B), function);
368 boost::shared_ptr<typename EliminationTraitsType::BayesTreeType> p_C2_B; {
370 KeySet C2_minus_B_set(C2->conditional()->beginParents(), C2->conditional()->endParents());
371 for(
const Key j: *B->conditional()) {
372 C2_minus_B_set.erase(j); }
373 C2_minus_B.assign(C2_minus_B_set.begin(), C2_minus_B_set.end());
376 sharedFactorGraph temp_remaining;
377 boost::tie(p_C2_B, temp_remaining) =
378 FactorGraphType(p_C2_Bred).eliminatePartialMultifrontal(
Ordering(C2_minus_B), function);
380 gttoc(Full_root_factoring);
382 gttic(Variable_joint);
387 p_BC1C2 += C1->conditional();
389 p_BC1C2 += C2->conditional();
390 gttoc(Variable_joint);
396 gttic(Disjoint_marginals);
397 p_BC1C2 += C1->marginal2(function);
398 p_BC1C2 += C2->marginal2(function);
399 gttoc(Disjoint_marginals);
403 return p_BC1C2.marginalMultifrontalBayesNet(
Ordering{j1, j2}, function);
407 template<
class CLIQUE>
415 template<
class CLIQUE>
418 root->deleteCachedShortcuts();
423 template<
class CLIQUE>
426 if (clique->isRoot()) {
427 typename Roots::iterator root = std::find(roots_.begin(), roots_.end(), clique);
428 if(root != roots_.end())
432 typename Roots::iterator child = std::find(parent->children.begin(), parent->children.end(), clique);
433 assert(child != parent->children.end());
434 parent->children.erase(child);
439 child->parent_ =
typename Clique::weak_ptr();
441 for(
Key j: clique->conditional()->frontals()) {
442 nodes_.unsafe_erase(j);
447 template <
class CLIQUE>
453 orphans->remove(clique);
456 this->removeClique(clique);
459 this->removePath(
typename Clique::shared_ptr(clique->parent_.lock()), bn,
464 orphans->insert(orphans->begin(), clique->children.begin(),
465 clique->children.end());
466 clique->children.clear();
468 bn->push_back(clique->conditional_);
474 template <
class CLIQUE>
479 for (
const Key& j : keys) {
482 typename Nodes::const_iterator node = nodes_.find(j);
483 if (node != nodes_.end()) {
485 this->removePath(node->second, bn, orphans);
491 for (
sharedClique& orphan : *orphans) orphan->deleteCachedShortcuts();
495 template<
class CLIQUE>
501 cliques.push_back(subtree);
504 if(!subtree->isRoot())
505 subtree->parent()->children.erase(std::find(
506 subtree->parent()->children.begin(), subtree->parent()->children.end(), subtree));
508 roots_.erase(std::find(roots_.begin(), roots_.end(), subtree));
511 for(
typename Cliques::iterator clique = cliques.begin(); clique != cliques.end(); ++clique)
515 cliques.push_back(child); }
518 (*clique)->deleteCachedShortcutsNonRecursive();
521 for(
Key j: (*clique)->conditional()->frontals()) {
522 nodes_.unsafe_erase(j); }
525 (*clique)->parent_.reset();
526 (*clique)->children.clear();
Bayes Tree is a tree of cliques of a Bayes Chain.
Variable ordering for the elimination algorithm.
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
bool equal(const T &obj1, const T &obj2, double tol)
Call equal on the object.
Definition: Testable.h:84
double dot(const V1 &a, const V2 &b)
Dot product.
Definition: Vector.h:195
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
void DepthFirstForest(FOREST &forest, DATA &rootData, VISITOR_PRE &visitorPre, VISITOR_POST &visitorPost)
Traverse a forest depth-first with pre-order and post-order visits.
Definition: treeTraversal-inst.h:77
void PrintForest(const FOREST &forest, std::string str, const KeyFormatter &keyFormatter)
Print a tree, prefixing each line with str, and formatting keys using keyFormatter.
Definition: treeTraversal-inst.h:219
FastList is a thin wrapper around std::list that uses the boost fast_pool_allocator instead of the de...
Definition: FastList.h:40
A factor graph is a bipartite graph with factor nodes connected to variable nodes.
Definition: FactorGraph.h:97
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
bool equals(const This &other, double tol=1e-9) const
check equality
Definition: BayesTree-inst.h:230
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
void clear()
Remove all nodes.
Definition: BayesTree-inst.h:408
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
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
sharedConditional marginalFactor(Key j, const Eliminate &function=EliminationTraitsType::DefaultEliminate) const
Return marginal on any variable.
Definition: BayesTree-inst.h:270
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
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
Definition: Ordering.h:34