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

first hg version after svn

+function [c,v] = scc(a,tol)
+
+%       Finds the strongly connected sets of vertices
+%                in the DI-rected G-raph of A
+%          c = 0-1 matrix displaying accessibility
+%          v = displays the equivalent classes
+%
+% v(i,j) is the j'th member of the i'th equiv class (0 padded)
+%
+% http://www.math.wsu.edu/math/faculty/tsat/matlab.html
+
+[m,n] = size(a);
+if m~=n 'Not a Square Matrix', return, end
+b=abs(a); o=ones(size(a)); x=zeros(1,n);
+msg='The Matrix is Irreducible !'; v='Connected Directed Graph !';
+if (nargin==1) tol=n*eps*norm(a,'inf'); end
+
+% Create a companion matrix
+c = b>tol*o;
+if (c==o)
+  %  msg, return
+  v = 1:length(a);
+  return
+end
+
+
+% Compute accessibility in at most n-step paths
+for k=1:n
+  for j=1:n
+    for i=1:n
+      % If index i accesses j, where can you go ?
+      if c(i,j) > 0  c(i,:) = c(i,:)+c(j,:); end
+    end
+  end
+end
+% Create a 0-1 matrix with the above information
+c>zeros(size(a)); c=ans; if (c==o) msg, return, end
+
+% Identify equivalence classes
+d=c.*c'+eye(size(a)); d>zeros(size(a)); d=ans;
+v=zeros(size(a));
+for i=1:n find(d(i,:)); ans(n)=0; v(i,:)=ans; end
+
+% Eliminate displaying of identical rows
+i=1;
+while(i<n)
+  for k=i+1:n
+    if v(k,1) == v(i,1)
+      v(k,:)=x;
+    end
+  end
+  i=i+1;
+end
+j=1;
+for i=1:n
+  if v(i,1)>0
+    h(j,:)=v(i,:);
+    j=j+1;
+  end
+end
+v=h;
+
+
+