wolffd@0: function [jtree, root, B, w] = cliques_to_jtree(cliques, ns)
wolffd@0: % MK_JTREE Make an optimal junction tree.
wolffd@0: % [jtree, root, B, w] = mk_jtree(cliques, ns)
wolffd@0: % 
wolffd@0: % A junction tree is a tree that satisfies the jtree property, which says:
wolffd@0: % for each pair of cliques U,V with intersection S, all cliques on the path between U and V
wolffd@0: % contain S. (This ensures that local propagation leads to global consistency.)
wolffd@0: %
wolffd@0: % We can create a junction tree by computing the maximal spanning tree of the junction graph.
wolffd@0: % (The junction graph connects all cliques, and the weight of an edge (i,j) is
wolffd@0: % |C(i) intersect C(j)|, where C(i) is the i'th clique.)
wolffd@0: %
wolffd@0: % The best jtree is the maximal spanning tree which minimizes the sum of the costs on each edge,
wolffd@0: % where cost(i,j) = w(C(i)) + w(C(j)), and w(C) is the weight of clique C,
wolffd@0: % which is the total number of values C can take on.
wolffd@0: %
wolffd@0: % For details, see
wolffd@0: %  - Jensen and Jensen, "Optimal Junction Trees", UAI 94.
wolffd@0: %
wolffd@0: % Input:
wolffd@0: %  cliques{i} = nodes in clique i
wolffd@0: %  ns(i) = number of values node i can take on
wolffd@0: % Output:
wolffd@0: %  jtree(i,j) = 1 iff cliques i and j aer connected
wolffd@0: %  root = the clique that should be used as root
wolffd@0: %  B(i,j) = 1 iff node j occurs in clique i
wolffd@0: %  w(i) = weight of clique i
wolffd@0: 
wolffd@0: 
wolffd@0: 
wolffd@0: num_cliques = length(cliques);
wolffd@0: w = zeros(num_cliques, 1); 
wolffd@0: B = sparse(num_cliques, 1);
wolffd@0: for i=1:num_cliques
wolffd@0:   B(i, cliques{i}) = 1;
wolffd@0:   w(i) = prod(ns(cliques{i}));
wolffd@0: end
wolffd@0: 
wolffd@0: 
wolffd@0: % C1(i,j) = length(intersect(cliques{i}, cliques{j})); 
wolffd@0: % The length of the intersection of two sets is the dot product of their bit vector representation.
wolffd@0: C1 = B*B';
wolffd@0: C1 = setdiag(C1, 0);
wolffd@0: 
wolffd@0: % C2(i,j) = w(i) + w(j)
wolffd@0: num_cliques = length(w);
wolffd@0: W = repmat(w, 1, num_cliques);
wolffd@0: C2 = W + W';
wolffd@0: C2 = setdiag(C2, 0);
wolffd@0: 
wolffd@0: jtree = sparse(minimum_spanning_tree(-C1, C2)); % Using -C1 gives *maximum* spanning tree
wolffd@0: 
wolffd@0: % The root is arbitrary, but since the first pass is towards the root,
wolffd@0: % we would like this to correspond to going forward in time in a DBN.
wolffd@0: root = num_cliques;
wolffd@0: 
wolffd@0: