www.pudn.com > ConstrainedEM.zip > net_to_jtree.m

function [jtree, root, cliques, B, w , elim_order ] =net_to_jtree(mnet,k,tree_flag) 
% original is DAG_TO_JTREE of BNT

% NET_TO_JTREE triangulate a graph, and make a junction tree from its cliques.
% [jtree, root, cliques, B, w] = dag_to_jtree(bnet, obs_nodes, stages, clusters)
%
% jtree(i,j) = 1 iff there is an arc between clique i and clique j 
% root = the root clique
% cliques{i} = the nodes in clique i
% B(i,j) = 1 iff node j occurs in clique i
% w(i) = weight of clique i


N = length(mnet);
MG=mnet;
stages = { 1:N };
ns = ones(1,N)*k;

% Find an optimal elimination ordering (NP-hard problem!)
if ~tree_flag
   elim_order = best_first_elim_order(MG, ns, stages);
   
   %disp('elim order');
   %elim_order
   
   [MTG, cliques, fill_in_edges]  = triangulate(MG, elim_order);
   %fill_in_edges
else
   % optimal elimination ordering is easily determined for a tree , and unfortunately
   % isn't found easily by best_first_elim_order
   [stam, stam, elim_order, stam, stam, pred ] = dfs(MG, 1, 0);
   cliques=mat2cell( [elim_order(1:end-1)' , pred(elim_order(1:end-1))'],ones(1,length(elim_order)-1),2);
end

% Connect the cliques up into a jtree,
[jtree, root, B, w] = cliques_to_jtree(cliques, ns);

if 0
  disp('testing dag to jtree');
  % Find the cliques containing each node, and check they form a connected subtree
  clqs_con_node = cell(1,N);
  for i=1:N
    clqs_con_node{i} = find(B(:,i))';
  end
  check_jtree_property(clqs_con_node, jtree);
end