Subversion Repositories wimsdev

pari_header=est_connexe(a)=my(n=#a,b=(1.+a)^(n-1));for(x=1,n,if(b[1,x]==0,return(0)));1\
/* graphe_connexe */\
graphe_connexe(n)={\
  my(a=matrix(n,n),i,j);\
  while(!est_connexe(a),i=1+random(n);j=1+random(n);if(i!=j,a[i,j]=a[j,i]=1));\
  a\
};\
\
/* M est la matrice d'un graphe connexe */\
graphe_eulerien(M)={\
  my(x,y,z,a=M,n=#a);\
  my(impdeg=vector(n,i,sum(j=1,n,a[i,j])%2));\
  while (sum(i=1,n,impdeg[i]),[x,y]=select(x->x,impdeg,1);\
    if (a[x,y],\
      z=1+(x==1)+(y==2);\
      if(a[x,z] && a[y,z], a[x,y]=a[y,x]=0,\
        a[x,z]=a[z,x]=1-a[x,z];a[y,z]=a[z,y]=1-a[y,z]),\
      a[x,y]=a[y,x]=1);\
      impdeg[x]=impdeg[y]=0\
  );\
  a\
};\
\
est_eulerien(a)=est_connexe(a)&&!vector(#a,i,sum(j=1,#a,a[i,j])%2)\
\
/* a  est la matrice d'un graphe eulerien trouve un cycle eulerien sur a */\
\
cycle_eulerien(a)={\
  my(n=#a,deg=vector(n,i,sum(j=1,n,a[i,j])),m=sum(i=1,n,deg[i])/2);\
  my(cdeg=vector(n),cyc=vector(m+1),c,x,x0,nb);\
  cyc[1]=nb=1;\
  while(nb <= m,\
   [c]=select(x->x&&cdeg[x]<deg[x],cyc,1);\
   x0 = x = cyc[c];\
   until (x==x0,\
     nb++; cdeg[x]++; y = 1; while (!a[x,y] || deg[y]==cdeg[y], y++);\
     cdeg[y]++; forstep (i=nb,c+1,-1,cyc[i]=cyc[i-1]);\
     a[x,y]--;a[y,x]--;\
     cyc[c]=y; x = y);\
  );\
  cyc\
};\