DiscreteJunctionTree

A junction tree is an internal data structure used during multifrontal elimination. DiscreteJunctionTree clusters an elimination tree into a forest of cliques suitable for multifrontal discrete inference. Python also exposes its nested cluster type as DiscreteCluster for inspecting frontal keys, attached factors, and child clusters.

Authors: Frank Dellaert, et al. (see THANKS for the full author list)

See LICENSE for the license information

try:
    import google.colab
    %pip install --quiet gtsam-develop
except ImportError:
    pass

import gtsam
import numpy as np
from gtsam.symbol_shorthand import M, X
from IPython.display import Markdown, display

From factor graph to junction tree¶

The junction tree is constructed from a DiscreteEliminationTree, so the graph and variable ordering remain explicit.

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)
junction_tree = gtsam.DiscreteJunctionTree(elimination_tree)
print("root clusters:", junction_tree.nrRoots())

`DiscreteJunctionTree`¶

nrRoots() reports the number of connected components. Indexing the tree selects a root DiscreteCluster, while print() renders the complete cluster hierarchy. A disconnected factor graph can therefore produce more than one root.

junction_tree.print("Junction tree")
root = junction_tree[0]
print("children below the root:", root.nrChildren())

`DiscreteCluster`¶

Each cluster exposes orderedFrontalKeys, the factors assigned to the clique, indexing for child clusters, nrChildren(), and print(). Clusters are obtained from a junction tree; they are not intended to be assembled independently in Python.

frontals = [
    gtsam.DefaultKeyFormatter(root.orderedFrontalKeys.at(i))
    for i in range(root.orderedFrontalKeys.size())
]
print("frontal keys:", frontals)
print("factors assigned to root:", root.factors.size())

Source¶

DiscreteJunctionTree.h

AI assistance caveat¶

AI was used to help draft this documentation, and inaccuracies could be present.