gtsam 4.2.0
gtsam
Loading...
Searching...
No Matches
JunctionTree-inst.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
21#pragma once
22
27
28namespace gtsam {
29
30template<class BAYESTREE, class GRAPH, class ETREE_NODE>
33 typedef typename JunctionTree<BAYESTREE, GRAPH>::sharedNode sharedNode;
34
35 ConstructorTraversalData* const parentData;
36 sharedNode junctionTreeNode;
37 FastVector<SymbolicConditional::shared_ptr> childSymbolicConditionals;
38 FastVector<SymbolicFactor::shared_ptr> childSymbolicFactors;
39
40 // Small inner class to store symbolic factors
41 class SymbolicFactors: public FactorGraph<Factor> {
42 };
43
45 parentData(_parentData) {
46 }
47
48 // Pre-order visitor function
49 static ConstructorTraversalData ConstructorTraversalVisitorPre(
50 const boost::shared_ptr<ETREE_NODE>& node,
51 ConstructorTraversalData& parentData) {
52 // On the pre-order pass, before children have been visited, we just set up
53 // a traversal data structure with its own JT node, and create a child
54 // pointer in its parent.
56 myData.junctionTreeNode =
57 boost::make_shared<Node>(node->key, node->factors);
58 parentData.junctionTreeNode->addChild(myData.junctionTreeNode);
59 return myData;
60 }
61
62 // Post-order visitor function
63 static void ConstructorTraversalVisitorPostAlg2(
64 const boost::shared_ptr<ETREE_NODE>& ETreeNode,
65 const ConstructorTraversalData& myData) {
66 // In this post-order visitor, we combine the symbolic elimination results
67 // from the elimination tree children and symbolically eliminate the current
68 // elimination tree node. We then check whether each of our elimination
69 // tree child nodes should be merged with us. The check for this is that
70 // our number of symbolic elimination parents is exactly 1 less than
71 // our child's symbolic elimination parents - this condition indicates that
72 // eliminating the current node did not introduce any parents beyond those
73 // already in the child->
74
75 // Do symbolic elimination for this node
76 SymbolicFactors symbolicFactors;
77 symbolicFactors.reserve(
78 ETreeNode->factors.size() + myData.childSymbolicFactors.size());
79 // Add ETree node factors
80 symbolicFactors += ETreeNode->factors;
81 // Add symbolic factors passed up from children
82 symbolicFactors += myData.childSymbolicFactors;
83
84 Ordering keyAsOrdering;
85 keyAsOrdering.push_back(ETreeNode->key);
87 SymbolicFactor::shared_ptr mySeparatorFactor;
88 boost::tie(myConditional, mySeparatorFactor) = internal::EliminateSymbolic(
89 symbolicFactors, keyAsOrdering);
90
91 // Store symbolic elimination results in the parent
92 myData.parentData->childSymbolicConditionals.push_back(myConditional);
93 myData.parentData->childSymbolicFactors.push_back(mySeparatorFactor);
94
95 sharedNode node = myData.junctionTreeNode;
96 const FastVector<SymbolicConditional::shared_ptr>& childConditionals =
97 myData.childSymbolicConditionals;
98 node->problemSize_ = (int) (myConditional->size() * symbolicFactors.size());
99
100 // Merge our children if they are in our clique - if our conditional has
101 // exactly one fewer parent than our child's conditional.
102 const size_t myNrParents = myConditional->nrParents();
103 const size_t nrChildren = node->nrChildren();
104 assert(childConditionals.size() == nrChildren);
105
106 // decide which children to merge, as index into children
107 std::vector<size_t> nrFrontals = node->nrFrontalsOfChildren();
108 std::vector<bool> merge(nrChildren, false);
109 size_t myNrFrontals = 1;
110 for (size_t i = 0;i<nrChildren;i++){
111 // Check if we should merge the i^th child
112 if (myNrParents + myNrFrontals == childConditionals[i]->nrParents()) {
113 // Increment number of frontal variables
114 myNrFrontals += nrFrontals[i];
115 merge[i] = true;
116 }
117 }
118
119 // now really merge
120 node->mergeChildren(merge);
121 }
122};
123
124/* ************************************************************************* */
125template<class BAYESTREE, class GRAPH>
126template<class ETREE_BAYESNET, class ETREE_GRAPH>
128 const EliminationTree<ETREE_BAYESNET, ETREE_GRAPH>& eliminationTree) {
129 gttic(JunctionTree_FromEliminationTree);
130 // Here we rely on the BayesNet having been produced by this elimination tree,
131 // such that the conditionals are arranged in DFS post-order. We traverse the
132 // elimination tree, and inspect the symbolic conditional corresponding to
133 // each node. The elimination tree node is added to the same clique with its
134 // parent if it has exactly one more Bayes net conditional parent than
135 // does its elimination tree parent.
136
137 // Traverse the elimination tree, doing symbolic elimination and merging nodes
138 // as we go. Gather the created junction tree roots in a dummy Node.
141 Data rootData(0);
142 // Make a dummy node to gather the junction tree roots
143 rootData.junctionTreeNode = boost::make_shared<typename Base::Node>();
144 treeTraversal::DepthFirstForest(eliminationTree, rootData,
145 Data::ConstructorTraversalVisitorPre,
146 Data::ConstructorTraversalVisitorPostAlg2);
147
148 // Assign roots from the dummy node
149 this->addChildrenAsRoots(rootData.junctionTreeNode);
150
151 // Transfer remaining factors from elimination tree
152 Base::remainingFactors_ = eliminationTree.remainingFactors();
153}
154
155} // namespace gtsam
Collects factorgraph fragments defined on variable clusters, arranged in a tree.
The junction tree.
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
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
A factor graph is a bipartite graph with factor nodes connected to variable nodes.
Definition FactorGraph.h:97
A Cluster is just a collection of factors.
Definition ClusterTree.h:36
An elimination tree is a data structure used intermediately during elimination.
Definition EliminationTree.h:52
const FastVector< sharedFactor > & remainingFactors() const
Return the remaining factors that are not pulled into elimination.
Definition EliminationTree.h:154
Definition EliminationTree.h:66
Definition JunctionTree-inst.h:31
Definition JunctionTree-inst.h:41
A JunctionTree is a cluster tree, a set of variable clusters with factors, arranged in a tree,...
Definition JunctionTree.h:50
Definition Ordering.h:34
boost::shared_ptr< This > shared_ptr
Typedef to the conditional base class.
Definition SymbolicConditional.h:44
boost::shared_ptr< This > shared_ptr
Overriding the shared_ptr typedef.
Definition SymbolicFactor.h:48