Mercurial > hg > camir-aes2014
diff toolboxes/FullBNT-1.0.7/graph/trees.txt @ 0:e9a9cd732c1e tip
first hg version after svn
author | wolffd |
---|---|
date | Tue, 10 Feb 2015 15:05:51 +0000 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/toolboxes/FullBNT-1.0.7/graph/trees.txt Tue Feb 10 15:05:51 2015 +0000 @@ -0,0 +1,168 @@ + +% make undirected adjacency matrix of graph/tree +% e.g., +% 1 +% / \ +% 2 3 +T = zeros(3,3); +T(1,2) = 1; T(2,1)=1; +T(1,3)=1; T(3,1) = 1; + +root = 1; +[T, preorder, postorder] = mk_rooted_tree(T, root); + +% bottom up message passing leaves to root +for n=postorder(:)' + for p = parents(T, n) + % p is parent of n + end +end + +% top down, root to leaves +for n=preorder(:)' + for c= children(T,n) + % c is child of n + end +end + + +%%%%%%%%%%%%% + +function ps = parents(adj_mat, i) +% PARENTS Return the list of parents of node i +% ps = parents(adj_mat, i) + +ps = find(adj_mat(:,i))'; + + +%%%%%%%%%%%% + +function cs = children(adj_mat, i, t) +% CHILDREN Return the indices of a node's children in sorted order +% c = children(adj_mat, i, t) +% +% t is an optional argument: if present, dag is assumed to be a 2-slice DBN + +if nargin < 3 + cs = find(adj_mat(i,:)); +else + if t==1 + cs = find(adj_mat(i,:)); + else + ss = length(adj_mat)/2; + j = i+ss; + cs = find(adj_mat(j,:)) + (t-2)*ss; + end +end + +%%%%%%%%%%% + +function [T, pre, post, cycle] = mk_rooted_tree(G, root) +% MK_ROOTED_TREE Make a directed, rooted tree out of an undirected tree. +% [T, pre, post, cycle] = mk_rooted_tree(G, root) + +n = length(G); +T = sparse(n,n); % not the same as T = sparse(n) ! +directed = 0; +[d, pre, post, cycle, f, pred] = dfs(G, root, directed); +for i=1:length(pred) + if pred(i)>0 + T(pred(i),i)=1; + end +end + + +%%%%%%%%%%% + +function [d, pre, post, cycle, f, pred] = dfs(adj_mat, start, directed) +% DFS Perform a depth-first search of the graph starting from 'start'. +% [d, pre, post, cycle, f, pred] = dfs(adj_mat, start, directed) +% +% Input: +% adj_mat(i,j)=1 iff i is connected to j. +% start is the root vertex of the dfs tree; if [], all nodes are searched +% directed = 1 if the graph is directed +% +% Output: +% d(i) is the time at which node i is first discovered. +% pre is a list of the nodes in the order in which they are first encountered (opened). +% post is a list of the nodes in the order in which they are last encountered (closed). +% 'cycle' is true iff a (directed) cycle is found. +% f(i) is the time at which node i is finished. +% pred(i) is the predecessor of i in the dfs tree. +% +% If the graph is a tree, preorder is parents before children, +% and postorder is children before parents. +% For a DAG, topological order = reverse(postorder). +% +% See Cormen, Leiserson and Rivest, "An intro. to algorithms" 1994, p478. + +n = length(adj_mat); + +global white gray black color +white = 0; gray = 1; black = 2; +color = white*ones(1,n); + +global time_stamp +time_stamp = 0; + +global d f +d = zeros(1,n); +f = zeros(1,n); + +global pred +pred = zeros(1,n); + +global cycle +cycle = 0; + +global pre post +pre = []; +post = []; + +if ~isempty(start) + dfs_visit(start, adj_mat, directed); +else + for u=1:n + if color(u)==white + dfs_visit(u, adj_mat, directed); + end + end +end + + +%%%%%%%%%% + +function dfs_visit(u, adj_mat, directed) + +global white gray black color time_stamp d f pred cycle pre post + +pre = [pre u]; +color(u) = gray; +time_stamp = time_stamp + 1; +d(u) = time_stamp; +if directed + ns = children(adj_mat, u); +else + ns = neighbors(adj_mat, u); + ns = mysetdiff(ns, pred(u)); % don't go back to visit the guy who called you! +end +for v=ns(:)' + %fprintf('u=%d, v=%d, color(v)=%d\n', u, v, color(v)) + switch color(v) + case white, % not visited v before (tree edge) + pred(v)=u; + dfs_visit(v, adj_mat, directed); + case gray, % back edge - v has been visited, but is still open + cycle = 1; + %fprintf('cycle: back edge from v=%d to u=%d\n', v, u); + case black, % v has been visited, but is closed + % no-op + end +end +color(u) = black; +post = [post u]; +time_stamp = time_stamp + 1; +f(u) = time_stamp; + +