Mercurial > hg > camir-aes2014

annotate toolboxes/FullBNT-1.0.7/graph/trees.txt @ 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
wolffd@0 2 % make undirected adjacency matrix of graph/tree
wolffd@0 3 % e.g.,
wolffd@0 4 % 1
wolffd@0 5 % / \
wolffd@0 6 % 2 3
wolffd@0 7 T = zeros(3,3);
wolffd@0 8 T(1,2) = 1; T(2,1)=1;
wolffd@0 9 T(1,3)=1; T(3,1) = 1;
wolffd@0 10
wolffd@0 11 root = 1;
wolffd@0 12 [T, preorder, postorder] = mk_rooted_tree(T, root);
wolffd@0 13
wolffd@0 14 % bottom up message passing leaves to root
wolffd@0 15 for n=postorder(:)'
wolffd@0 16 for p = parents(T, n)
wolffd@0 17 % p is parent of n
wolffd@0 18 end
wolffd@0 19 end
wolffd@0 20
wolffd@0 21 % top down, root to leaves
wolffd@0 22 for n=preorder(:)'
wolffd@0 23 for c= children(T,n)
wolffd@0 24 % c is child of n
wolffd@0 25 end
wolffd@0 26 end
wolffd@0 27
wolffd@0 28
wolffd@0 29 %%%%%%%%%%%%%
wolffd@0 30
wolffd@0 31 function ps = parents(adj_mat, i)
wolffd@0 32 % PARENTS Return the list of parents of node i
wolffd@0 33 % ps = parents(adj_mat, i)
wolffd@0 34
wolffd@0 35 ps = find(adj_mat(:,i))';
wolffd@0 36
wolffd@0 37
wolffd@0 38 %%%%%%%%%%%%
wolffd@0 39
wolffd@0 40 function cs = children(adj_mat, i, t)
wolffd@0 41 % CHILDREN Return the indices of a node's children in sorted order
wolffd@0 42 % c = children(adj_mat, i, t)
wolffd@0 43 %
wolffd@0 44 % t is an optional argument: if present, dag is assumed to be a 2-slice DBN
wolffd@0 45
wolffd@0 46 if nargin < 3
wolffd@0 47 cs = find(adj_mat(i,:));
wolffd@0 48 else
wolffd@0 49 if t==1
wolffd@0 50 cs = find(adj_mat(i,:));
wolffd@0 51 else
wolffd@0 52 ss = length(adj_mat)/2;
wolffd@0 53 j = i+ss;
wolffd@0 54 cs = find(adj_mat(j,:)) + (t-2)*ss;
wolffd@0 55 end
wolffd@0 56 end
wolffd@0 57
wolffd@0 58 %%%%%%%%%%%
wolffd@0 59
wolffd@0 60 function [T, pre, post, cycle] = mk_rooted_tree(G, root)
wolffd@0 61 % MK_ROOTED_TREE Make a directed, rooted tree out of an undirected tree.
wolffd@0 62 % [T, pre, post, cycle] = mk_rooted_tree(G, root)
wolffd@0 63
wolffd@0 64 n = length(G);
wolffd@0 65 T = sparse(n,n); % not the same as T = sparse(n) !
wolffd@0 66 directed = 0;
wolffd@0 67 [d, pre, post, cycle, f, pred] = dfs(G, root, directed);
wolffd@0 68 for i=1:length(pred)
wolffd@0 69 if pred(i)>0
wolffd@0 70 T(pred(i),i)=1;
wolffd@0 71 end
wolffd@0 72 end
wolffd@0 73
wolffd@0 74
wolffd@0 75 %%%%%%%%%%%
wolffd@0 76
wolffd@0 77 function [d, pre, post, cycle, f, pred] = dfs(adj_mat, start, directed)
wolffd@0 78 % DFS Perform a depth-first search of the graph starting from 'start'.
wolffd@0 79 % [d, pre, post, cycle, f, pred] = dfs(adj_mat, start, directed)
wolffd@0 80 %
wolffd@0 81 % Input:
wolffd@0 82 % adj_mat(i,j)=1 iff i is connected to j.
wolffd@0 83 % start is the root vertex of the dfs tree; if [], all nodes are searched
wolffd@0 84 % directed = 1 if the graph is directed
wolffd@0 85 %
wolffd@0 86 % Output:
wolffd@0 87 % d(i) is the time at which node i is first discovered.
wolffd@0 88 % pre is a list of the nodes in the order in which they are first encountered (opened).
wolffd@0 89 % post is a list of the nodes in the order in which they are last encountered (closed).
wolffd@0 90 % 'cycle' is true iff a (directed) cycle is found.
wolffd@0 91 % f(i) is the time at which node i is finished.
wolffd@0 92 % pred(i) is the predecessor of i in the dfs tree.
wolffd@0 93 %
wolffd@0 94 % If the graph is a tree, preorder is parents before children,
wolffd@0 95 % and postorder is children before parents.
wolffd@0 96 % For a DAG, topological order = reverse(postorder).
wolffd@0 97 %
wolffd@0 98 % See Cormen, Leiserson and Rivest, "An intro. to algorithms" 1994, p478.
wolffd@0 99
wolffd@0 100 n = length(adj_mat);
wolffd@0 101
wolffd@0 102 global white gray black color
wolffd@0 103 white = 0; gray = 1; black = 2;
wolffd@0 104 color = white*ones(1,n);
wolffd@0 105
wolffd@0 106 global time_stamp
wolffd@0 107 time_stamp = 0;
wolffd@0 108
wolffd@0 109 global d f
wolffd@0 110 d = zeros(1,n);
wolffd@0 111 f = zeros(1,n);
wolffd@0 112
wolffd@0 113 global pred
wolffd@0 114 pred = zeros(1,n);
wolffd@0 115
wolffd@0 116 global cycle
wolffd@0 117 cycle = 0;
wolffd@0 118
wolffd@0 119 global pre post
wolffd@0 120 pre = [];
wolffd@0 121 post = [];
wolffd@0 122
wolffd@0 123 if ~isempty(start)
wolffd@0 124 dfs_visit(start, adj_mat, directed);
wolffd@0 125 else
wolffd@0 126 for u=1:n
wolffd@0 127 if color(u)==white
wolffd@0 128 dfs_visit(u, adj_mat, directed);
wolffd@0 129 end
wolffd@0 130 end
wolffd@0 131 end
wolffd@0 132
wolffd@0 133
wolffd@0 134 %%%%%%%%%%
wolffd@0 135
wolffd@0 136 function dfs_visit(u, adj_mat, directed)
wolffd@0 137
wolffd@0 138 global white gray black color time_stamp d f pred cycle pre post
wolffd@0 139
wolffd@0 140 pre = [pre u];
wolffd@0 141 color(u) = gray;
wolffd@0 142 time_stamp = time_stamp + 1;
wolffd@0 143 d(u) = time_stamp;
wolffd@0 144 if directed
wolffd@0 145 ns = children(adj_mat, u);
wolffd@0 146 else
wolffd@0 147 ns = neighbors(adj_mat, u);
wolffd@0 148 ns = mysetdiff(ns, pred(u)); % don't go back to visit the guy who called you!
wolffd@0 149 end
wolffd@0 150 for v=ns(:)'
wolffd@0 151 %fprintf('u=%d, v=%d, color(v)=%d\n', u, v, color(v))
wolffd@0 152 switch color(v)
wolffd@0 153 case white, % not visited v before (tree edge)
wolffd@0 154 pred(v)=u;
wolffd@0 155 dfs_visit(v, adj_mat, directed);
wolffd@0 156 case gray, % back edge - v has been visited, but is still open
wolffd@0 157 cycle = 1;
wolffd@0 158 %fprintf('cycle: back edge from v=%d to u=%d\n', v, u);
wolffd@0 159 case black, % v has been visited, but is closed
wolffd@0 160 % no-op
wolffd@0 161 end
wolffd@0 162 end
wolffd@0 163 color(u) = black;
wolffd@0 164 post = [post u];
wolffd@0 165 time_stamp = time_stamp + 1;
wolffd@0 166 f(u) = time_stamp;
wolffd@0 167
wolffd@0 168