tarjan

 function SCC = tarjan(e)
 Implements tarjan's algorithm for a graph with adjacency matrix e.  A value in
 e(i,j) indicates an edge from v(j) to v(i).  If this is transposed from the
 default, well it really shouldn't matter, right? 

 Returns a cell array of vectors containing scc's, sorted by descending size. The
 length of SCC will equal the number of strongly connected components.  If (V,E) is
 acyclic then SCC will be an Nx1 cell array of single vertices.

 function [SCC,I] = tarjan(N,e)
 also returns an Nx1 vector of indices into SCC corresponding to nodes in v.

 Usage example:
 >> E = sparse([2 3 4 5 5 6 6 7 8 4 9 5 10 6 9], ...
 [1 2 2 3 4 3 5 6 4 8 8 9 9 10 6], ...
 ones(1,15));
 >> c = tarjan(E)
 c = 
     [1x4 double]    [1x2 double]    [7]    [3]    [2]    [1]
 >> c{1}
 ans =
      5     6     9    10
 >> 
 >> 

 Here E is the adjacency matrix for a directed graph, and the nodes with indices
 5, 6, 9, and 10 form the largest strongly connected component in the graph.

0001 function [SCC,I] = tarjan(e)
0002 % function SCC = tarjan(e)
0003 % Implements tarjan's algorithm for a graph with adjacency matrix e.  A value in
0004 % e(i,j) indicates an edge from v(j) to v(i).  If this is transposed from the
0005 % default, well it really shouldn't matter, right?
0006 %
0007 % Returns a cell array of vectors containing scc's, sorted by descending size. The
0008 % length of SCC will equal the number of strongly connected components.  If (V,E) is
0009 % acyclic then SCC will be an Nx1 cell array of single vertices.
0010 %
0011 % function [SCC,I] = tarjan(N,e)
0012 % also returns an Nx1 vector of indices into SCC corresponding to nodes in v.
0013 %
0014 % Usage example:
0015 % >> E = sparse([2 3 4 5 5 6 6 7 8 4 9 5 10 6 9], ...
0016 % [1 2 2 3 4 3 5 6 4 8 8 9 9 10 6], ...
0017 % ones(1,15));
0018 % >> c = tarjan(E)
0019 % c =
0020 %     [1x4 double]    [1x2 double]    [7]    [3]    [2]    [1]
0021 % >> c{1}
0022 % ans =
0023 %      5     6     9    10
0024 % >>
0025 % >>
0026 %
0027 % Here E is the adjacency matrix for a directed graph, and the nodes with indices
0028 % 5, 6, 9, and 10 form the largest strongly connected component in the graph.
0029 
0030 
0031 % using globals because matlab doesn't have shared private variables
0032 global tarjan_v tarjan_SCC tarjan_stack index
0033 
0034 tarjan_SCC={};
0035 tarjan_stack=[];
0036 
0037 N=max(size(e));
0038 
0039 tarjan_v = struct('index',num2cell(zeros(1,N)),'lowlink',num2cell(zeros(1,N)), ...
0040                   'onStack',num2cell(logical(zeros(1,N))));
0041 
0042 index=0;
0043 
0044 % loop through all nodes
0045 for i=1:N
0046     if tarjan_v(i).index==0
0047         strongconnect(i,e);
0048     end
0049 end
0050 
0051 % generate count vector
0052 for j=1:length(tarjan_SCC)
0053     count(j)=length(tarjan_SCC{j});
0054     tarjan_SCC{j}=sort(tarjan_SCC{j}); % for convenience- sort individual components
0055 end
0056 
0057 % sort by decreasing size
0058 [~,q]=sort(count,'descend');
0059 SCC=tarjan_SCC(q);
0060 
0061 for j=1:length(SCC)
0062     I(SCC{j})=j;
0063 end
0064 
0065 
0066 function strongconnect(i,e)
0067 global tarjan_v tarjan_SCC tarjan_stack index
0068 index=index+1;
0069 
0070 % visit the node
0071 tarjan_v(i).index=index;
0072 tarjan_v(i).lowlink=index;
0073 tarjan_stack=[i tarjan_stack];
0074 tarjan_v(i).onStack=true;
0075 
0076 if size(e,2)>=i
0077     out_edges=find(e(:,i));
0078 else % permit operation on rectangular matrices
0079     out_edges=[];
0080 end
0081 
0082 for k=1:length(out_edges)
0083     j=out_edges(k);
0084     % if not visited, visit
0085     if tarjan_v(j).index==0
0086         strongconnect(j,e);
0087         % carry back lowlink, if lower
0088         tarjan_v(i).lowlink=min(tarjan_v([i j]).lowlink);
0089     elseif tarjan_v(j).onStack==true
0090         % carry back index, if lower
0091         tarjan_v(i).lowlink=min([tarjan_v(i).lowlink tarjan_v(j).index]);
0092     end
0093 end
0094 
0095 if tarjan_v(i).lowlink == tarjan_v(i).index
0096     % label a new SCC
0097     theSCC=tarjan_stack(1:find(tarjan_stack==i));
0098     tarjan_stack=tarjan_stack(length(theSCC)+1:end);
0099     [tarjan_v(theSCC).onStack]=deal(false);
0100     tarjan_SCC=[tarjan_SCC {theSCC}];
0101 end
0102 
0103