wolffd@0: function [jtree, root, cliques, B, w, elim_order] = graph_to_jtree(MG, ns, partial_order, stages, clusters)
wolffd@0: % GRAPH_TO_JTREE Triangulate a graph and make a junction tree from its cliques.
wolffd@0: % [jtree, root, cliques, B, w, elim_order] = ...
wolffd@0: %    graph_to_jtree(graph, node_sizes, partial_order, stages, clusters)
wolffd@0: %
wolffd@0: % INPUT:
wolffd@0: % graph(i,j) = 1 iff there is an edge between i,j
wolffd@0: % node_weights(i) = num discrete values node i can take on [1 if observed]
wolffd@0: % partial_order = {} if no constraints on elimination ordering
wolffd@0: % stages{i} = nodes that must be eliminated at i'th stage (if porder is empty)
wolffd@0: % clusters{i} = list of nodes that must get connected together in the moral graph
wolffd@0: %
wolffd@0: % OUTPUT:
wolffd@0: % jtree(i,j) = 1 iff there is an arc between clique i and clique j 
wolffd@0: % root = the root clique
wolffd@0: % cliques{i} = the nodes in clique i
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: N = length(MG);
wolffd@0: 
wolffd@0: if nargin >= 5
wolffd@0:   % Add extra arcs between nodes in each cluster to ensure they occur in the same clique
wolffd@0:   for i=1:length(clusters)
wolffd@0:     c = clusters{i};
wolffd@0:     MG(c,c) = 1;
wolffd@0:   end
wolffd@0: end
wolffd@0: MG = setdiag(MG, 0);
wolffd@0: 
wolffd@0: % Find an optimal elimination ordering (NP-hard problem!)
wolffd@0: if nargin < 4
wolffd@0:   stages = {1:N};
wolffd@0: end
wolffd@0: if nargin < 3
wolffd@0:   partial_order = {};
wolffd@0: end
wolffd@0: if isempty(partial_order)
wolffd@0:   strong = 0;
wolffd@0:   elim_order = best_first_elim_order(MG, ns, stages);
wolffd@0: else
wolffd@0:   strong = 1;
wolffd@0:   elim_order = strong_elim_order(MG, ns, partial_order);
wolffd@0: end
wolffd@0: 
wolffd@0: [MTG, cliques, fill_in_edges]  = triangulate(MG, elim_order);
wolffd@0: 
wolffd@0: % Connect the cliques up into a jtree,
wolffd@0: [jtree, root, B, w] = cliques_to_jtree(cliques, ns);
wolffd@0: 
wolffd@0: if 0
wolffd@0:   disp('testing dag to jtree');
wolffd@0:   % Find the cliques containing each node, and check they form a connected subtree
wolffd@0:   clqs_con_node = cell(1,N);
wolffd@0:   for i=1:N
wolffd@0:     clqs_con_node{i} = find(B(:,i))';
wolffd@0:   end
wolffd@0:   check_jtree_property(clqs_con_node, jtree);
wolffd@0: end