% GraphTook - 2007-2012 Glotin & Chouchane
% Dyni LSIS USTV - { glotin, mathieu.chouchane} @ univ-tln.fr

function CC = tarjan(G)

S = []; %pile
CC = []; %toutes les composantes fortement connexes
index = zeros(1, size(G,1)); %date de découverte du sommet (rang)
index_accessible = zeros(1, size(G,1)); %rang d'attache du sommet
idx = 1;

% Parcours des sommets non marqués
for i = 1 : size(G,1)
    if(index(i) == 0)
        [CC S idx index index_accessible] = strongconnect(CC, G, i, S, idx, index, index_accessible);
    end
end
end

function [C S idx index index_accessible] = strongconnect(C, G, v, S, idx, index, index_accessible)
index(v) = idx;
index_accessible(v) = idx;
idx = idx+1;
S = push(S,v); %ajouter le sommet courant à la pile

% Liste les sommets adjacents au sommet courant
n = voisin(G,v);

% Parcours récursif
for i = 1:length(n)
    if(index(n(i)) == 0)
        [C, S idx index index_accessible] = strongconnect(C, G, n(i), S, idx, index, index_accessible);
        index_accessible(v) = min(index_accessible(v), index_accessible(n(i)));
    elseif (~isempty(find(S == n(i), 1)))
        index_accessible(v) = min(index_accessible(v), index(n(i)));
    end
end

% Le sommet est une racine, on calcule la composante fortement connexe associée
if(index_accessible(v) == index(v))
    cc = []; %composante fortement connexe issue du sommet
    if(~isempty(S))
        [tmp S] = pop(S);
        cc = [cc tmp];
    end
    while(~isempty(S) && tmp ~= v)
        [tmp S] = pop(S);
        cc = [cc tmp];
    end
    if(~isempty(cc))
        % Les composantes connexes n'ont pas toutes
        % la même longueur. On complète donc la ligne
        % avec des 0.
        C = [C ; cc zeros(1,size(G,1) - length(cc))];
    end
end
end

function V = voisin(G,s)
V = find(G(s,:)==1);
end

% empiler
function p = push(p, n)
p = [p n];
end

% dépiler
function [n, p] = pop(p)
n = [];
if(~isempty(p))
    n = p(end);
    p = p(1:end-1);
end
end
