|
wolffd@0
|
1 function [jtree, root, cliques, B, w, elim_order] = graph_to_jtree(MG, ns, partial_order, stages, clusters)
|
|
wolffd@0
|
2 % GRAPH_TO_JTREE Triangulate a graph and make a junction tree from its cliques.
|
|
wolffd@0
|
3 % [jtree, root, cliques, B, w, elim_order] = ...
|
|
wolffd@0
|
4 % graph_to_jtree(graph, node_sizes, partial_order, stages, clusters)
|
|
wolffd@0
|
5 %
|
|
wolffd@0
|
6 % INPUT:
|
|
wolffd@0
|
7 % graph(i,j) = 1 iff there is an edge between i,j
|
|
wolffd@0
|
8 % node_weights(i) = num discrete values node i can take on [1 if observed]
|
|
wolffd@0
|
9 % partial_order = {} if no constraints on elimination ordering
|
|
wolffd@0
|
10 % stages{i} = nodes that must be eliminated at i'th stage (if porder is empty)
|
|
wolffd@0
|
11 % clusters{i} = list of nodes that must get connected together in the moral graph
|
|
wolffd@0
|
12 %
|
|
wolffd@0
|
13 % OUTPUT:
|
|
wolffd@0
|
14 % jtree(i,j) = 1 iff there is an arc between clique i and clique j
|
|
wolffd@0
|
15 % root = the root clique
|
|
wolffd@0
|
16 % cliques{i} = the nodes in clique i
|
|
wolffd@0
|
17 % B(i,j) = 1 iff node j occurs in clique i
|
|
wolffd@0
|
18 % w(i) = weight of clique i
|
|
wolffd@0
|
19
|
|
wolffd@0
|
20 N = length(MG);
|
|
wolffd@0
|
21
|
|
wolffd@0
|
22 if nargin >= 5
|
|
wolffd@0
|
23 % Add extra arcs between nodes in each cluster to ensure they occur in the same clique
|
|
wolffd@0
|
24 for i=1:length(clusters)
|
|
wolffd@0
|
25 c = clusters{i};
|
|
wolffd@0
|
26 MG(c,c) = 1;
|
|
wolffd@0
|
27 end
|
|
wolffd@0
|
28 end
|
|
wolffd@0
|
29 MG = setdiag(MG, 0);
|
|
wolffd@0
|
30
|
|
wolffd@0
|
31 % Find an optimal elimination ordering (NP-hard problem!)
|
|
wolffd@0
|
32 if nargin < 4
|
|
wolffd@0
|
33 stages = {1:N};
|
|
wolffd@0
|
34 end
|
|
wolffd@0
|
35 if nargin < 3
|
|
wolffd@0
|
36 partial_order = {};
|
|
wolffd@0
|
37 end
|
|
wolffd@0
|
38 if isempty(partial_order)
|
|
wolffd@0
|
39 strong = 0;
|
|
wolffd@0
|
40 elim_order = best_first_elim_order(MG, ns, stages);
|
|
wolffd@0
|
41 else
|
|
wolffd@0
|
42 strong = 1;
|
|
wolffd@0
|
43 elim_order = strong_elim_order(MG, ns, partial_order);
|
|
wolffd@0
|
44 end
|
|
wolffd@0
|
45
|
|
wolffd@0
|
46 [MTG, cliques, fill_in_edges] = triangulate(MG, elim_order);
|
|
wolffd@0
|
47
|
|
wolffd@0
|
48 % Connect the cliques up into a jtree,
|
|
wolffd@0
|
49 [jtree, root, B, w] = cliques_to_jtree(cliques, ns);
|
|
wolffd@0
|
50
|
|
wolffd@0
|
51 if 0
|
|
wolffd@0
|
52 disp('testing dag to jtree');
|
|
wolffd@0
|
53 % Find the cliques containing each node, and check they form a connected subtree
|
|
wolffd@0
|
54 clqs_con_node = cell(1,N);
|
|
wolffd@0
|
55 for i=1:N
|
|
wolffd@0
|
56 clqs_con_node{i} = find(B(:,i))';
|
|
wolffd@0
|
57 end
|
|
wolffd@0
|
58 check_jtree_property(clqs_con_node, jtree);
|
|
wolffd@0
|
59 end
|
