|
wolffd@0
|
1 function [t,nk] = minspan(IJC)
|
|
wolffd@0
|
2 %MINSPAN Minimum weight spanning tree using Kruskal algorithm.
|
|
wolffd@0
|
3 %[t,nk] = minspan(IJC)
|
|
wolffd@0
|
4 % IJC = n x 3 matrix arc list [i j c] of arc heads, tails, and costs
|
|
wolffd@0
|
5 % t = n-element logical vector, where
|
|
wolffd@0
|
6 % t(i) = 1, if IJC(i,:) arc in spanning tree
|
|
wolffd@0
|
7 % t(i) = k, if IJC(i,:) arc in component k of forest
|
|
wolffd@0
|
8 % nk = number of components
|
|
wolffd@0
|
9
|
|
wolffd@0
|
10 % Copyright (c) 1998-2001 by Michael G. Kay
|
|
wolffd@0
|
11 % Matlog Version 5 22-Aug-2001
|
|
wolffd@0
|
12
|
|
wolffd@0
|
13 % Input Error Checking ******************************************************
|
|
wolffd@0
|
14 [n,cIJC] = size(IJC);
|
|
wolffd@0
|
15 if cIJC ~= 3
|
|
wolffd@0
|
16 error('''IJC'' must be a 3-column matrix.')
|
|
wolffd@0
|
17 elseif n < 1
|
|
wolffd@0
|
18 error('''IJC'' must have at least one row.')
|
|
wolffd@0
|
19 elseif any(IJC(:,1) < 1) | any(any(~isint(IJC(:,[1 2]))))
|
|
wolffd@0
|
20 error('Invalid arc index in IJC.')
|
|
wolffd@0
|
21 end
|
|
wolffd@0
|
22 % End (Input Error Checking) ************************************************
|
|
wolffd@0
|
23
|
|
wolffd@0
|
24 i = IJC(:,1); j = abs(IJC(:,2));
|
|
wolffd@0
|
25 m = max(max([i j]));
|
|
wolffd@0
|
26
|
|
wolffd@0
|
27 sidxIJ = argsort(IJC(:,3));
|
|
wolffd@0
|
28 i = i(sidxIJ); j = j(sidxIJ);
|
|
wolffd@0
|
29
|
|
wolffd@0
|
30 t = logical(zeros(n,1));
|
|
wolffd@0
|
31 k = 1; % Current arc
|
|
wolffd@0
|
32 nt = 0; % Number of arcs in spanning tree
|
|
wolffd@0
|
33 v = (1:m)'; % Arc labels
|
|
wolffd@0
|
34
|
|
wolffd@0
|
35 while nt < m - 1 & k <= n
|
|
wolffd@0
|
36 if (v(i(k)) ~= v(j(k)))
|
|
wolffd@0
|
37 v(v==v(j(k))) = v(i(k));
|
|
wolffd@0
|
38 t(k) = 1;
|
|
wolffd@0
|
39 nt = nt + 1;
|
|
wolffd@0
|
40 end
|
|
wolffd@0
|
41 k = k + 1;
|
|
wolffd@0
|
42 end
|
|
wolffd@0
|
43
|
|
wolffd@0
|
44 idxIJ = invperm(sidxIJ);
|
|
wolffd@0
|
45 t = t(idxIJ); i = i(idxIJ); j = j(idxIJ);
|
|
wolffd@0
|
46
|
|
wolffd@0
|
47 c = unique(v(unique([i; j]))); % Unique labels of arc vertices
|
|
wolffd@0
|
48 nk = length(c);
|
|
wolffd@0
|
49 if ~any(t), nk = 0; end % Self-loop not a component
|
|
wolffd@0
|
50
|
|
wolffd@0
|
51 if nk > 1
|
|
wolffd@0
|
52 for k = 1:nk
|
|
wolffd@0
|
53 t(t~=0 & v(i)==c(k)) = k; % Relabel to consecutive component numbers
|
|
wolffd@0
|
54 end
|
|
wolffd@0
|
55 end
|
|
wolffd@0
|
56
|
