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 {
159 int operator()(
const std::shared_ptr<CLIQUE>& clique,
int dummy) {
167 template <
class CLIQUE>
172 _pushCliqueFunctor<FactorType, CLIQUE> functor(graph);
177 template<
class CLIQUE>
189 template<
class CLIQUE>
196 for (
auto&& root: roots_) {
197 std::queue<sharedClique> bfs_queue;
200 bfs_queue.push(root);
206 while (!bfs_queue.empty()) {
208 auto current = bfs_queue.front();
212 for (
auto child: current->children) {
213 bfs_queue.push(child);
223 template<
typename NODE>
224 std::shared_ptr<NODE>
225 BayesTreeCloneForestVisitorPre(
const std::shared_ptr<NODE>& node,
const std::shared_ptr<NODE>& parentPointer)
228 std::shared_ptr<NODE> clone = std::make_shared<NODE>(*node);
229 clone->children.clear();
230 clone->parent_ = parentPointer;
231 parentPointer->children.push_back(clone);
237 template<
class CLIQUE>
240 std::shared_ptr<Clique> rootContainer = std::make_shared<Clique>();
242 for(
const sharedClique& root: rootContainer->children) {
243 root->parent_ =
typename Clique::weak_ptr();
250 template<
class CLIQUE>
252 std::cout << s <<
": cliques: " << size() <<
", variables: " << nodes_.size() << std::endl;
258 template<
class CLIQUE>
259 bool check_sharedCliques(
263 return v1.first == v2.first &&
264 ((!v1.second && !v2.second) || (v1.second && v2.second && v1.second->equals(*v2.second)));
268 template<
class CLIQUE>
270 return size()==other.
size() &&
271 std::equal(nodes_.begin(), nodes_.end(), other.
nodes_.begin(), &check_sharedCliques<CLIQUE>);
275 template<
class CLIQUE>
276 template<
class CONTAINER>
278 typename CONTAINER::const_iterator lowestOrderedParent = min_element(parents.begin(), parents.end());
279 assert(lowestOrderedParent != parents.end());
280 return *lowestOrderedParent;
284 template<
class CLIQUE>
287 for(
const Key& j: subtree->conditional()->frontals()) {
288 bool inserted = nodes_.insert({j, subtree}).second;
289 assert(inserted); (void)inserted;
293 for(
const sharedClique& child: subtree->children) {
294 fillNodesIndex(child); }
298 template<
class CLIQUE>
300 roots_.push_back(subtree);
301 fillNodesIndex(subtree);
307 template<
class CLIQUE>
308 typename BayesTree<CLIQUE>::sharedConditional
311 gttic(BayesTree_marginalFactor);
317 FactorGraphType cliqueMarginal = clique->marginal2(
function);
320 BayesNetType marginalBN =
321 *cliqueMarginal.marginalMultifrontalBayesNet(
Ordering{j},
function);
324 return marginalBN.front();
330 template<
class CLIQUE>
331 typename BayesTree<CLIQUE>::sharedFactorGraph
334 gttic(BayesTree_joint);
335 return std::make_shared<FactorGraphType>(*jointBayesNet(j1, j2,
function));
339 template<
class CLIQUE>
340 typename BayesTree<CLIQUE>::sharedBayesNet
343 gttic(BayesTree_jointBayesNet);
347 gttic(Lowest_common_ancestor);
368 while(p1 != path1.end() && p2 != path2.end() && *p1 == *p2) {
374 gttoc(Lowest_common_ancestor);
377 FactorGraphType p_BC1C2;
383 FactorGraphType p_B = B->marginal2(
function);
387 gttic(Clique_shortcuts);
388 BayesNetType p_C1_Bred = C1->shortcut(B,
function);
389 BayesNetType p_C2_Bred = C2->shortcut(B,
function);
390 gttoc(Clique_shortcuts);
394 gttic(Full_root_factoring);
395 std::shared_ptr<typename EliminationTraitsType::BayesTreeType> p_C1_B; {
397 KeySet C1_minus_B_set(C1->conditional()->beginParents(), C1->conditional()->endParents());
398 for(
const Key j: *B->conditional()) {
399 C1_minus_B_set.erase(j); }
400 C1_minus_B.assign(C1_minus_B_set.begin(), C1_minus_B_set.end());
404 FactorGraphType(p_C1_Bred)
405 .eliminatePartialMultifrontal(
Ordering(C1_minus_B),
function)
408 std::shared_ptr<typename EliminationTraitsType::BayesTreeType> p_C2_B; {
410 KeySet C2_minus_B_set(C2->conditional()->beginParents(), C2->conditional()->endParents());
411 for(
const Key j: *B->conditional()) {
412 C2_minus_B_set.erase(j); }
413 C2_minus_B.assign(C2_minus_B_set.begin(), C2_minus_B_set.end());
417 FactorGraphType(p_C2_Bred)
418 .eliminatePartialMultifrontal(
Ordering(C2_minus_B),
function)
421 gttoc(Full_root_factoring);
423 gttic(Variable_joint);
424 p_BC1C2.push_back(p_B);
425 p_BC1C2.push_back(*p_C1_B);
426 p_BC1C2.push_back(*p_C2_B);
428 p_BC1C2.push_back(C1->conditional());
430 p_BC1C2.push_back(C2->conditional());
431 gttoc(Variable_joint);
437 gttic(Disjoint_marginals);
438 p_BC1C2.push_back(C1->marginal2(
function));
439 p_BC1C2.push_back(C2->marginal2(
function));
440 gttoc(Disjoint_marginals);
444 return p_BC1C2.marginalMultifrontalBayesNet(
Ordering{j1, j2},
function);
448 template<
class CLIQUE>
456 template<
class CLIQUE>
459 root->deleteCachedShortcuts();
464 template<
class CLIQUE>
467 if (clique->isRoot()) {
468 typename Roots::iterator root = std::find(roots_.begin(), roots_.end(), clique);
469 if(root != roots_.end())
473 typename Roots::iterator child = std::find(parent->children.begin(), parent->children.end(), clique);
474 assert(child != parent->children.end());
475 parent->children.erase(child);
480 child->parent_ =
typename Clique::weak_ptr();
482 for(
Key j: clique->conditional()->frontals()) {
483 nodes_.unsafe_erase(j);
488 template <
class CLIQUE>
494 orphans->remove(clique);
497 this->removeClique(clique);
500 this->removePath(
typename Clique::shared_ptr(clique->parent_.lock()), bn,
505 orphans->insert(orphans->begin(), clique->children.begin(),
506 clique->children.end());
507 clique->children.clear();
509 bn->push_back(clique->conditional_);
515 template <
class CLIQUE>
520 for (
const Key& j : keys) {
523 typename Nodes::const_iterator node = nodes_.find(j);
524 if (node != nodes_.end()) {
526 this->removePath(node->second, bn, orphans);
532 for (
sharedClique& orphan : *orphans) orphan->deleteCachedShortcuts();
536 template<
class CLIQUE>
542 cliques.push_back(subtree);
545 if(!subtree->isRoot())
546 subtree->parent()->children.erase(std::find(
547 subtree->parent()->children.begin(), subtree->parent()->children.end(), subtree));
549 roots_.erase(std::find(roots_.begin(), roots_.end(), subtree));
552 for(
typename Cliques::iterator clique = cliques.begin(); clique != cliques.end(); ++clique)
556 cliques.push_back(child); }
559 (*clique)->deleteCachedShortcutsNonRecursive();
562 for(
Key j: (*clique)->conditional()->frontals()) {
563 nodes_.unsafe_erase(j); }
566 (*clique)->parent_.reset();
567 (*clique)->children.clear();
void removePath(sharedClique clique, BayesNetType *bn, Cliques *orphans)
Definition: BayesTree-inst.h:489
void removeTop(const KeyVector &keys, BayesNetType *bn, Cliques *orphans)
Definition: BayesTree-inst.h:516
size_t size() const
Definition: BayesTree-inst.h:133
This & operator=(const This &other)
Definition: BayesTree-inst.h:238
double dot(const V1 &a, const V2 &b)
Definition: Vector.h:195
Nodes nodes_
Definition: BayesTree.h:100
void addClique(const sharedClique &clique, const sharedClique &parent_clique=sharedClique())
Definition: BayesTree-inst.h:142
IsDerived< DERIVEDFACTOR > push_back(std::shared_ptr< DERIVEDFACTOR > factor)
Add a factor directly using a shared_ptr.
Definition: FactorGraph.h:190
Definition: BayesTree.h:34
Variable ordering for the elimination algorithm.
bool equals(const This &other, double tol=1e-9) const
Definition: BayesTree-inst.h:269
Definition: Ordering.h:37
void fillNodesIndex(const sharedClique &subtree)
Definition: BayesTree-inst.h:285
Key findParentClique(const CONTAINER &parents) const
Definition: BayesTree-inst.h:277
std::shared_ptr< Clique > sharedClique
Shared pointer to a clique.
Definition: BayesTree.h:74
void insertRoot(const sharedClique &subtree)
Definition: BayesTree-inst.h:299
void DepthFirstForest(FOREST &forest, DATA &rootData, VISITOR_PRE &visitorPre, VISITOR_POST &visitorPost)
Definition: treeTraversal-inst.h:77
void deleteCachedShortcuts()
Definition: BayesTree-inst.h:457
Cliques removeSubtree(const sharedClique &subtree)
Definition: BayesTree-inst.h:537
BayesTreeCliqueData getCliqueData() const
Definition: BayesTree-inst.h:35
void saveGraph(const std::string &filename, const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
output to file with graphviz format.
Definition: BayesTree-inst.h:85
void PrintForest(const FOREST &forest, std::string str, const KeyFormatter &keyFormatter)
Definition: treeTraversal-inst.h:219
BayesTree()
Definition: BayesTree.h:109
void print(const std::string &s="", const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
Definition: BayesTree-inst.h:251
void addFactorsToGraph(FactorGraph< FactorType > *graph) const
Definition: BayesTree-inst.h:168
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
Bayes Tree is a tree of cliques of a Bayes Chain.
Definition: FastList.h:43
Definition: chartTesting.h:28
FastVector< Key > KeyVector
Define collection type once and for all - also used in wrappers.
Definition: Key.h:86
void dot(std::ostream &os, const KeyFormatter &keyFormatter=DefaultKeyFormatter) const
Output to graphviz format, stream version.
Definition: BayesTree-inst.h:64
void clear()
Definition: BayesTree-inst.h:449
void removeClique(sharedClique clique)
Definition: BayesTree-inst.h:465
~BayesTree()
Definition: BayesTree-inst.h:190
sharedBayesNet jointBayesNet(Key j1, Key j2, const Eliminate &function=EliminationTraitsType::DefaultEliminate) const
Definition: BayesTree-inst.h:341
Definition: BayesTree.h:48
sharedFactorGraph joint(Key j1, Key j2, const Eliminate &function=EliminationTraitsType::DefaultEliminate) const
Definition: BayesTree-inst.h:332
size_t numCachedSeparatorMarginals() const
Definition: BayesTree-inst.h:55
bool equal(const T &obj1, const T &obj2, double tol)
Definition: Testable.h:85
sharedConditional marginalFactor(Key j, const Eliminate &function=EliminationTraitsType::DefaultEliminate) const
Definition: BayesTree-inst.h:309
std::uint64_t Key
Integer nonlinear key type.
Definition: types.h:102