// gcc -Wall g1g2g3g4.c -g -std=gnu99
#include<stdio.h>
#define nba 7
typedef enum {A, B, C, D, E, nbs} sommet; // A=0, B=1, C=2, D=3, E=4, nbs=5

typedef enum {faux,vrai} bool, graphe1[nbs][nbs];
graphe1 g1={{0, 1, 1, 0, 0},  //       A->B A->C
            {0, 0, 1, 0, 1},  //            B->C      B->E
            {1, 0, 0, 0, 1},  //  C->A                C->E
            {0, 0, 0, 0, 0},  //
            {1, 0, 0, 0, 0}}; //  E->A

typedef int graphe2[nba+nbs+1];
graphe2 g2={/* A-> */ B, C,
            /* B-> */ C, E,
            /* C-> */ A, E,
            /* E-> */ A,
            0,2,4,6,6,7};
#define lim (g2+nba)

typedef struct maillon maillon, *liste, *graphe3[nbs];
struct maillon { sommet s; liste suite; } m1={C,0}, m2={B,&m1}, m3={E,0}, m4={C,&m3}, m5={E,0}, m6={A,&m5}, m7={A,0};
graphe3 g3={&m2,&m4,&m6,0,&m7};

typedef sommet graphe4[nba*2];
graphe4 g4={A, B, C, E, A, C, B,   // origines des arcs
            B, C, E, A, C, A, E};  // extrémités des arcs
#define ext (g4+nba)

typedef int suite_tete[nba+nbs];
#define tete (suite+nba)
void setsuite(graphe4 g4, suite_tete suite)
{ for(sommet s=0;s<nbs;s++) tete[s]=-1;
  for(int i=nba;i--;) suite[i]=tete[g4[i]], tete[g4[i]]=i;
}

void affarc(sommet s, sommet t) { printf("%c->%c ",s+'A',t+'A'); }
void affg1(graphe1 g1)
{ for(sommet s=0;s<nbs;s++)       //  pour tout sommet s
   for(sommet t=0;t<nbs;t++)      //    pour tout sommet t
   if(g1[s][t])                   //      si s->t est dans g1
   affarc(s,t);                   //        on écrit s->t
  printf("\n");
}
void affg2(graphe2 g2)
{ for(sommet s=0;s<nbs;s++)
   for(int i=lim[s];i<lim[s+1];i++) 
   affarc(s,g2[i]);
  printf("\n");
}
void affg3(graphe3 g3)
{ for(sommet s=0;s<nbs;s++)
   for(liste p=g3[s];p;p=p->suite)
   affarc(s,p->s);
  printf("\n");
}
void affg4(graphe4 g4)
{ for(int i=0;i<nba;i++) affarc(g4[i],ext[i]);
  printf("\n");
}
void affg5(graphe4 g4, suite_tete suite)
{ for(sommet s=0;s<nbs;s++)
   for(int i=tete[s];i>=0;i=suite[i])
   affarc(s,ext[i]);
  printf("\n");
}

int deg_sor1(graphe1 g1, sommet s)
{ int c=0;
  for(sommet t=0;t<nbs;t++) c+=g1[s][t];
  return c;
}
int deg_sor2(graphe2 g2, sommet s) { return lim[s+1]-lim[s]; }
int deg_sor3(graphe3 g3, sommet s)
{ int c=0;
  for(liste p=g3[s];p;p=p->suite) c++;
  return c;
}
int deg_sor4(graphe4 g4, sommet s)
{ int c=0;
  for(int i=0;i<nba;i++) c+=g4[i]==s;
  return c;
}
int deg_sor5(graphe4 g4, suite_tete suite, sommet s)
{ int c=0;
  for(int i=tete[s];i>=0;i=suite[i]) c++;
  return c;
}
void g1g4(graphe1 g1, graphe4 g4)
{ int j=0;
  for(sommet s=0;s<nbs;s++)
   for(sommet t=0;t<nbs;t++)
   if(g1[s][t])
   g4[j]=s, ext[j++]=t;
}
void g2g4(graphe2 g2, graphe4 g4)
{ for(sommet s=0;s<nbs;s++)
   for(int i=lim[s];i<lim[s+1];i++) 
   g4[i]=s, ext[i]=g2[i];
}
void g3g4(graphe3 g3, graphe4 g4)
{ int j=0;
  for(sommet s=0;s<nbs;s++)
   for(liste p=g3[s];p;p=p->suite)
   g4[j]=s, ext[j++]=p->s;
}
void g4g1(graphe4 g4, graphe1 g1)
{ for(sommet s=0;s<nbs;s++) for(sommet t=0;t<nbs;t++) g1[s][t]=0;
  for(int i=0;i<nba;i++) g1[g4[i]][ext[i]]=1;
}
void g4g2(graphe4 g4, graphe2 g2)
{ for(sommet s=0;s<=nbs;s++) lim[s]=0;
  for(int i=0;i<nba;i++) lim[g4[i]]++;
  for(sommet s=0;s<nbs;s++) lim[s+1]+=lim[s];
  for(int i=nba;i--;) g2[--lim[g4[i]]]=ext[i];
}
void g4g3(graphe4 g4, graphe3 g3, liste p)
{ for(sommet s=0;s<nbs;s++) g3[s]=0;
  for(int i=0;i<nba;i++)
  { liste *l=g3+g4[i];
    *p=(maillon){ext[i],*l};
    *l=p++;
  }
}

int main()
{ suite_tete suite;
  setsuite(g4,suite);
  affg1(g1);
  affg2(g2);
  affg3(g3);
  affg4(g4);
  affg5(g4,suite);
  for(sommet s=0;s<nbs;s++) printf("d°(%d)=%d ",s,deg_sor1(g1,s)); printf("\n"); 
  for(sommet s=0;s<nbs;s++) printf("d°(%d)=%d ",s,deg_sor2(g2,s)); printf("\n"); 
  for(sommet s=0;s<nbs;s++) printf("d°(%d)=%d ",s,deg_sor3(g3,s)); printf("\n"); 
  for(sommet s=0;s<nbs;s++) printf("d°(%d)=%d ",s,deg_sor4(g4,s)); printf("\n"); 
  for(sommet s=0;s<nbs;s++) printf("d°(%d)=%d ",s,deg_sor5(g4,suite,s)); printf("\n"); 
  graphe4 h4;
  g1g4(g1, h4), affg4(h4);
  g2g4(g2, h4), affg4(h4);
  g3g4(g3, h4), affg4(h4);
  maillon p[nba];
  graphe1 h1; g4g1(g4, h1); affg1(h1);
  graphe2 h2; g4g2(g4, h2); affg2(h2);
  graphe3 h3; g4g3(g4, h3, p); affg3(h3);
  return 0;
}