BNW using Octave instead of Matlab.

This version of BNW should perform the same as the original version. The only difference is that it uses Octave instead of Matlab when running BayesNet Toolbox during parameter learning.

I am calling this BNW_1.02. It can be accessed at:
compbio.uthsc.edu/BNW_1.02

1 files changed, 131 insertions, 0 deletions

diff --git a/sourcecodes/bnt-master/graph/triangulate_2Dlattice_demo.m b/sourcecodes/bnt-master/graph/triangulate_2Dlattice_demo.m
new file mode 100644
index 00000000..12ad1312
--- /dev/null
+++ b/sourcecodes/bnt-master/graph/triangulate_2Dlattice_demo.m
@@ -0,0 +1,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)