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