diff options
Diffstat (limited to 'sourcecodes/bnt-master/graph/Old')
| -rw-r--r-- | sourcecodes/bnt-master/graph/Old/CVS/Entries | 6 | ||||
| -rw-r--r-- | sourcecodes/bnt-master/graph/Old/CVS/Repository | 1 | ||||
| -rw-r--r-- | sourcecodes/bnt-master/graph/Old/CVS/Root | 1 | ||||
| -rw-r--r-- | sourcecodes/bnt-master/graph/Old/best_first_elim_order.m | 64 | ||||
| -rw-r--r-- | sourcecodes/bnt-master/graph/Old/dag_to_jtree.m | 55 | ||||
| -rw-r--r-- | sourcecodes/bnt-master/graph/Old/dfs.m | 84 | ||||
| -rw-r--r-- | sourcecodes/bnt-master/graph/Old/dsep_test.m | 15 | ||||
| -rw-r--r-- | sourcecodes/bnt-master/graph/Old/mk_2D_lattice_slow.m | 121 |
8 files changed, 347 insertions, 0 deletions
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); |