/*********************************************************  
  TD d'Algorithmique IN202   
  ENSTA  
   
  Mardi 5 Decembre 2000  
   
  Algorithme de Aho-Hopcroft-Ullman  
     
                                        Guillaume Poupard  
*********************************************************/   
#include <stdio.h> 
#include <stdlib.h>  
 
#define infini 10000  
#define zero 0 
  
int min(int a, int b) 
{  
  if (a<b) 
    return a;  
  else 
    return b;  
} 
  
int plus(int a, int b) 
{  
  return a+b; 
}  
 
int etoile(int a)  
{ 
  return 0;  
} 
  
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]=infini; 
}  
 
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++) 
      {  
        H.mat[i][j]=G.mat[i][j]; 
        if (i==j)  
          H.mat[i][j]=min(zero,H.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]=min(H.mat[i][j],  
                        plus(plus(H.mat[i][k], 
                                  etoile(H.mat[k][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++) 
        if (G.mat[i][j]==infini)  
          printf("-- "); 
        else  
          printf("%2d ",G.mat[i][j]); 
      printf("\n");  
    } 
  printf("\n");}  
int main(int argc, char * argv[]) 
{  
  Graphe G,H; 
    
  initGraphe(6,&G); 
  G.mat[0][1]=2;  
  G.mat[0][2]=3; 
  G.mat[0][5]=12;  
  G.mat[1][3]=6; 
  G.mat[1][4]=2;  
  G.mat[2][3]=1; 
  G.mat[2][4]=3;  
  G.mat[3][5]=2; 
  G.mat[4][5]=3;  
  H=AHU(G); 
  imprime(G);  
  imprime(H); 
  exit(0);  
}