A DiscreteEliminationTree is an internal data structure used inside elimination algorithms. It records the dependency structure induced by eliminating a discrete factor graph in a chosen order, and it can be used to construct a junction tree.
import gtsam
import numpy as np
from gtsam.symbol_shorthand import M, X
from IPython.display import Markdown, displayConstructing an elimination tree¶
Create the factor graph first, then provide an explicit Ordering. Variables appearing earlier in the ordering are eliminated earlier, which determines both the parent relationships and the size of intermediate factors.
A = (gtsam.symbol("A", 0), 2)
B = (gtsam.symbol("B", 0), 2)
C = (gtsam.symbol("C", 0), 2)
graph = gtsam.DiscreteFactorGraph()
graph.add(A, "0.6 0.4")
graph.add([B, A], "3 1 1 3")
graph.add([C, B], "4 1 1 4")
ordering = gtsam.Ordering()
for key in (A[0], B[0], C[0]):
ordering.push_back(key)
elimination_tree = gtsam.DiscreteEliminationTree(graph, ordering)
elimination_tree.print("A-B-C elimination tree")Important operations¶
The constructor also accepts a precomputed VariableIndex when an application already maintains graph incidence information. print() is the main inspection tool, and equals() is useful in tests that compare two orderings or construction paths. The tree deliberately does not perform inference itself; pass it to DiscreteJunctionTree or DiscreteSearch for downstream algorithms.
same_tree = gtsam.DiscreteEliminationTree(graph, ordering)
print("same structure:", elimination_tree.equals(same_tree, 1e-9))See also¶
DiscreteJunctionTreeclusters this tree for multifrontal inference.DiscreteSearchuses it for ranked assignments.
Source¶
AI assistance caveat¶
AI was used to help draft this documentation, and inaccuracies could be present.