Code covered by the BSD License

The JSR toolbox

Raphael Jungers (view profile)

10 Oct 2011 (Updated )

Gathers and compares the best methods for the joint spectral radius computation

graphSCC(G)
```function [scnt,C] = graphSCC(G)
%
% GRAPHSCC  Finds the strongly connected components of graph
%           G using Tarjan's algorithm.
%
% [SCNT,C] = GRAPHSCC(G)
%
%  G must be the adjency matrix of a directed graph, i.e. if entry (i,j) is
%    non-zero there is an edge going from i to j
%
%  SCNT is the number of strongly connected components
%
%  C is a vector indicating to which component each node belongs
%
%
% REFERENCES:
%    R.Tarjan,
%      "Depth first search and linear graph algorithms",
%      SIAM J. on Computing, 1(2):146-160, 1972
%    R.Sedgewick,
%      "Algorithms in Java, Third Edition, Part 5: Graph Algorithms",

global S

n = length(G);

for ivert = 1:n
end

scnt=0;
cnt = 0;

S.nel=0;
S.stack = {};
S.isIn = zeros(1,n);

low = -ones(1,n);
number = -ones(1,n);
C = -ones(1,n);

for iv = 1:n
if (number(iv)==-1)
strongConnect(iv);
end
end

function strongConnect(v)
cnt = cnt+1;
low(v)=cnt;
number(v)=cnt;

if (number(w)==-1)
strongConnect(w);
low(v) = min(low(v),low(w));
elseif (number(w)<number(v))
if (S.isIn(w))
low(v) = min(low(v),number(w));
end
end
end
if (low(v) == number(v))
cont = 1;
scnt = scnt+1;

while (S.nel ~= 0 && cont)
top = S.stack{1};
if (number(top) >= number(v) )
w = pop();
C(w) = scnt;
else
cont = 0;
end
end
end
end
end

global S
S.nel = S.nel+1;
S.stack = [{v} S.stack];
S.isIn(v)=1;
end

function  v = pop()
global S
if (S.nel~=0)
v = S.stack{1};
S.nel = S.nel-1;
S.stack(1) = [];
S.isIn(v)=0;
else
v = [];
end

end
```