Internals

mutable struct Node{T}

• id::Any

• children::Array{JunctionTrees.Node{T}, 1} where T

• parent::JunctionTrees.Node

Tree node definition intended to be used with AbstractTrees.jl.

_marg(r_vals, ret_vars, Avals, dims) -> Factor

Performance critical code of the factor marginalization operation.

_product(A_vals_new, B_vals_new, C_vars) -> Factor

Performance critical code of the factor product operation.

add_edges!(g, edges)

Construct the edges and store their sepset as an edge property.

add_vertices!(g, bags)

Add a vertex for each bag and initialize its properties.

addchild!(
    id,
    parent::JunctionTrees.Node
) -> JunctionTrees.Node

Add a child node with id id to parent.

addchildren!(ids, parent::JunctionTrees.Node) -> Any

Add several children with with ids ids to parent.

are_connected(g, v1, v2) -> Bool

Return whether vertices v1 and v2 are connected.

assign_factors!(g, factors, root)

Assign each factor to a cluster that covers its variables.

boost_algo(algo::Expr; optimizer) -> Expr

Speed up the sum-product in the algorithm using OMEinsum's contraction routines.

Examples

package_root_dir = pathof(JunctionTrees) |> dirname |> dirname
uai_filepath = joinpath(package_root_dir, "docs", "src", "problems", "paskin", "paskin.uai")
algo = compile_algo(uai_filepath, use_omeinsum = true);
eval(algo)
obsvars, obsvals = Int64[], Int64[]
marginals = run_algo(obsvars, obsvals)

calculate_sepset_key(
    g::MetaGraphs.MetaGraph,
    sepset::Vector{Int64},
    cards
) -> Tuple{Int64, Int64}

Calculate the "key" of sepset based on:

1. Mass: The number of variables in sepset.
2. Cost: The product of the cardinality of each variable in sepset.

The number of variables in the sepset has higher priority than the product of their cardinality. The higher the mass, the lower the key. The lower the cost, the lower the key.

calculate_var_key(
    g::MetaGraphs.MetaGraph,
    v::Int64,
    cards
) -> Tuple{Int64, Int64}

Calculate the "key" of v based on:

1. The number of edges to be added if v's neighbors were to be connected.
2. The weight of v and its neighbors (also known as the induced bag).

The number of edges to be added has more priority than the weight of the induced cluster. The lower the number of edges to be added, the lower the key. The lower the weight, the lower the key.

compile_backward_pass!(g, root) -> Expr

Compile the downstream messages.

compile_bag_potentials(g, factor_eltype) -> Expr

Compile each bag's potential into a Julia expression.

compile_forward_pass!(g, root) -> Expr

Compile the upstream messages.

compile_message_propagation!(g, root) -> Tuple{Expr, Expr}

Compile the forward and backward passes of messages.

compile_normalized_marginals(unnormalized_marginals) -> Expr

Compile the normalized marginal expressions for each variable in the model.

compile_unnormalized_marginals(
    g,
    nvars,
    partial_evaluation
) -> Tuple{Expr, Expr, Expr}

Compile marginalization statements for each variable from a sepset if possible and otherwise from a bag.

connect_bags!(
    td::MetaGraphs.MetaGraph,
    mrf::MetaGraphs.MetaGraph,
    bags::Vector{Vector{Int64}},
    cards
)

Connect the bags such that the running intersection property is satisfied.

construct_mrf_graph(nvars, factors) -> MetaGraphs.MetaGraph

Construct a Markov random field graph with nvars variables and the cliques contained in factors.

construct_td_graph(
    td_filepath::AbstractString
) -> MetaGraphs.MetaGraph{Int64, Float64}

Construct a tree decomposition graph based on td_filepath.

The td_filepath file format is defined in: https://pacechallenge.org/2017/treewidth/.

Example

td_filepath = "../problems/Promedus_26/Promedus_26.td"
td = compile_algo(td_filepath)

construct_td_graph(
    mrf,
    cards
) -> MetaGraphs.MetaGraph{Int64, Float64}

Transform the given Markov random field into a junction tree. This implementation is based on "Inference in Belief Networks: A Procedural Guide" by Cecil Huang and Adnan Darwiche (1996) pg. 235.

convertToAbstractTree!(g, root::JunctionTrees.Node)
convertToAbstractTree!(
    g,
    root::JunctionTrees.Node,
    parent::JunctionTrees.Node
)

Construct a tree decomposition abstract tree based on the graph g using root as the root node.

Example

using Graphs

g = double_binary_tree(3)
root = Node(1)
convertToAbstractTree!(g, root)
print_tree(root)

cost(
    g::MetaGraphs.MetaGraph,
    sepset::Vector{Int64},
    cards
) -> Int64

Compute the product of the cardinalities of bag constituent vars.

count_edges_to_be_added(
    g::MetaGraphs.MetaGraph,
    v::Int64
) -> Int64

Compute the number of edges to be added to the graph if we choose to eliminate this vertex.

Arguments

• g::MetaGraph the graph to consider.
• v::Int64 the vertex to eliminate.

Return

• count::Int64 number of edges to add in the graph g if v is eliminated.

form_bags(g, cards) -> Vector{Vector{Int64}}

Return the maximal cliques of g using the minfill heuristic. The maximal cliques of the triangulated graph correspond to the bags of the junction tree. This implementation is based on: "Inference in Belief Networks: A Procedural Guide" by Cecil Huang and Adnan Darwiche (1996) pg. 235. TODO: See https://matbesancon.xyz/post/2019-05-30-vertex-safe-removal/ to implement this function using a vertex-safe version of Graphs.jl. This would avoid having to bookkeep the node ids in the original graph after it is modified with rev_vertex!.

Bookkepping example for the paskin-example problem:

-----------------------------------------------------------
| var to remove | vertices(g) | int2ext     | ext2int     |
-----------------------------------------------------------
| 6             | 1 2 3 4 5 6 | 1 2 3 4 5 6 | 1 2 3 4 5 6 |
| 4             | 1 2 3 4 5   | 1 2 3 4 5   | 1 2 3 4 5 0 |
| 5             | 1 2 3 4     | 1 2 3 5     | 1 2 3 0 4 0 |
| 2             | 1 2 3       | 1 2 3       | 1 2 3 0 0 0 |
| 1             | 1 2         | 1 3         | 1 0 2 0 0 0 |
| 3             | 1           | 3           | 0 0 1 0 0 0 |
-----------------------------------------------------------

Variables preceded with _ use the internal variable indexation. Those without use the external/original variable indexation.

generate_function_expression(
    function_name,
    sig,
    variables,
    body
) -> Expr

Generate a function expression using Julia's metaprogramming capabilities

Example

function_name = :foo
sig = (Int, Float64, Int32)
variables = [:a, :q, :d]
body = :(a + q * d)

ex = generate_function_expression(function_name, sig, variables, body)

eval(ex)

foo(1, 2.0, Int32(3))

get_induced_bag(g::MetaGraphs.MetaGraph, v::Int64) -> Any

Return the bag induced after removing v, i.e. the set of vars consisting of v and its neighbors.

get_induced_bag_weight(
    g::MetaGraphs.MetaGraph,
    v::Int64,
    cards
) -> Int64

Compute the weight of the bag consisting of v and its neighbors.

get_td_soln(
    td_filepath::AbstractString
) -> Union{Vector{Missing}, Vector{Int64}}

Get the solution arguments of the tree decomposition file passed as argument. This function returns a vector with the solution arguments, which consist of:

1. the number of bags of the tree decomposition
2. the width of the tree decomposition plus one (i.e., the largest bag size)
3. the number of vertices of the original input graph

The tree decomposition file should be defined in the PACE format: https://pacechallenge.org/2017/treewidth/

initialize_td_graph!(
    g,
    factors,
    smart_root_selection
) -> Tuple{JunctionTrees.Node, Expr}

Initialize the td graph by assigning the different factors to one bag that covers its scope.

inject_redus(g, before_pass_pots, obsvars, obsvals) -> Expr

Inject a reduction expression to potentials that contain observed variables.

inject_redus(
    td,
    before_pass_pots,
    before_pass_forward_pass,
    before_pass_backward_pass,
    obsvars,
    obsvals
) -> Tuple{Expr, Expr, Expr}

Inject a reduction expression to potentials that contain observed variables.

inject_redus_in_msgs(
    g,
    before_pass_msgs,
    obsvars,
    obsvals
) -> Expr

Inject a reduction statement for each observed variable. Each reduction takes the observed variable and it's corresponding observed value. The reduction statements are introduced as late as possible, i.e. just before the observed variable is marginalized.

inject_redus_in_pots(
    g,
    before_pass_pots,
    obsvars,
    obsvals
) -> Expr

Inject a reduction statement for observed variables contained inside isolated bags. An isolated bag is a leaf bag connected to the rest of the tree via one empty sepset. Each reduction takes the observed variable and it's corresponding observed value.

is_maximal(candidate_clique, cliques) -> Bool

Return whether clique is maximal in the clique_set

mark_leaves!(g::MetaGraphs.MetaGraph) -> Any

Mark which nodes of g correspond to leaves using a property.

mark_obsbags!(g, obsvars)

Mark which nodes of g have at least one observed variable.

mass(
    g::MetaGraphs.MetaGraph,
    sepset::Vector{Int64}
) -> Int64

Return the number of vars in the sepset.

my_indexin(x, y) -> Any

Optimized version of the function indexin defined in Base.

normalize_messages(
    obsvals,
    pots,
    before_pass_forward_msgs,
    before_pass_backward_msgs,
    operations
) -> Tuple{Expr, Expr}

Normalize messages in the propagation phase that cause an overflow when running the expressions inside operations. Operations can be either sum-prod messages from the propagation phase or edge/bag marginals computations.

partial_eval_analysis!(g)

Analyzes which messages can be computed during the compilation stage in the graph g.

partial_eval_prop_update!(
    g,
    curr_node,
    prev_node,
    obs_bag_var,
    obs_var_marginalized
)

Recursive function that invalidates messages in the graph g that cannot be partially evaluated at compile time. This marking is done using MetaGraphs' properties for each edge in the graph.

partial_evaluation(
    td,
    pots,
    forward_pass,
    backward_pass
) -> Tuple{Expr, Expr}

Partially evaluates messages of the propagation stage that do not depend on online observations.

partially_evaluate(g, before_pass_msgs) -> Expr

Partially evaluate messages that do not depend on observed variables.

preprocess_heap_elements(
    g::MetaGraphs.MetaGraph,
    bag1,
    bag2,
    cards
) -> NamedTuple{(:endpoints, :sepset, :key), _A} where _A<:Tuple{Tuple{Any, Any}, Any, Tuple{Int64, Int64}}

Calculate the key for each element that will be inserted into the binary heap and wraps the edge, its sepset and the key into a tuple.

read_td_file(
    td_filepath::AbstractString
) -> Tuple{Int64, Int64, Int64, Vector{Vector{Int64}}, Vector{Vector{Int64}}}

Parse a tree decomposition instance described the PACE format.

The PACE file format is defined in: https://pacechallenge.org/2017/treewidth/

read_uai_evid_file(
    uai_evid_filepath::AbstractString
) -> Tuple{Vector{Int64}, Vector{Int64}}

Return the observed variables and values in uai_evid_filepath. If the passed file path is an empty string, return empty vectors.

The UAI file formats are defined in: https://personal.utdallas.edu/~vibhav.gogate/uai16-evaluation/uaiformat.html

read_uai_file(
    uai_filepath;
    factor_eltype
) -> Tuple{Int64, Vector{Int64}, Int64, Any}

Parse the problem instance found in uai_filepath defined in the UAI model format.

The UAI file formats are defined in: https://personal.utdallas.edu/~vibhav.gogate/uai16-evaluation/uaiformat.html

read_uai_mar_file(
    uai_mar_filepath::AbstractString;
    factor_eltype
) -> Vector{Vector{Float64}}

Return the marginals of all variables. The order of the variables is the same as in the model

The UAI file formats are defined in: https://personal.utdallas.edu/~vibhav.gogate/uai16-evaluation/uaiformat.html

select_rootnode(
    g;
    smart_root_selection
) -> JunctionTrees.Node

Select and return the root node of g.

weight(g, bag::Vector{Int64}, cards) -> Int64

Compute the product of the cardinalities of bag constituent vars.