/*********************************************************  
  TD d'Algorithmique IN202 
  ENSTA  
 
  Mardi 5 Decembre 2000  
 
  Algorithme "speculatif"  
   
                                        Guillaume Poupard  
*********************************************************/ 
#include <stdio.h>  
#include <stdlib.h> 
  
#define empty 0 
#define epsilon 1  
#define infini 10000 
  
double max(double a, double b) 
{  
  if ((a==infini) || (b==infini)) 
    return infini;  
  if (a>b)    
    return a;  
  else 
    return b;  
} 
  
double fois(double a, double b) 
{  
  if ((a==infini) || (b==infini)) 
    return infini;
  else  
    return a*b;   
} 
  
double etoile(double a) 
{  
  if (a<=1) 
    return 1;  
  else 
    return infini;  
} 
  
struct graphe{ 
  int n;  
  double **mat; 
};  
 
typedef struct graphe Graphe;  
 
void initGraphe(int nb, Graphe *G)  
{ 
  int i,j;  
  (*G).n=nb; 
  (*G).mat=(double **)malloc(sizeof(double *)*nb);  
  for(i=0;i<nb;i++) 
    (*G).mat[i]=(double *)malloc(sizeof(double)*nb);  
  for(i=0;i<(*G).n;i++) 
    for(j=0;j<(*G).n;j++)  
      (*G).mat[i][j]=empty; 
}  
 
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]=max(epsilon,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]=max(H.mat[i][j],fois(fois(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("%5.2f ",G.mat[i][j]); 
      printf("\n");  
    } 
  printf("\n");  
} 
          
     
int main(int argc, char * argv[])  
{ 
  Graphe G,H;  
   
  initGraphe(4,&G);
  G.mat[0][0]=1.0; 
  G.mat[1][1]=1.0;  
  G.mat[2][2]=1.0; 
  G.mat[3][3]=1.0;  
  G.mat[0][1]=0.2; 
  G.mat[1][0]=5;  
  G.mat[1][2]=10.0; 
  G.mat[2][1]=0.1;  
  G.mat[1][3]=0.5; 
  G.mat[3][1]=2;  
  G.mat[3][2]=20.1;  /* au lieu de 20 */ 
  H=AHU(G);  
  imprime(G); 
  imprime(H);  
  exit(0); 
}