view toolboxes/FullBNT-1.0.7/graph/triangulate_2Dlattice_demo.m @ 0:e9a9cd732c1e tip

first hg version after svn

% 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)