comparison toolboxes/FullBNT-1.0.7/graph/minspan.m @ 0:e9a9cd732c1e tip

first hg version after svn

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