Mercurial > hg > camir-aes2014

annotate toolboxes/FullBNT-1.0.7/graph/min_subtree_con_nodes.m @ 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 function [subtree, nroot_node] = min_subtree_con_nodes(jtree, root, nodes)
wolffd@0 2 %min_subtree_con_nodes get the minimum subtree of tree which contains the nodes
wolffd@0 3
wolffd@0 4 if isempty(jtree) | isempty(nodes)
wolffd@0 5 subtree = [];
wolffd@0 6 nroot_node = [];
wolffd@0 7 return;
wolffd@0 8 end
wolffd@0 9
wolffd@0 10 rnodes = min_subtree_nodes(jtree, nodes);
wolffd@0 11 nea_node = nearest_node(jtree, root, nodes);
wolffd@0 12 node_num = length(jtree);
wolffd@0 13 subtree = zeros(node_num);
wolffd@0 14 subtree(rnodes, rnodes) = jtree(rnodes, rnodes);
wolffd@0 15 nroot_node = nea_node;
wolffd@0 16
wolffd@0 17
wolffd@0 18 function rnodes = min_subtree_nodes(tree, nodes)
wolffd@0 19 rnodes = [];
wolffd@0 20 if isempty(tree) | isempty(nodes)
wolffd@0 21 return
wolffd@0 22 end
wolffd@0 23
wolffd@0 24 rnodes = nodes(1);
wolffd@0 25 newnodes = neighbors(tree, nodes(1));
wolffd@0 26 while ~mysubset(nodes, rnodes)
wolffd@0 27 swapnodes = newnodes;
wolffd@0 28 newnodes = [];
wolffd@0 29 added = 0;
wolffd@0 30 for i=1:length(swapnodes)
wolffd@0 31 inode = swapnodes(i);
wolffd@0 32 tnodes = myunion(inode, rnodes);
wolffd@0 33 if mysubset(nodes, tnodes)
wolffd@0 34 added = 1;
wolffd@0 35 break;
wolffd@0 36 end
wolffd@0 37 nns = neighbors(tree, inode);
wolffd@0 38 add_nodes = mysetdiff(nns, tnodes);
wolffd@0 39 newnodes = myunion(newnodes, add_nodes);
wolffd@0 40 end
wolffd@0 41 if added
wolffd@0 42 rnodes = tnodes;
wolffd@0 43 else
wolffd@0 44 rnodes = myunion(rnodes, newnodes);
wolffd@0 45 end
wolffd@0 46 end
wolffd@0 47
wolffd@0 48 function nea_node = nearest_node(tree, inode, nodes)
wolffd@0 49 if myismember(inode, nodes)
wolffd@0 50 nea_node = inode;
wolffd@0 51 return;
wolffd@0 52 end
wolffd@0 53 cs = children(tree, inode);
wolffd@0 54 for i = 1:length(cs)
wolffd@0 55 n = cs(i);
wolffd@0 56 nea_node = nearest_node(tree, n, nodes);
wolffd@0 57 end
wolffd@0 58
wolffd@0 59
wolffd@0 60