CHEMIN CRITIQUE PAR LA METHODE PERT

/******************************/
/*   El Antri Abdellah        */
/*   Sous licence GNU         */
/******************************/

/*****************************/
/* Tester sous linux         */
/* compilation: cc ro.c -o ro*/
/* Execution: ./ro           */
/*****************************/

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

#define MAX_INT 65535

#define max(x,y) x>y?x:y
#define min(x,y) x<y?x:y

typedef struct {int date_plutot, date_plutard, marge, num_tache;}tache;

tache *projet;
int **matrice;

int main()
{
int chemin[100];
int associe [100];
int som_ch = 0;
int nbr_tache;
int i,j,k;
int num_succ;
int nbr_succ;
int duree;
int som = 0;
int *pile;

printf("\n Donner le nombre des taches: ");
scanf("%d",&nbr_tache);

projet = (tache *)malloc((nbr_tache + 2) * sizeof(tache));
if(projet == NULL)
  {
  printf(" \n Impossible d'allouer de l'espace pour projet");
  exit(1);
  }
  else printf("\n Espace allouer avec succe");


matrice = (int **)malloc((nbr_tache + 2) * sizeof(int *));

for(i = 0; i < nbr_tache + 2; i++)
   {
   matrice[i] = (int *)malloc((nbr_tache + 2) * sizeof(int));	   
   }

for(i = 0; i < nbr_tache + 2; i++)
    for(j = 0; j < nbr_tache + 2; j++)
       {
	matrice[i][j] = -1;
       }
matrice[0][1] = 0;

pile = (int *)malloc((nbr_tache +2) * sizeof(int));

for(i = 1; i < nbr_tache ; i++)
   {
   printf(" \n Donner le nombre des taches qui vient apres %d:",i);
   scanf("%d",&nbr_succ);
   for(j = 0; j < nbr_succ; j++)
     {
     printf(" Donner le numero du successeur N %d:", j+1);
     scanf("%d", &num_succ);
     printf(" Donner la duree entre %d et %d: ", i , num_succ);
     scanf("%d", &duree);	     
     matrice[i][num_succ] = duree; 
     }
   }
matrice[nbr_tache][nbr_tache+1] = 1;

// date au plutot
projet[0].date_plutot = 0;

for(j = 1; j < nbr_tache + 2; j++)
   {
   projet[j].date_plutot = 0;
   for(i = 0; i < j; i++)
      {
      if(matrice[i][j] != -1)
         {
	 projet[j].date_plutot = max(projet[j].date_plutot,
			             projet[i].date_plutot + matrice[i][j]);
	 }
      }	      
   printf(" \n date_plutot de %d: %d", j, projet[j].date_plutot);
   }

printf("\n Tapper une touche ...");
scanf("%d", &i);
projet[nbr_tache+1].date_plutard = projet[nbr_tache+1].date_plutot;

// date au plutard
for(i = nbr_tache ; i >= 0; i--)
   {
   projet[i].date_plutard = MAX_INT;	   
   for(j = i + 1; j <= nbr_tache + 1; j++)
      {
      if(matrice[i][j] != -1)
        projet[i].date_plutard  = min (projet[j].date_plutard  -  matrice[i][j],
			               projet[i].date_plutard); 
      }	      
   printf(" \n date_plutard de %d: %d", i, projet[i].date_plutot);
   }
printf("\n Tapper une touche ...");
scanf("%d", &i);

// marges
for(i=0; i < nbr_tache +2; i++)
   {
    projet[i].marge = projet[i].date_plutard - projet[i].date_plutot;
    printf("\n La marge de %d: %d", i, projet[i].marge);
   }

printf("\n Tapper une touche ...");
scanf("%d", &i);

associe[som_ch] = -1;
pile[som] = 1;
som ++;
som_ch ++;

while(som > 0)
	{
	som --;
	i = pile[som];
	chemin[som_ch] = i;
	som_ch ++;
	for(j = i+1; j < nbr_tache + 2; j++)
   	  if(matrice[i][j] != -1)	
      	   {
      	   if(projet[i].marge == 0 && projet[j].marge == 0 )
        	{
		if(j != nbr_tache + 1)	
		   {
		   pile[som] = j;
		   associe[som] = i;
		   som++; 
		   }
                  else 
	             {
		     printf("\n ==> ");	     
		     for (k = 1; k < som_ch; k++)
			 printf(" %d ", chemin[k]);
		     for (k = 0; k < som_ch; k++)
		          if(som > 0 && chemin[k] ==  associe[som - 1])
			  {
			  som_ch = k + 1;
			  break;
			  }	
		     }		     
     	        }	
	   }
	}	

printf("\n");
return 0;
}