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