Découverte d'un circuit dans un graphe orienté

% GraphTook - 2007-2012 Glotin & Chouchane
% Dyni LSIS USTV - {glotin, mathieu.chouchane} @ univ-tln.fr
 
% Detecte l'existence d'un cycle dans un graphe oriente
function c = contient_cycle(G)
 
nsommets = size(G,1);
 
p = zeros(1, nsommets); % Sommets en cours de traitement
l = zeros(1, nsommets); % Sommets deja visites
 
c = 0;
 
for i = 1 : nsommets
    if(l(i) == 0 && c == 0)
        % On appelle la fonction de parcours en profondeur du graphe en
        % partant de chaque sommet
        [p, l, c] = visite(G, i, p, l);
        % Si on a detecte un cycle, on peut quitter
        if(c == 1)
            return
        end
    end
end
end
 
% La fonction visite effectue un parcours en profondeur du graphe a partir
% d'un sommet racine pour detecter l'existence d'un cycle
function [p, l, c] = visite(G, s, p, l)
% Si on tombe sur un sommet deja visite, c'est qu'un cycle existe
if(p(1,s) == 1)
    c = 1;
    return;
else
    l(1,s) = 1;
    p(1,s) = 1;
    v = voisin(G,s);
    if(~isempty(v))
        % Si un voisin du sommet en cours de traitement a deja ete visite
        % alors c'est qu'un cycle existe
        for i = 1 : length(v)
            if(p(1,v(i)) == 1)
                c = 1;
                return;
            else
                % Appel recursif de la fonction de visite pour s'enfoncer
                % dans le graphe
                [p, l, c] = visite(G, v(i), p, l);
                % Si lors du parcours recursif du graphe on a rencontre
                % un cycle, on quitte la fonction
                if(c == 1)
                    return
                end
            end
        end
        p(1,s) = 0;
    end
    p(1,s) = 0;
    c = 0;
end
end
 
function V = voisin(G,s)
V = find(G(s,:)==1);
end