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
|
function t=min_weight_tree(i,g)
// Copyright INRIA
[lhs,rhs]=argn(0)
select rhs
case 1
if type(i)==16 then
g=i
i=1
else
error('First argument must be a number or a graph list')
end
case 2 then
if prod(size(i))<>1 then
error('First argument must be a number')
end
else
error(39)
end
// check g
check_graph(g)
// compute lp, la and ls
n=g('node_number')
ma=prod(size(g('tail')))
if g('directed')==1 then
[lp,la,ls]=m6ta2lpd(g('tail'),g('head'),n+1,n)
else
[lp,la,ls]=m6ta2lpu(g('tail'),g('head'),n+1,n,2*ma)
end
// value of weight
if g('edge_weight')==[] then
w=zeros(1,ma)
else
w=g('edge_weight')
end
// compute minimal spanning tree
if g('directed')==1 then
alf=m6dmtree(i,la,lp,ls,n,w)
t=m6prevn2st(alf,la,lp,ls)
else
if ma<0.5*n*n then
alf=m6umtree1(la,lp,ls,n,w)
else
alf=m6umtree(la,lp,ls,n,w)
end
t=m6edge2st(alf)
end
|
