wolffd@0: % Consider a 3x3 lattice with 4-nearest neighbor connectivity
wolffd@0: 
wolffd@0: % 1 - 2 - 3
wolffd@0: % |   |   |
wolffd@0: % 4 - 5 - 6
wolffd@0: % |   |   |
wolffd@0: % 7 - 8 - 9
wolffd@0: 
wolffd@0: N = 3;
wolffd@0: G = mk_2D_lattice(N,N,4);
wolffd@0: G0 = G;
wolffd@0: 
wolffd@0: % Now add in the diagonal edges
wolffd@0: 
wolffd@0: if 0
wolffd@0: % 1 - 2 - 3
wolffd@0: % | x | x |
wolffd@0: % 4 - 5 - 6
wolffd@0: % | x | x |
wolffd@0: % 7 - 8 - 9
wolffd@0: 
wolffd@0: G(1,5)=1; G(5,1)=1;
wolffd@0: G(2,6)=1; G(6,2)=1;
wolffd@0: G(4,2)=1; G(2,4)=1;
wolffd@0: G(5,3)=1; G(3,5)=1;
wolffd@0: 
wolffd@0: G(4,8)=1; G(8,4)=1;
wolffd@0: G(5,9)=1; G(9,5)=1;
wolffd@0: G(7,5)=1; G(5,7)=1;
wolffd@0: G(8,6)=1; G(6,8)=1;
wolffd@0: end
wolffd@0: 
wolffd@0: % 1 - 2 - 3
wolffd@0: % | / | \ |
wolffd@0: % 4 - 5 - 6
wolffd@0: % | \ | / |
wolffd@0: % 7 - 8 - 9
wolffd@0: 
wolffd@0: G(2,6)=1; G(6,2)=1;
wolffd@0: G(4,2)=1; G(2,4)=1;
wolffd@0: G(4,8)=1; G(8,4)=1;
wolffd@0: G(8,6)=1; G(6,8)=1;
wolffd@0: 
wolffd@0: % Is this a chordal (triangulated) graph? No!
wolffd@0: 
wolffd@0: assert(~check_triangulated(G))
wolffd@0: 
wolffd@0: % The reason is that there is a chordless cycle around the outside nodes.
wolffd@0: % To see this, imagine "picking up" node 5, leaving the rest on the plane
wolffd@0: % (like a hoop skirt, or a tent), as shown below
wolffd@0: 
wolffd@0: % 1 - 2 - 3
wolffd@0: % | /   \ |
wolffd@0: % 4       6
wolffd@0: % | \   / |
wolffd@0: % 7 - 8 - 9
wolffd@0: 
wolffd@0: 
wolffd@0: % However, if we add in the 4-6 arc, it will be chordal.
wolffd@0: 
wolffd@0: G2 = G;
wolffd@0: G2(4,6)=1; G2(6,4)=1;
wolffd@0: assert(check_triangulated(G2))
wolffd@0: 
wolffd@0: % Or we can add in the 2-8 arc
wolffd@0: G2 = G;
wolffd@0: G2(2,8)=1; G2(8,2)=1;
wolffd@0: assert(check_triangulated(G2))
wolffd@0: 
wolffd@0: 
wolffd@0: if 0
wolffd@0: % 4x4 lattice with cross arcs
wolffd@0: N=4;G0 = mk_2D_lattice(N,N,4);
wolffd@0: vs = [1 6;  2 5;   2 7;   3 6;   3 8;   4 7; ...
wolffd@0:       5 10; 6 9;   6 11;  7 10;  7 12;  8 11;...
wolffd@0:       9 14; 10 13; 10 15; 11 14; 11 16; 12 15];
wolffd@0: for i=1:size(vs,1)
wolffd@0:   u = vs(i,1); v= vs(i,2);
wolffd@0:   G0(u,v) = 1; G0(v,u) = 1;
wolffd@0: end
wolffd@0: end
wolffd@0: 
wolffd@0: % Here is how we can discover which edges to fill in automatically 
wolffd@0: % (although possibly sub-optimally)
wolffd@0: weights = 2*ones(1,N*N); % all nodes are binar
wolffd@0: 
wolffd@0: % fill-ins = 2-4, 2-6,  4-8, 6-8 and 4-6
wolffd@0: % cliques = 124, etc  and 2456  4568
wolffd@0: greedy_order = best_first_elim_order(G0, weights);
wolffd@0: [GT, cliques, fill_ins] = triangulate(G0, greedy_order)
wolffd@0: assert(check_triangulated(GT))
wolffd@0: 
wolffd@0: 
wolffd@0: 
wolffd@0: greedy_order = best_first_elim_order(G, weights);
wolffd@0: [GT, cliques, fill_ins] = triangulate(G, greedy_order)
wolffd@0: assert(check_triangulated(GT))
wolffd@0: 
wolffd@0: % fill-ins = [4 6]
wolffd@0: 
wolffd@0: % Cliques are the overlapping squares  [1,2,4,5], [2 3 5 6], [4 5 7 8], [5 6 8 9]
wolffd@0: % and the following caused by the fill-in: [2 4 5 6], [4 5 6 8]
wolffd@0: 
wolffd@0: % Connect the maximal cliques of the triangulate graph into a junction tree
wolffd@0: [jtree, root, B, clq_weights] = cliques_to_jtree(cliques, weights);
wolffd@0: 
wolffd@0: % In this case, all cliques have weight 2^4 = 16
wolffd@0: 
wolffd@0: 
wolffd@0: % Now consider size of max clique as a function of grid size
wolffd@0: % Note: this is not necessarily the optimal triangulation
wolffd@0: 
wolffd@0: % N  5  10 15 16 17 18
wolffd@0: % m  6  15 23 25 28 28
wolffd@0: Ns = [5 10 15 16 17 18]; 
wolffd@0: for i=1:length(Ns)
wolffd@0:   N = Ns(i)
wolffd@0:   G = mk_2D_lattice(N,N,4);
wolffd@0:   weights = 2*ones(1,N*N); % all nodes are binary
wolffd@0:   greedy_order = best_first_elim_order(G, weights); % slow!
wolffd@0:   [GT, cliques, fill_ins] = triangulate(G, greedy_order);
wolffd@0:   %assert(check_triangulated(GT))
wolffd@0:   [jtree, root, B, clq_weights] = cliques_to_jtree(cliques, weights);
wolffd@0:   m(i) = log2(max(clq_weights));
wolffd@0: end
wolffd@0: 
wolffd@0: % plot distribution of clique sizes for fixed N
wolffd@0: for c=1:length(cliques)
wolffd@0:   l(c) = length(cliques{c});
wolffd@0: end
wolffd@0: hist(l)