wolffd@0: function [t,nk] = minspan(IJC)
wolffd@0: %MINSPAN Minimum weight spanning tree using Kruskal algorithm.
wolffd@0: %[t,nk] = minspan(IJC)
wolffd@0: %   IJC = n x 3 matrix arc list [i j c] of arc heads, tails, and costs
wolffd@0: %     t = n-element logical vector, where 
wolffd@0: %         t(i) = 1, if IJC(i,:) arc in spanning tree
wolffd@0: %         t(i) = k, if IJC(i,:) arc in component k of forest
wolffd@0: %    nk = number of components
wolffd@0: 
wolffd@0: % Copyright (c) 1998-2001 by Michael G. Kay
wolffd@0: % Matlog Version 5 22-Aug-2001
wolffd@0: 
wolffd@0: % Input Error Checking ******************************************************
wolffd@0: [n,cIJC] = size(IJC);
wolffd@0: if cIJC ~= 3
wolffd@0:    error('''IJC'' must be a 3-column matrix.')
wolffd@0: elseif n < 1
wolffd@0:    error('''IJC'' must have at least one row.')
wolffd@0: elseif any(IJC(:,1) < 1) | any(any(~isint(IJC(:,[1 2]))))
wolffd@0:    error('Invalid arc index in IJC.')
wolffd@0: end
wolffd@0: % End (Input Error Checking) ************************************************
wolffd@0: 
wolffd@0: i = IJC(:,1); j = abs(IJC(:,2));
wolffd@0: m = max(max([i j]));
wolffd@0: 
wolffd@0: sidxIJ = argsort(IJC(:,3));
wolffd@0: i = i(sidxIJ); j = j(sidxIJ);
wolffd@0: 
wolffd@0: t = logical(zeros(n,1));
wolffd@0: k = 1;            % Current arc
wolffd@0: nt = 0;           % Number of arcs in spanning tree
wolffd@0: v = (1:m)';       % Arc labels
wolffd@0: 
wolffd@0: while nt < m - 1 & k <= n
wolffd@0:    if (v(i(k)) ~= v(j(k)))
wolffd@0:       v(v==v(j(k))) = v(i(k));
wolffd@0:       t(k) = 1;
wolffd@0:       nt = nt + 1;
wolffd@0:    end
wolffd@0:    k = k + 1;
wolffd@0: end
wolffd@0: 
wolffd@0: idxIJ = invperm(sidxIJ);
wolffd@0: t = t(idxIJ); i = i(idxIJ); j = j(idxIJ);
wolffd@0: 
wolffd@0: c = unique(v(unique([i; j])));   % Unique labels of arc vertices
wolffd@0: nk = length(c);
wolffd@0: if ~any(t), nk = 0; end          % Self-loop not a component
wolffd@0: 
wolffd@0: if nk > 1
wolffd@0:    for k = 1:nk
wolffd@0:       t(t~=0 & v(i)==c(k)) = k;  % Relabel to consecutive component numbers
wolffd@0:    end
wolffd@0: end
wolffd@0: