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