Programmes en C

 
/* -*/

#define Nmax 100

typedef int Sommet ;

typedef Sommet GrapheMat[Nmax][Nmax];

int ExisteChemin (int i,int j, int n, GrapheMat g)
{
    int       k;
    GrapheMat x,y;

    Copy(g, x, n);
    k = 1;
    while (x[i][j] == 0 && k <= n){
        ++ k;
        Produit(n, x, g, y);
        Copy(y, x, n);
    }
    return (x[i][j] != 0);
}

void Phi (GrapheMat g, int n, int x) 
{                         /* -*/
    int     u,v;

    for(u = 1; u <= n; ++u)
        if (g[u][x] == 1)
            for (v = 1;v <= n; ++v)
               if (g[x][v] == 1) 
                   g[u][v] = 1;
}

void FermetureTransitive (GrapheMat g, int n)
{
    int     x;

    for (x = 1; x <= n; ++x) 
        Phi(g, n, x);
}

#define Sucmax   50    /* - */
#define Omega    -1

typedef Sommet GrapheSuc[Nmax][Sucmax];

void TransformMatSuc (GrapheMat g, int n, GrapheSuc succ)
{
    int     i,j,k;

    for (i = 1; i <= n; ++i){
        k = 1;
        for (j = 1; j <= n; ++j)
            if (g[i][j] == 1){
                succ[i][k] = j;
                ++k;
            }
        succ[i][k] = Omega;
    }
}

struct Cellule {          /* - */
    Sommet          contenu;
    struct Cellule  *suivant;
};

typedef struct Cellule   Cellule;
typedef struct Cellule   *Liste;           
typedef Liste            GraphePoint[Nmax] ;

void TransformSucPoint (GrapheSuc succ, int n, GraphePoint gpoint)
{
    int     i;
    Liste   a;
    Sommet  x;

    for (x = 1; x <= n; ++x) {
        gpoint[x] = NULL;
        i = 1;
        while (succ[x][i] != Omega) {  
            a = (Liste) malloc(sizeof(Cellule));
            a -> contenu = succ[x][i];
            a -> suivant = gpoint[x];
            gpoint[x] = a;
            ++ i;
        }
    }
}

/* -
 * -
*/

typedef Sommet   Arbo[Nmax];

void SuccEnPere (GrapheSuc succ, int n, Sommet r, Arbo pere)
{
    int     k;
    Sommet  i,j;

    pere[r] = r;
    for (i = 1; i <= n; ++i){
        k = 1;
        j = succ[i][k];
        while (j != Omega){
            pere[j] = i;
            ++k;
            j = succ[i][k];
        }
    }
}

void Numprefixe (Sommet x, GrapheSuc succ, SomVect numero, int *num)
{
    int      i;
    Sommet   y;

    numero[x] = *num;
    ++ *num;
    for(i = 1; succ[x][i] != Omega; ++i)
        Numprefixe(succ[x][i], succ, numero, num);
}

void ArbPlusCourt (GrapheSuc succ, int n, Sommet x, Arbo pere)
{                          /* - */
    Fil      f;
    Sommet   u,v;
    int      i;
    
    FaireFil(&f);
    for (u = 1; u <= n; ++u) 
        pere[u] = Omega;
    Fajouter(x, &f);
    pere[x] = x;
    u = Fvaleur(&f);
    while ( !Fvide (&f) ) {
        u = Fvaleur(&f);
        Fsupprimer (&f);
        for(i = 1; succ[u][i] != Omega; ++i){
            v = succ[u][i];
            if (pere[v] == Omega){
                pere[v] = u;
                Fajouter(v,&f);
            } 
        }
    } 
}

void TremauxRec (Sommet u, Arbo pere, GrapheSuc succ, int n)
{                         /* - */
    int    k;
    Sommet v;

    for (k = 1; succ[u][k] != Omega; ++k) {
        v = succ[u][k];
        if (pere[v] == Omega) {
            pere[v] = u;
            TremauxRec(v, pere, succ, n);
        }
    }
}

void TremauxPil (GrapheSuc succ, int n, Sommet x, Arbo pere)
{                   /* - */

    Pile     p;
    Sommet   i,u,v;
    int      j;

    for (i = 1; i <= n; ++i)
         pere[i] = Omega;
    FairePile (&p);
    Pajouter (x, &p);
    pere[x] = x;
    while ( !Pvide(&p) ) {
        u = Pvaleur (&p);
        j = 1; 
        v =succ[u][j]; 
        while (v != Omega && pere[v] != Omega) {
            ++j;
            v = succ[u][j];
        };
        if (v != Omega) {
            pere[v] = u;
            Pajouter (v, &p);
        } else
            Psupprimer (&p);
        
    }
}

typedef int    SomVect[Nmax];      /* - */

Sommet PointAttache(Sommet u, GrapheSuc succ, int n, SomVect at)
{
    int      k;
    Sommet   v, w, mi;

    mi = u;
    at[u] = u;
    for (k = 1; succ[u][k] != Omega; ++k) {
        v = succ[u][k];
        if (at[v] == Omega) 
            w = PointAttache(v, succ, n, at);
        else
            w = v;
        if (w < mi)
            mi = w;
    }
    at[u] = mi;
    return mi;
}

/*- */
void Supprimer (Sommet u, int nu, SomVect numComp,
                               GrapheSuc succ, int n)
{
    Sommet   v;
    int      k;

    numComp[u] = nu;
    for (k = 1; succ[u][k] != Omega; ++k){
        v = succ[u][k];
        if (v > u && numComp[v] == 0)
            Supprimer(v, nu, numComp, succ, n);
    }
}

void PointAttache1(Sommet u, GrapheSuc succ, int n,
                   SomVect at, SomVect numComp, int *nu)
{
    int    k;
    Sommet v,w,mi;

    at[u] = u;
    for (k = 1; succ[u][k] != Omega; k++){
        v = succ[u][k];
        if (at[v] == Omega){ 
            PointAttache1 (v, succ, n, at, numComp, nu);
            at[u] = min (at[u], at[v]);
        }else
            if (numComp[v] == 0)
                 at[u] = minimum (at[u], v);
     }
     if (u == at[u]) {
          ++ *nu;
          Supprimer(u, *nu, numComp, succ, n);
      }
}
void CompCon (GrapheSuc succ, int n,  SomVect numComp)
{   
    Sommet   u;
    int      num;
    SomVect  at;

    for (u = 1; u <= n; ++u){
        numComp[u] = 0;
        at[u] = Omega;
    }
    
    num = 0;
    for (u = 1; u <= n ; ++u) 
        if (numComp[u] == 0 && at[u] == Omega)            
            PointAttache1(u,  succ, n, at, numComp, &num);
}