From 8070dc963753142bb86c4ed698d91fd623ed28e7 Mon Sep 17 00:00:00 2001 From: ziejd2 Date: Thu, 28 Sep 2017 15:04:40 -0500 Subject: 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 --- sourcecodes/bnt-master/graph/Old/CVS/Entries | 6 + sourcecodes/bnt-master/graph/Old/CVS/Repository | 1 + sourcecodes/bnt-master/graph/Old/CVS/Root | 1 + .../bnt-master/graph/Old/best_first_elim_order.m | 64 +++++++++++ sourcecodes/bnt-master/graph/Old/dag_to_jtree.m | 55 ++++++++++ sourcecodes/bnt-master/graph/Old/dfs.m | 84 ++++++++++++++ sourcecodes/bnt-master/graph/Old/dsep_test.m | 15 +++ .../bnt-master/graph/Old/mk_2D_lattice_slow.m | 121 +++++++++++++++++++++ 8 files changed, 347 insertions(+) create mode 100644 sourcecodes/bnt-master/graph/Old/CVS/Entries create mode 100644 sourcecodes/bnt-master/graph/Old/CVS/Repository create mode 100644 sourcecodes/bnt-master/graph/Old/CVS/Root create mode 100644 sourcecodes/bnt-master/graph/Old/best_first_elim_order.m create mode 100644 sourcecodes/bnt-master/graph/Old/dag_to_jtree.m create mode 100644 sourcecodes/bnt-master/graph/Old/dfs.m create mode 100644 sourcecodes/bnt-master/graph/Old/dsep_test.m create mode 100644 sourcecodes/bnt-master/graph/Old/mk_2D_lattice_slow.m (limited to 'sourcecodes/bnt-master/graph/Old') diff --git a/sourcecodes/bnt-master/graph/Old/CVS/Entries b/sourcecodes/bnt-master/graph/Old/CVS/Entries new file mode 100644 index 00000000..c45011ba --- /dev/null +++ b/sourcecodes/bnt-master/graph/Old/CVS/Entries @@ -0,0 +1,6 @@ +/best_first_elim_order.m/1.1.1.1/Mon Aug 29 17:44:02 2005// +/dag_to_jtree.m/1.1.1.1/Mon Aug 29 17:44:02 2005// +/dfs.m/1.1.1.1/Mon Aug 29 17:44:02 2005// +/dsep_test.m/1.1.1.1/Mon Aug 29 17:44:02 2005// +/mk_2D_lattice_slow.m/1.1.1.1/Mon Aug 29 17:44:02 2005// +D diff --git a/sourcecodes/bnt-master/graph/Old/CVS/Repository b/sourcecodes/bnt-master/graph/Old/CVS/Repository new file mode 100644 index 00000000..f3b2d81f --- /dev/null +++ b/sourcecodes/bnt-master/graph/Old/CVS/Repository @@ -0,0 +1 @@ +FullBNT/graph/Old diff --git a/sourcecodes/bnt-master/graph/Old/CVS/Root b/sourcecodes/bnt-master/graph/Old/CVS/Root new file mode 100644 index 00000000..f3bd14a6 --- /dev/null +++ b/sourcecodes/bnt-master/graph/Old/CVS/Root @@ -0,0 +1 @@ +:ext:nsaunier@bnt.cvs.sourceforge.net:/cvsroot/bnt diff --git a/sourcecodes/bnt-master/graph/Old/best_first_elim_order.m b/sourcecodes/bnt-master/graph/Old/best_first_elim_order.m new file mode 100644 index 00000000..82f1236b --- /dev/null +++ b/sourcecodes/bnt-master/graph/Old/best_first_elim_order.m @@ -0,0 +1,64 @@ +function order = best_first_elim_order(G, node_sizes, stage) +% BEST_FIRST_ELIM_ORDER Greedily search for an optimal elimination order. +% order = best_first_elim_order(moral_graph, node_sizes) +% +% Find an order in which to eliminate nodes from the graph in such a way as to try and minimize the +% weight of the resulting triangulated graph. The weight of a graph is the sum of the weights of each +% of its cliques; the weight of a clique is the product of the weights of each of its members; the +% weight of a node is the number of values it can take on. +% +% Since this is an NP-hard problem, we use the following greedy heuristic: +% at each step, eliminate that node which will result in the addition of the least +% number of fill-in edges, breaking ties by choosing the node that induces the lighest clique. +% For details, see +% - Kjaerulff, "Triangulation of graphs -- algorithms giving small total state space", +% Univ. Aalborg tech report, 1990 (www.cs.auc.dk/~uk) +% - C. Huang and A. Darwiche, "Inference in Belief Networks: A procedural guide", +% Intl. J. Approx. Reasoning, 11, 1994 +% + +% Warning: This code is pretty old and could probably be made faster. + +n = length(G); +if nargin < 3, stage = { 1:n }; end % no constraints + +% For long DBNs, it may be useful to eliminate all the nodes in slice t before slice t+1. +% This will ensure that the jtree has a repeating structure (at least away from both edges). +% This is why we have stages. +% See the discussion of splicing jtrees on p68 of +% Geoff Zweig's PhD thesis, Dept. Comp. Sci., UC Berkeley, 1998. +% This constraint can increase the clique size significantly. + +MG = G; % copy the original graph +uneliminated = ones(1,n); +order = zeros(1,n); +t = 1; % Counts which time slice we are on +for i=1:n + U = find(uneliminated); + valid = myintersect(U, stage{t}); + % Choose the best node from the set of valid candidates + score1 = zeros(1,length(valid)); + score2 = zeros(1,length(valid)); + for j=1:length(valid) + k = valid(j); + ns = myintersect(neighbors(G, k), U); + l = length(ns); + M = MG(ns,ns); + score1(j) = l^2 - sum(M(:)); % num. added edges + score2(j) = prod(node_sizes([k ns])); % weight of clique + end + j1s = find(score1==min(score1)); + j = j1s(argmin(score2(j1s))); + k = valid(j); + uneliminated(k) = 0; + order(i) = k; + ns = myintersect(neighbors(G, k), U); + if ~isempty(ns) + G(ns,ns) = 1; + G = setdiag(G,0); + end + if ~any(logical(uneliminated(stage{t}))) % are we allowed to the next slice? + t = t + 1; + end +end + diff --git a/sourcecodes/bnt-master/graph/Old/dag_to_jtree.m b/sourcecodes/bnt-master/graph/Old/dag_to_jtree.m new file mode 100644 index 00000000..23c58430 --- /dev/null +++ b/sourcecodes/bnt-master/graph/Old/dag_to_jtree.m @@ -0,0 +1,55 @@ +function [jtree, root, cliques, B, w, elim_order, moral_edges, fill_in_edges, strong] = ... + dag_to_jtree(dag, node_sizes, partial_order, stages, clusters) +% DAG_TO_JTREE Moralize and triangulate a DAG, and make a junction tree from its cliques. +% [jtree, root, cliques, B, w, elim_order, moral_edges, fill_in_edges, strong] = ... +% dag_to_jtree(dag, node_sizes, partial_order, stages, clusters) +% +% Input: +% dag(i,j) +% jtree(i,j) = 1 iff there is an arc between clique i and clique j +% root = the root clique +% cliques{i} = the nodes in clique i +% B(i,j) = 1 iff node j occurs in clique i +% w(i) = weight of clique i + +N = length(bnet.dag); +if nargin < 2, obs_nodes = []; end +if nargin < 3, stages = { 1:N }; end +if nargin < 4, clusters = {}; end + +[MG, moral_edges] = moralize(bnet.dag); + +% Add extra arcs between nodes in each cluster to ensure they occur in the same clique +for i=1:length(clusters) + c = clusters{i}; + MG(c,c) = 1; +end +MG = setdiag(MG, 0); + +% Find an optimal elimination ordering (NP-hard problem!) +ns = bnet.node_sizes(:); +ns(obs_nodes) = 1; % observed nodes have only 1 possible value +partial_order = determine_elim_constraints(bnet, obs_nodes); + +if isempty(partial_order) + strong = 0; + elim_order = best_first_elim_order(MG, ns, stages); +else + strong = 1; + elim_order = strong_elim_order(MG, ns, partial_order); +end + +[MTG, cliques, fill_in_edges] = triangulate(MG, elim_order); + +% Connect the cliques up into a jtree, +[jtree, root, B, w] = cliques_to_jtree(cliques, ns); + +if 0 + disp('testing dag to jtree'); + % Find the cliques containing each node, and check they form a connected subtree + clqs_con_node = cell(1,N); + for i=1:N + clqs_con_node{i} = find(B(:,i))'; + end + check_jtree_property(clqs_con_node, jtree); +end diff --git a/sourcecodes/bnt-master/graph/Old/dfs.m b/sourcecodes/bnt-master/graph/Old/dfs.m new file mode 100644 index 00000000..0c7f46ab --- /dev/null +++ b/sourcecodes/bnt-master/graph/Old/dfs.m @@ -0,0 +1,84 @@ +function [d, pre, post, height, cycle, pred] = dfs(adj_mat, start, directed) +% DFS Perform a depth-first search of the graph starting from 'start'. +% [d, pre, post, height, cycle, pred] = dfs(adj_mat, start, directed) +% +% d(i) is the time at which node i is first discovered. +% pre is a listing of the nodes in the order in which they are first encountered (opened). +% post is a listing of the nodes in the order in which they are last encountered (closed). +% A node is last encountered once we have explored all of its neighbors. +% If the graph is directed, i's neighbors are its children. +% If the graph is a tree, preorder is parents before children, and +% postorder is children before parents. +% For a DAG, topological order = reverse(postorder). +% height(i) is the height (distance) of node i from the start. +% 'cycle' is true iff a (directed) cycle is found. +% pred(i) is the parent of i in the dfs tree rooted at start. +% See Cormen, Leiserson and Rivest, "An intro. to algorithms" 1994, p478. + +% We can detect undirected cycles by checking if we are about to visit a node n which we have +% already visited. To detect *directed* cycles, we need to know if n has been closed or is still open. +% For example (where arcs are directed down) +% 1 2 +% \ / +% 3 +% Assume we visit 1, 3 and then 2 in order. The fact that a child of 2 (namely, 3) has +% already been visited is okay, because 3 has been closed. +% The algorithms in Aho, Hopcroft and Ullman, and Sedgewick, do not detect directed cycles. + +n = length(adj_mat); + +global white gray black +white = 0; gray = 1; black = 2; + +color = white*ones(1,n); +d = zeros(1,n); +height = zeros(1,n); +pred = zeros(1,n); +pre = []; +post = []; +cycle = 0; +global count +count = 0; +h = 0; +[d, pre, post, height, cycle, color, pred] = ... + dfs2(adj_mat, start, directed, h, d, pre, post, height, cycle, color, pred); + + + +%%%%%%%%%% + +function [d, pre, post, height, cycle, color, pred] = ... + dfs2(adj_mat, i, directed, h, d, pre, post, height, cycle, color, pred) + +global count +global white gray black + +color(i) = gray; +count = count + 1; +d(i) = count; +pre = [pre i]; +height(i) = h; +if directed + ns = children(adj_mat, i); +else + ns = neighbors(adj_mat, i); +end +for j=1:length(ns) + n=ns(j); + if ~directed & n==pred(i) % don't go back up the edge you just came down + % continue + else + if color(n) == gray % going back to a non-closed vertex via a new edge + %fprintf(1, 'cycle from %d to %d\n', i, n); + cycle = 1; + end + if color(n) == white % not visited n before + pred(n)=i; + [d, pre, post, height, cycle, color, pred] = ... + dfs2(adj_mat, n, directed, h+1, d, pre, post, height, cycle, color, pred); + end + end +end +color(i) = black; +post = [post i]; + diff --git a/sourcecodes/bnt-master/graph/Old/dsep_test.m b/sourcecodes/bnt-master/graph/Old/dsep_test.m new file mode 100644 index 00000000..f0f14638 --- /dev/null +++ b/sourcecodes/bnt-master/graph/Old/dsep_test.m @@ -0,0 +1,15 @@ + +% Cowell et al p72 +G = zeros(10); +G(1,2)=1; +G(2,3)=1; +G(3,7)=1; +G(4,[5 8])=1; +G(5,6)=1; +G(6,7)=1; +G(7,[9 10])=1; +G(8,9)=1; + +dsep(1, 4, [5 7], G) +dsep(1, 4, [7], G) +dsep(1, 4, [10 5], G) diff --git a/sourcecodes/bnt-master/graph/Old/mk_2D_lattice_slow.m b/sourcecodes/bnt-master/graph/Old/mk_2D_lattice_slow.m new file mode 100644 index 00000000..e5f595b7 --- /dev/null +++ b/sourcecodes/bnt-master/graph/Old/mk_2D_lattice_slow.m @@ -0,0 +1,121 @@ +function G = mk_2D_lattice(nrows, ncols, wrap_around) +% MK_2D_LATTICE Return adjacency matrix for 4-nearest neighbor connected 2D lattice +% G = mk_2D_lattice(nrows, ncols, wrap_around) +% G(k1, k2) = 1 iff k1=(i1,j1) is connected to k2=(i2,j2) +% +% If wrap_around = 1, we use toroidal boundary conditions (default = 0) +% +% Nodes are assumed numbered as in the following 3x3 lattice +% 1 4 7 +% 2 5 8 +% 3 6 9 +% +% e.g., G = mk_2D_lattice(3, 3, 0) returns +% 0 1 0 1 0 0 0 0 0 +% 1 0 1 0 1 0 0 0 0 +% 0 1 0 0 0 1 0 0 0 +% 1 0 0 0 1 0 1 0 0 +% 0 1 0 1 0 1 0 1 0 +% 0 0 1 0 1 0 0 0 1 +% 0 0 0 1 0 0 0 1 0 +% 0 0 0 0 1 0 1 0 1 +% 0 0 0 0 0 1 0 1 0 +% so find(G(5,:)) = [2 4 6 8] +% but find(G(1,:)) = [2 4] +% +% Using wrap around, G = mk_2D_lattice(3, 3, 1), we get +% 0 1 1 1 0 0 1 0 0 +% 1 0 1 0 1 0 0 1 0 +% 1 1 0 0 0 1 0 0 1 +% 1 0 0 0 1 1 1 0 0 +% 0 1 0 1 0 1 0 1 0 +% 0 0 1 1 1 0 0 0 1 +% 1 0 0 1 0 0 0 1 1 +% 0 1 0 0 1 0 1 0 1 +% 0 0 1 0 0 1 1 1 0 +% so find(G(5,:)) = [2 4 6 8] +% and find(G(1,:)) = [2 3 4 7] + +if nargin < 3, wrap_around = 0; end + +% M contains the number of each cell e.g. +% 1 4 7 +% 2 5 8 +% 3 6 9 +% North neighbors (assuming wrap around) are +% 3 6 9 +% 1 4 7 +% 2 5 8 +% Without wrap around, they are +% 1 4 7 +% 1 4 7 +% 2 5 8 +% The first row is arbitrary, since pixels at the top have no north neighbor. + +npixels = nrows*ncols; + +N = 1; E = 2; S = 3; W = 4; +if wrap_around + rows{N} = [nrows 1:nrows-1]; cols{N} = 1:ncols; + rows{E} = 1:nrows; cols{E} = [2:ncols 1]; + rows{S} = [2:nrows 1]; cols{S} = 1:ncols; + rows{W} = 1:nrows; cols{W} = [ncols 1:ncols-1]; +else + rows{N} = [1 1:nrows-1]; cols{N} = 1:ncols; + rows{E} = 1:nrows; cols{E} = [2:ncols 2]; + rows{S} = [2:nrows 2]; cols{S} = 1:ncols; + rows{W} = 1:nrows; cols{W} = [1 1:ncols-1]; +end + +M = reshape(1:npixels, [nrows ncols]); +nbrs = cell(1, 4); +for i=1:4 + nbrs{i} = M(rows{i}, cols{i}); +end + + +G = zeros(npixels, npixels); +if wrap_around + for i=1:4 + if 0 + % naive + for p=1:npixels + G(p, nbrs{i}(p)) = 1; + end + else + % vectorized + ndx2 = sub2ind([npixels npixels], 1:npixels, nbrs{i}(:)'); + G(ndx2) = 1; + end + end +else + i = N; + mask = ones(nrows, ncols); + mask(1,:) = 0; % pixels in row 1 have no nbr to the north + ndx = find(mask); + ndx2 = sub2ind([npixels npixels], ndx, nbrs{i}(ndx)); + G(ndx2) = 1; + + i = E; + mask = ones(nrows, ncols); + mask(:,ncols) = 0; + ndx = find(mask); + ndx2 = sub2ind([npixels npixels], ndx, nbrs{i}(ndx)); + G(ndx2) = 1; + + i = S; + mask = ones(nrows, ncols); + mask(nrows,:)=0; + ndx = find(mask); + ndx2 = sub2ind([npixels npixels], ndx, nbrs{i}(ndx)); + G(ndx2) = 1; + + i = W; + mask = ones(nrows, ncols); + mask(:,1)=0; + ndx = find(mask); + ndx2 = sub2ind([npixels npixels], ndx, nbrs{i}(ndx)); + G(ndx2) = 1; +end + +G = setdiag(G, 0); -- cgit 1.4.1