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