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
12/**
13 * @file EliminateableFactorGraph.h
14 * @brief Variable elimination algorithms for factor graphs
15 * @author Richard Roberts
16 * @date Apr 21, 2013
17 */
18
19#pragma once
20
21#include <memory>
22#include <cstddef>
23#include <functional>
24#include <optional>
25
26#include <gtsam/inference/Ordering.h>
27#include <gtsam/inference/VariableIndex.h>
28
29namespace gtsam {
30 /// Traits class for eliminateable factor graphs, specifies the types that result from
31 /// elimination, etc. This must be defined for each factor graph that inherits from
32 /// EliminateableFactorGraph.
33 template<class GRAPH>
34 struct EliminationTraits
35 {
36 // Template for deriving:
37 // typedef MyFactor FactorType; ///< Type of factors in factor graph (e.g. GaussianFactor)
38 // typedef MyFactorGraphType FactorGraphType; ///< Type of the factor graph (e.g. GaussianFactorGraph)
39 // typedef MyConditional ConditionalType; ///< Type of conditionals from elimination (e.g. GaussianConditional)
40 // typedef MyBayesNet BayesNetType; ///< Type of Bayes net from sequential elimination (e.g. GaussianBayesNet)
41 // typedef MyEliminationTree EliminationTreeType; ///< Type of elimination tree (e.g. GaussianEliminationTree)
42 // typedef MyBayesTree BayesTreeType; ///< Type of Bayes tree (e.g. GaussianBayesTree)
43 // typedef MyJunctionTree JunctionTreeType; ///< Type of Junction tree (e.g. GaussianJunctionTree)
44 // static pair<shared_ptr<ConditionalType>, shared_ptr<FactorType>
45 // DefaultEliminate(
46 // const MyFactorGraph& factors, const Ordering& keys); ///< The default dense elimination function
47 };
48
49
50 /** EliminateableFactorGraph is a base class for factor graphs that contains elimination
51 * algorithms. Any factor graph holding eliminateable factors can derive from this class to
52 * expose functions for computing marginals, conditional marginals, doing multifrontal and
53 * sequential elimination, etc. */
54 template<class FACTOR_GRAPH>
55 class EliminateableFactorGraph
56 {
57 private:
58 typedef EliminateableFactorGraph<FACTOR_GRAPH> This; ///< Typedef to this class.
59 typedef FACTOR_GRAPH FactorGraphType; ///< Typedef to factor graph type
60 // Base factor type stored in this graph (private because derived classes will get this from
61 // their FactorGraph base class)
62 typedef typename EliminationTraits<FactorGraphType>::FactorType _FactorType;
63
64 public:
65 /// Typedef to the specific EliminationTraits for this graph
66 typedef EliminationTraits<FactorGraphType> EliminationTraitsType;
67
68 /// Conditional type stored in the Bayes net produced by elimination
69 typedef typename EliminationTraitsType::ConditionalType ConditionalType;
70
71 /// Bayes net type produced by sequential elimination
72 typedef typename EliminationTraitsType::BayesNetType BayesNetType;
73
74 /// Elimination tree type that can do sequential elimination of this graph
75 typedef typename EliminationTraitsType::EliminationTreeType EliminationTreeType;
76
77 /// Bayes tree type produced by multifrontal elimination
78 typedef typename EliminationTraitsType::BayesTreeType BayesTreeType;
79
80 /// Junction tree type that can do multifrontal elimination of this graph
81 typedef typename EliminationTraitsType::JunctionTreeType JunctionTreeType;
82
83 /// The pair of conditional and remaining factor produced by a single dense elimination step on
84 /// a subgraph.
85 typedef std::pair<std::shared_ptr<ConditionalType>, std::shared_ptr<_FactorType> > EliminationResult;
86
87 /// The function type that does a single dense elimination step on a subgraph.
88 typedef std::function<EliminationResult(const FactorGraphType&, const Ordering&)> Eliminate;
89
90 /// Typedef for an optional variable index as an argument to elimination functions
91 /// It is an optional to a constant reference
92 typedef std::optional<std::reference_wrapper<const VariableIndex>> OptionalVariableIndex;
93
94 /// Typedef for an optional ordering type
95 typedef std::optional<Ordering::OrderingType> OptionalOrderingType;
96
97 /** Do sequential elimination of all variables to produce a Bayes net. If an ordering is not
98 * provided, the ordering provided by COLAMD will be used.
99 *
100 * <b> Example - Full Cholesky elimination in COLAMD order: </b>
101 * \code
102 * std::shared_ptr<GaussianBayesNet> result = graph.eliminateSequential(EliminateCholesky);
103 * \endcode
104 *
105 * <b> Example - METIS ordering for elimination
106 * \code
107 * std::shared_ptr<GaussianBayesNet> result = graph.eliminateSequential(OrderingType::METIS);
108 * \endcode
109 *
110 * <b> Example - Reusing an existing VariableIndex to improve performance, and using COLAMD ordering: </b>
111 * \code
112 * VariableIndex varIndex(graph); // Build variable index
113 * Data data = otherFunctionUsingVariableIndex(graph, varIndex); // Other code that uses variable index
114 * std::shared_ptr<GaussianBayesNet> result = graph.eliminateSequential(EliminateQR, varIndex, std::nullopt);
115 * \endcode
116 * */
117 std::shared_ptr<BayesNetType> eliminateSequential(
118 OptionalOrderingType orderingType = {},
119 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
120 OptionalVariableIndex variableIndex = {}) const;
121
122 /** Do sequential elimination of all variables to produce a Bayes net.
123 *
124 * <b> Example - Full QR elimination in specified order:
125 * \code
126 * std::shared_ptr<GaussianBayesNet> result = graph.eliminateSequential(myOrdering, EliminateQR);
127 * \endcode
128 *
129 * <b> Example - Reusing an existing VariableIndex to improve performance: </b>
130 * \code
131 * VariableIndex varIndex(graph); // Build variable index
132 * Data data = otherFunctionUsingVariableIndex(graph, varIndex); // Other code that uses variable index
133 * std::shared_ptr<GaussianBayesNet> result = graph.eliminateSequential(myOrdering, EliminateQR, varIndex, std::nullopt);
134 * \endcode
135 * */
136 std::shared_ptr<BayesNetType> eliminateSequential(
137 const Ordering& ordering,
138 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
139 OptionalVariableIndex variableIndex = {}) const;
140
141 /** Do multifrontal elimination of all variables to produce a Bayes tree. If an ordering is not
142 * provided, the ordering will be computed using either COLAMD or METIS, depending on
143 * the parameter orderingType (Ordering::COLAMD or Ordering::METIS)
144 *
145 * <b> Example - Full Cholesky elimination in COLAMD order: </b>
146 * \code
147 * std::shared_ptr<GaussianBayesTree> result = graph.eliminateMultifrontal(EliminateCholesky);
148 * \endcode
149 *
150 * <b> Example - Reusing an existing VariableIndex to improve performance, and using COLAMD ordering: </b>
151 * \code
152 * VariableIndex varIndex(graph); // Build variable index
153 * Data data = otherFunctionUsingVariableIndex(graph, varIndex); // Other code that uses variable index
154 * std::shared_ptr<GaussianBayesTree> result = graph.eliminateMultifrontal(EliminateQR, {}, varIndex);
155 * \endcode
156 * */
157 std::shared_ptr<BayesTreeType> eliminateMultifrontal(
158 OptionalOrderingType orderingType = {},
159 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
160 OptionalVariableIndex variableIndex = {}) const;
161
162 /** Do multifrontal elimination of all variables to produce a Bayes tree. If an ordering is not
163 * provided, the ordering will be computed using either COLAMD or METIS, depending on
164 * the parameter orderingType (Ordering::COLAMD or Ordering::METIS)
165 *
166 * <b> Example - Full QR elimination in specified order:
167 * \code
168 * std::shared_ptr<GaussianBayesTree> result = graph.eliminateMultifrontal(EliminateQR, myOrdering);
169 * \endcode
170 * */
171 std::shared_ptr<BayesTreeType> eliminateMultifrontal(
172 const Ordering& ordering,
173 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
174 OptionalVariableIndex variableIndex = {}) const;
175
176 /** Do sequential elimination of some variables, in \c ordering provided, to produce a Bayes net
177 * and a remaining factor graph. This computes the factorization \f$ p(X) = p(A|B) p(B) \f$,
178 * where \f$ A = \f$ \c variables, \f$ X \f$ is all the variables in the factor graph, and \f$
179 * B = X\backslash A \f$. */
180 std::pair<std::shared_ptr<BayesNetType>, std::shared_ptr<FactorGraphType> >
181 eliminatePartialSequential(
182 const Ordering& ordering,
183 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
184 OptionalVariableIndex variableIndex = {}) const;
185
186 /** Do sequential elimination of the given \c variables in an ordering computed by COLAMD to
187 * produce a Bayes net and a remaining factor graph. This computes the factorization \f$ p(X)
188 * = p(A|B) p(B) \f$, where \f$ A = \f$ \c variables, \f$ X \f$ is all the variables in the
189 * factor graph, and \f$ B = X\backslash A \f$. */
190 std::pair<std::shared_ptr<BayesNetType>, std::shared_ptr<FactorGraphType> >
191 eliminatePartialSequential(
192 const KeyVector& variables,
193 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
194 OptionalVariableIndex variableIndex = {}) const;
195
196 /** Do multifrontal elimination of some variables, in \c ordering provided, to produce a Bayes
197 * tree and a remaining factor graph. This computes the factorization \f$ p(X) = p(A|B) p(B)
198 * \f$, where \f$ A = \f$ \c variables, \f$ X \f$ is all the variables in the factor graph, and
199 * \f$ B = X\backslash A \f$. */
200 std::pair<std::shared_ptr<BayesTreeType>, std::shared_ptr<FactorGraphType> >
201 eliminatePartialMultifrontal(
202 const Ordering& ordering,
203 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
204 OptionalVariableIndex variableIndex = {}) const;
205
206 /** Do multifrontal elimination of the given \c variables in an ordering computed by COLAMD to
207 * produce a Bayes tree and a remaining factor graph. This computes the factorization \f$ p(X)
208 * = p(A|B) p(B) \f$, where \f$ A = \f$ \c variables, \f$ X \f$ is all the variables in the
209 * factor graph, and \f$ B = X\backslash A \f$. */
210 std::pair<std::shared_ptr<BayesTreeType>, std::shared_ptr<FactorGraphType> >
211 eliminatePartialMultifrontal(
212 const KeyVector& variables,
213 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
214 OptionalVariableIndex variableIndex = {}) const;
215
216 /** Compute the marginal of the requested variables and return the result as a Bayes net. Uses
217 * COLAMD marginalization ordering by default
218 * @param variables Determines the *ordered* variables whose marginal to compute,
219 * will be ordered in the returned BayesNet as specified.
220 * @param function Optional dense elimination function.
221 * @param variableIndex Optional pre-computed VariableIndex for the factor graph, if not
222 * provided one will be computed.
223 */
224 std::shared_ptr<BayesNetType> marginalMultifrontalBayesNet(
225 const Ordering& variables,
226 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
227 OptionalVariableIndex variableIndex = {}) const;
228
229 /** Compute the marginal of the requested variables and return the result as a Bayes net. Uses
230 * COLAMD marginalization ordering by default
231 * @param variables Determines the variables whose marginal to compute, will be ordered
232 * using COLAMD; use `Ordering(variables)` to specify the variable ordering.
233 * @param function Optional dense elimination function.
234 * @param variableIndex Optional pre-computed VariableIndex for the factor graph, if not
235 * provided one will be computed.
236 */
237 std::shared_ptr<BayesNetType> marginalMultifrontalBayesNet(
238 const KeyVector& variables,
239 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
240 OptionalVariableIndex variableIndex = {}) const;
241
242 /** Compute the marginal of the requested variables and return the result as a Bayes net.
243 * @param variables Determines the *ordered* variables whose marginal to compute,
244 * will be ordered in the returned BayesNet as specified.
245 * @param marginalizedVariableOrdering Ordering for the variables being marginalized out,
246 * i.e. all variables not in \c variables.
247 * @param function Optional dense elimination function.
248 * @param variableIndex Optional pre-computed VariableIndex for the factor graph, if not
249 * provided one will be computed.
250 */
251 std::shared_ptr<BayesNetType> marginalMultifrontalBayesNet(
252 const Ordering& variables,
253 const Ordering& marginalizedVariableOrdering,
254 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
255 OptionalVariableIndex variableIndex = {}) const;
256
257 /** Compute the marginal of the requested variables and return the result as a Bayes net.
258 * @param variables Determines the variables whose marginal to compute, will be ordered
259 * using COLAMD; use `Ordering(variables)` to specify the variable ordering.
260 * @param marginalizedVariableOrdering Ordering for the variables being marginalized out,
261 * i.e. all variables not in \c variables.
262 * @param function Optional dense elimination function.
263 * @param variableIndex Optional pre-computed VariableIndex for the factor graph, if not
264 * provided one will be computed.
265 */
266 std::shared_ptr<BayesNetType> marginalMultifrontalBayesNet(
267 const KeyVector& variables,
268 const Ordering& marginalizedVariableOrdering,
269 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
270 OptionalVariableIndex variableIndex = {}) const;
271
272 /** Compute the marginal of the requested variables and return the result as a Bayes tree. Uses
273 * COLAMD marginalization order by default
274 * @param variables Determines the *ordered* variables whose marginal to compute,
275 * will be ordered in the returned BayesNet as specified.
276 * @param function Optional dense elimination function..
277 * @param variableIndex Optional pre-computed VariableIndex for the factor graph, if not
278 * provided one will be computed. */
279 std::shared_ptr<BayesTreeType> marginalMultifrontalBayesTree(
280 const Ordering& variables,
281 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
282 OptionalVariableIndex variableIndex = {}) const;
283
284 /** Compute the marginal of the requested variables and return the result as a Bayes tree. Uses
285 * COLAMD marginalization order by default
286 * @param variables Determines the variables whose marginal to compute, will be ordered
287 * using COLAMD; use `Ordering(variables)` to specify the variable ordering.
288 * @param function Optional dense elimination function..
289 * @param variableIndex Optional pre-computed VariableIndex for the factor graph, if not
290 * provided one will be computed. */
291 std::shared_ptr<BayesTreeType> marginalMultifrontalBayesTree(
292 const KeyVector& variables,
293 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
294 OptionalVariableIndex variableIndex = {}) const;
295
296 /** Compute the marginal of the requested variables and return the result as a Bayes tree.
297 * @param variables Determines the *ordered* variables whose marginal to compute,
298 * will be ordered in the returned BayesNet as specified.
299 * @param marginalizedVariableOrdering Ordering for the variables being marginalized out,
300 * i.e. all variables not in \c variables.
301 * @param function Optional dense elimination function..
302 * @param variableIndex Optional pre-computed VariableIndex for the factor graph, if not
303 * provided one will be computed. */
304 std::shared_ptr<BayesTreeType> marginalMultifrontalBayesTree(
305 const Ordering& variables,
306 const Ordering& marginalizedVariableOrdering,
307 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
308 OptionalVariableIndex variableIndex = {}) const;
309
310 /** Compute the marginal of the requested variables and return the result as a Bayes tree.
311 * @param variables Determines the variables whose marginal to compute, will be ordered
312 * using COLAMD; use `Ordering(variables)` to specify the variable ordering.
313 * @param marginalizedVariableOrdering Ordering for the variables being marginalized out,
314 * i.e. all variables not in \c variables.
315 * @param function Optional dense elimination function..
316 * @param variableIndex Optional pre-computed VariableIndex for the factor graph, if not
317 * provided one will be computed. */
318 std::shared_ptr<BayesTreeType> marginalMultifrontalBayesTree(
319 const KeyVector& variables,
320 const Ordering& marginalizedVariableOrdering,
321 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
322 OptionalVariableIndex variableIndex = {}) const;
323
324 /** Compute the marginal factor graph of the requested variables. */
325 std::shared_ptr<FactorGraphType> marginal(
326 const KeyVector& variables,
327 const Eliminate& function = EliminationTraitsType::DefaultEliminate,
328 OptionalVariableIndex variableIndex = {}) const;
329
330 private:
331
332 // Access the derived factor graph class
333 const FactorGraphType& asDerived() const { return static_cast<const FactorGraphType&>(*this); }
334
335 // Access the derived factor graph class
336 FactorGraphType& asDerived() { return static_cast<FactorGraphType&>(*this); }
337 };
338
339}
340