|
wolffd@0
|
1 function [jtree, root, cliques, B, w, elim_order, moral_edges, fill_in_edges, strong] = ...
|
|
wolffd@0
|
2 dag_to_jtree(dag, node_sizes, partial_order, stages, clusters)
|
|
wolffd@0
|
3 % DAG_TO_JTREE Moralize and triangulate a DAG, and make a junction tree from its cliques.
|
|
wolffd@0
|
4 % [jtree, root, cliques, B, w, elim_order, moral_edges, fill_in_edges, strong] = ...
|
|
wolffd@0
|
5 % dag_to_jtree(dag, node_sizes, partial_order, stages, clusters)
|
|
wolffd@0
|
6 %
|
|
wolffd@0
|
7 % Input:
|
|
wolffd@0
|
8 % dag(i,j)
|
|
wolffd@0
|
9 % jtree(i,j) = 1 iff there is an arc between clique i and clique j
|
|
wolffd@0
|
10 % root = the root clique
|
|
wolffd@0
|
11 % cliques{i} = the nodes in clique i
|
|
wolffd@0
|
12 % B(i,j) = 1 iff node j occurs in clique i
|
|
wolffd@0
|
13 % w(i) = weight of clique i
|
|
wolffd@0
|
14
|
|
wolffd@0
|
15 N = length(bnet.dag);
|
|
wolffd@0
|
16 if nargin < 2, obs_nodes = []; end
|
|
wolffd@0
|
17 if nargin < 3, stages = { 1:N }; end
|
|
wolffd@0
|
18 if nargin < 4, clusters = {}; end
|
|
wolffd@0
|
19
|
|
wolffd@0
|
20 [MG, moral_edges] = moralize(bnet.dag);
|
|
wolffd@0
|
21
|
|
wolffd@0
|
22 % Add extra arcs between nodes in each cluster to ensure they occur in the same clique
|
|
wolffd@0
|
23 for i=1:length(clusters)
|
|
wolffd@0
|
24 c = clusters{i};
|
|
wolffd@0
|
25 MG(c,c) = 1;
|
|
wolffd@0
|
26 end
|
|
wolffd@0
|
27 MG = setdiag(MG, 0);
|
|
wolffd@0
|
28
|
|
wolffd@0
|
29 % Find an optimal elimination ordering (NP-hard problem!)
|
|
wolffd@0
|
30 ns = bnet.node_sizes(:);
|
|
wolffd@0
|
31 ns(obs_nodes) = 1; % observed nodes have only 1 possible value
|
|
wolffd@0
|
32 partial_order = determine_elim_constraints(bnet, obs_nodes);
|
|
wolffd@0
|
33
|
|
wolffd@0
|
34 if isempty(partial_order)
|
|
wolffd@0
|
35 strong = 0;
|
|
wolffd@0
|
36 elim_order = best_first_elim_order(MG, ns, stages);
|
|
wolffd@0
|
37 else
|
|
wolffd@0
|
38 strong = 1;
|
|
wolffd@0
|
39 elim_order = strong_elim_order(MG, ns, partial_order);
|
|
wolffd@0
|
40 end
|
|
wolffd@0
|
41
|
|
wolffd@0
|
42 [MTG, cliques, fill_in_edges] = triangulate(MG, elim_order);
|
|
wolffd@0
|
43
|
|
wolffd@0
|
44 % Connect the cliques up into a jtree,
|
|
wolffd@0
|
45 [jtree, root, B, w] = cliques_to_jtree(cliques, ns);
|
|
wolffd@0
|
46
|
|
wolffd@0
|
47 if 0
|
|
wolffd@0
|
48 disp('testing dag to jtree');
|
|
wolffd@0
|
49 % Find the cliques containing each node, and check they form a connected subtree
|
|
wolffd@0
|
50 clqs_con_node = cell(1,N);
|
|
wolffd@0
|
51 for i=1:N
|
|
wolffd@0
|
52 clqs_con_node{i} = find(B(:,i))';
|
|
wolffd@0
|
53 end
|
|
wolffd@0
|
54 check_jtree_property(clqs_con_node, jtree);
|
|
wolffd@0
|
55 end
|
