1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
% Consider a 3x3 lattice with 4-nearest neighbor connectivity
% 1 - 2 - 3
% | | |
% 4 - 5 - 6
% | | |
% 7 - 8 - 9
N = 3;
G = mk_2D_lattice(N,N,4);
G0 = G;
% Now add in the diagonal edges
if 0
% 1 - 2 - 3
% | x | x |
% 4 - 5 - 6
% | x | x |
% 7 - 8 - 9
G(1,5)=1; G(5,1)=1;
G(2,6)=1; G(6,2)=1;
G(4,2)=1; G(2,4)=1;
G(5,3)=1; G(3,5)=1;
G(4,8)=1; G(8,4)=1;
G(5,9)=1; G(9,5)=1;
G(7,5)=1; G(5,7)=1;
G(8,6)=1; G(6,8)=1;
end
% 1 - 2 - 3
% | / | \ |
% 4 - 5 - 6
% | \ | / |
% 7 - 8 - 9
G(2,6)=1; G(6,2)=1;
G(4,2)=1; G(2,4)=1;
G(4,8)=1; G(8,4)=1;
G(8,6)=1; G(6,8)=1;
% Is this a chordal (triangulated) graph? No!
assert(~check_triangulated(G))
% The reason is that there is a chordless cycle around the outside nodes.
% To see this, imagine "picking up" node 5, leaving the rest on the plane
% (like a hoop skirt, or a tent), as shown below
% 1 - 2 - 3
% | / \ |
% 4 6
% | \ / |
% 7 - 8 - 9
% However, if we add in the 4-6 arc, it will be chordal.
G2 = G;
G2(4,6)=1; G2(6,4)=1;
assert(check_triangulated(G2))
% Or we can add in the 2-8 arc
G2 = G;
G2(2,8)=1; G2(8,2)=1;
assert(check_triangulated(G2))
if 0
% 4x4 lattice with cross arcs
N=4;G0 = mk_2D_lattice(N,N,4);
vs = [1 6; 2 5; 2 7; 3 6; 3 8; 4 7; ...
5 10; 6 9; 6 11; 7 10; 7 12; 8 11;...
9 14; 10 13; 10 15; 11 14; 11 16; 12 15];
for i=1:size(vs,1)
u = vs(i,1); v= vs(i,2);
G0(u,v) = 1; G0(v,u) = 1;
end
end
% Here is how we can discover which edges to fill in automatically
% (although possibly sub-optimally)
weights = 2*ones(1,N*N); % all nodes are binar
% fill-ins = 2-4, 2-6, 4-8, 6-8 and 4-6
% cliques = 124, etc and 2456 4568
greedy_order = best_first_elim_order(G0, weights);
[GT, cliques, fill_ins] = triangulate(G0, greedy_order)
assert(check_triangulated(GT))
greedy_order = best_first_elim_order(G, weights);
[GT, cliques, fill_ins] = triangulate(G, greedy_order)
assert(check_triangulated(GT))
% fill-ins = [4 6]
% Cliques are the overlapping squares [1,2,4,5], [2 3 5 6], [4 5 7 8], [5 6 8 9]
% and the following caused by the fill-in: [2 4 5 6], [4 5 6 8]
% Connect the maximal cliques of the triangulate graph into a junction tree
[jtree, root, B, clq_weights] = cliques_to_jtree(cliques, weights);
% In this case, all cliques have weight 2^4 = 16
% Now consider size of max clique as a function of grid size
% Note: this is not necessarily the optimal triangulation
% N 5 10 15 16 17 18
% m 6 15 23 25 28 28
Ns = [5 10 15 16 17 18];
for i=1:length(Ns)
N = Ns(i)
G = mk_2D_lattice(N,N,4);
weights = 2*ones(1,N*N); % all nodes are binary
greedy_order = best_first_elim_order(G, weights); % slow!
[GT, cliques, fill_ins] = triangulate(G, greedy_order);
%assert(check_triangulated(GT))
[jtree, root, B, clq_weights] = cliques_to_jtree(cliques, weights);
m(i) = log2(max(clq_weights));
end
% plot distribution of clique sizes for fixed N
for c=1:length(cliques)
l(c) = length(cliques{c});
end
hist(l)
|
