/*********************************************************   
  TD d'Algorithmique IN202    
  ENSTA   
    
  Mardi 5 Decembre 2000   
    
  Algorithme de fermeture transitive de graphe   
      
                                        Guillaume Poupard  
*********************************************************/   
#include <stdio.h>  
#include <stdlib.h>   
  
struct graphe{   
  int n;  
  int **mat;   
};  
   
typedef struct graphe Graphe;  
   
void initGraphe(int nb, Graphe *G)  
{   
  int i,j;  
  (*G).n=nb;   
  (*G).mat=(int **)malloc(sizeof(int *)*nb);  
  for(i=0;i<nb;i++)   
    (*G).mat[i]=(int *)malloc(sizeof(int)*nb);  
  for(i=0;i<(*G).n;i++)   
    for(j=0;j<(*G).n;j++)  
      (*G).mat[i][j]=0;   
}  
   
Graphe AHU(Graphe G)  
{   
  Graphe H;  
  int i,j,k;   
    
  initGraphe(G.n,&H);   
  for(i=0;i<G.n;i++)  
    for(j=0;j<G.n;j++)   
      if (i==j)  
        H.mat[i][j]=1;   
      else  
        H.mat[i][j]=G.mat[i][j];   
  for(k=0;k<G.n;k++)  
    for(i=0;i<G.n;i++)   
      for(j=0;j<G.n;j++)  
        H.mat[i][j]=H.mat[i][j] | (H.mat[i][k] & H.mat[k][j]);   
  return H;  
}   
  
void imprime(Graphe G)   
{  
  int i,j;   
  printf("    ");  
  for(i=0;i<G.n;i++)   
    printf("%2d ",i);  
  printf("\n");   
  for(i=0;i<G.n;i++)  
    {   
      printf("%2d  ",i);  
      for(j=0;j<G.n;j++)   
        printf(" %d ",G.mat[i][j]);  
      printf("\n");   
    }  
  printf("\n");   
}  
       
int main(int argc, char * argv[])  
{   
  Graphe G,H;  
     
  initGraphe(7,&G);  
  G.mat[0][1]=1;   
  G.mat[0][3]=1;  
  G.mat[3][1]=1;   
  G.mat[1][4]=1;  
  G.mat[4][3]=1;
  G.mat[2][4]=1;  
  G.mat[2][5]=1;   
  G.mat[5][5]=1;  
  H=AHU(G);   
  imprime(G);  
  imprime(H);   
  exit(0);  
}