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


%%%%%%%%%%%%%%%%%%%%%%%%
% PARTIE 1 : "Codage des analyses sur graphe eulériens"
%%%%%%%%%%%%%%%

function zs = alea(n,f)
% tire zs dans 1:n, zs différent de f
aux=randperm(n);zs=aux(1);
if(zs==f);zs=aux(2);end
end % funct

%%%%%%%%%%%%%%%
function p=present(c,f,z)
% teste si couple f z dans c
if vide(f) ; p=0 ;
elseif vide(z) ; p=0 ;
elseif ~prod(in([f,z],c)) ; p=0 ;
else pf=find(c==f); pz=find(c==z);
    pred_pf = pf-1; pred_pz = pz-1;
    p=or(sum(in(pf,pred_pz))>0,sum(in(pz,pred_pf))>0);
end ; end % funct

%%%%%%%%%%%%%%%
function t = vide(L)
% test si L est vide
t = (length(L) == 0);
end % funct

%%%%%%%%%%%%%%%
function p=in(m,a);
% a est un vecteur ligne ou colonne
% in(m,a), m peut etre matrice, teste pour
% chaque element de m s'il se trouve dans a, renvoit p ,
% dim(p)=dim(m), p est boolean, 1 si m(p==1) % est ds a
% ps : le sparce (matrice creuse) n'est pas indispensable
%p = sparse(zeros(size(m,1),size(m,2)));
p = (zeros(size(m,1),size(m,2)));
for i = 1:max(size(a))
    % p = sparse( m==a(i) | p ) ;
    p =  (m==a(i) | p );
end ; end % funct

%%%%%%%%%%%%%%%
function G = adjacence(c)
% c cycle eulÃ©rien ; pour des arcs, generalisé aux aretes
% G avec des arc : G = or(G,G') pour aretes
n = max(c); G = zeros(n,n);
for i = 1:length(c)-1
    x = c(i) ; y = c(i+1); G(x,y)= G(x,y)+1;
    G=or(G,G');
end ;end % funct

%%%%%%%%%%%%%%%
function d=degre(G,s)
d = sum(G(s,:));
end % func

%%%%%%%%%%%%%%%
function P = pair(N)
P = 1-mod(N,2);
end % funct

%%%%%%%%%%%%%%%
function D = touslesdegres(G)
D = sum(G);
end % funct

%%%%%%%%%%%%%%%
function e = euler(G) % renvoie vrai si eulerien
e = prod(pair(touslesdegres(G)));
end % funct

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

%%%%%%%%%%%%%%%
function PC = composantes_connexes(G)
% HG, nov 2010
% G bool, aggreg prÃ©-composante de G
% PC donne en ligne les composantes connexes(G)
% EN AYANT SUPPRIME un eventuel sommet fantome qui rajoute une composante:
sg = size(G,1);
if sg ==0 % vide
    PC = []
elseif G == zeros(sg,sg) ;
    PC = sg;
else
    fantome = 0 ; nCf = 0;
    if size(find(sum(G)==0)~=0);
        fantome = find(sum(G)==0);
        G = supprimer_sommet(G,fantome) ;
        nCf = 1;
    end
    
    n = size(G,1);
    % init Ã  l'ensemble (voisins(s) U s)
    PC = or(G, diag(ones(1,n),0)); % ou faire sum
    i = 0 ;
    while and( (prod(sum(PC,1))~=1), (sum(prod(PC,2))==0))
        % rajout cond arret = existance de G complet , ex h6 en bas :
        % PC = [Â 1   1   1   1   1   1
        %        0   0   1   1   0   0 ]
        i = i + 1;
        intersect = and(PC, ones(size(PC,1),1)*PC(i,:));
        internonvide = (sum(intersect,2)>0); % U(n nonvides)
        %plus rapide que or(A,zeros(size(A))), non distribuÃ©
        agglu = (sum(PC(internonvide,:))>0); % U(des connexes Ã  PC(i))
        PC(internonvide,:)=[]; PC = [ agglu ; PC ] ;
    end % while
    complete = find(prod(PC,2)==1) ; % cas arret 2
    if complete ; PC = ones(1,n); end % if
    if nCf == 1
        PC = [ PC ; zeros(1,n) ];% preferable de mettre '1' sur fantome
    end ; end % ifelse
end % funct

%%%%%%%%%%%%%%%
function test_isole = isole(G,s)
test_isole = degre(G,s) == 0
end % funct

%%%%%%%%%%%%%%%
function G = supprimer_arete(G,x,y)
% supprime l'ARETE
G(x,y) = 0 ; G(y,x)=0 ;
end % funct

%%%%%%%%%%%%%%%
function test_connexe = connexe(G)
test_connexe = size(composantes_connexes(G),1) == 1
end % funct

%%%%%%%%%%%%%%%
function G = supprimer_sommet(G,s)
G(s,:) = [] ; G(:,s) = [];
end % funct

%%%%%%%%%%%%%%%
function c = creation_cycle_euler(n)
% genere un cycle eulerien dans un graphe * non oriente * d'ordre n
% est debeugÃ© :
% 8 7 5 6 2 3 5 8 2 7 4 5 2 1 5 ==> impossible, car on empeche le recrutement de sommet de degre >= n-2, car ils sont de degre max n-1 (sauf pour le sommet initial si on a deja parcouru tous les sommets au moins une fois)
% reste ce beug = [Â 6   4   1   3   6   5   1   6   2   4   3   5   2 => BEUG
% cce(4) = 4   1   2   4   3 % beug !

c=[n];f=c; % on commence Ã  n pour que degre(adjacence(c),z) soit calculable qqs z
do  do z=alea(n,f);
testparite=(degre(adjacence(c),z)<(n-mod(n+1,2)));
until not(present(c,f,z)) & ( (z==n & length(unique(c))~=n) | (degre(adjacence(c),z)<(n-2))) & testparite
% contraintes = z jamais 2 fois par la meme arete,
% et pour n pair:d(x)<n-1 (sinon blocage)
c=[c,z]
f=z ;
until (length(unique(c))==n) & (f==c(1))
end % funct


%%%%%%%%%%%%%
function GA = ajouter_arete(G,s1,s2)
GA=G;
GA(s1,s2)=1;
GA(s2,s1)=1;
end


%%%%%%%%%%%%%%%
function DI = miseajourind(DI,x)
DI =DI + ([ 1:length(DI) ] >= x ) ;
end % funct


%%%%%%%%%%%%%%%
function DI2 = miseajourind2(DI2,x)
DI2 =([ 1:length(DI2) ] >= x ) ;
end % funct
