Mercurial > hg > camir-aes2014

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

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