/***************************************************************************
                             Recherche Op‚rationnelle
                                     TP4

Olivier SANNIER
Denis VANPEPERSTRAETE
***************************************************************************/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <ctype.h>
#include <io.h>
#include <fcntl.h>
#include <time.h>
#include <string.h>

// d‚finition de la structure pour la repr‚sentation liste chaŒn‚e
typedef struct Elem {
               int val;               // destination de l'arc
               int poids;             // poids de l'arc
               struct Elem *lien;
               } elem;

/*------------------------------------------------------------------------
  ajout_arc

  Cette fonction ajoute un arc … un graphe repr‚sent‚ par un tableau
  contenant des pointeurs sur des listes chaŒn‚es d'entiers repr‚sentants
  les arcs du graphe.
  L'ajout est effectu‚ dans l'ordre et non pas en d‚but de liste.
  Les paramŠtres transmis sont :
  un pointeur sur le d‚but du tableau de pointeurs et les sommets de d‚part
  et d'arriv‚e du lien … ajouter.
--------------------------------------------------------------------------*/
void ajout_arc(elem **tableau, int x, int y, int poids)
{
elem *actuel, *prec, *temp;

  if (tableau!=NULL)
  {
    temp=(elem *)malloc(sizeof(elem));
    temp->val=y;
    temp->poids=poids;
    temp->lien=NULL;

    prec=NULL;
    actuel=tableau[x];

    while ((actuel!=NULL) && (actuel->val<y))
    {
      prec=actuel;
      actuel=actuel->lien;
    }
	if ((actuel!=NULL)&&(actuel->val==y))
    {
      free(temp);
    }
    else
    {
      temp->lien=actuel;
      if (prec==NULL)
      {
        tableau[x]=temp;
      }
      else
      {
        prec->lien=temp;
      }
    }
  }
  else
  {
    printf("Vous devez d'abord passer par la fonction de saisie\n");
    getch();
  }
}

/*------------------------------------------------------------------------
  saisie_probleme

  Cette fonction cr‚e un graphe repr‚sent‚ par un tableau contenant des
  pointeurs sur des listes chaŒn‚es d'entiers repr‚sentants les arcs du
  graphe. Ce graphe repr‚sente le problŠme qui va ˆtre saisi
  Les paramŠtres transmis sont :
  un pointeur sur le pointeur de d‚but du tableau de pointeurs (ainsi pass‚
  par paramŠtre) et le nombre de sommets (lui aussi pass‚ par paramŠtre).
--------------------------------------------------------------------------*/
void saisie_probleme(elem ***tableau, int *nbsommets)
{
int i,
    j,
    tache,
    *poids;
char ligne[128], nombre[128], *esp;
elem *actuel;

  scanf("%d", nbsommets);

  *nbsommets+=2;         // 2 sommets virtuels en plus

  *tableau=(elem **)malloc( (*nbsommets) * sizeof(elem *));
  poids=(int *)malloc(*nbsommets*sizeof(int));
  for(i=0;i<*nbsommets;i++)
  {
    (*tableau)[i]=NULL;
    poids[i]=0;
  }

  for(i=0;i<(*nbsommets)-1;i++)
  {
    printf("Num‚ro de la tƒche … ajouter : ");
    scanf("%d", &tache);
    printf("Dur‚e de cette tƒche : ");
    scanf("%d", &(poids[i]));
    printf("Contrainte(s) pour r‚aliser cette tƒche : ");
    fgets(ligne, 126, stdin);
    printf("%s\n", ligne);
    // dans ligne on a un la (les) contrainte(s)
    j=0;
    while (strlen(ligne)!=0)
    {
      esp=strchr(ligne, ' ');
      strncpy(nombre, ligne, esp-ligne);
      nombre[esp-ligne]='\0';

      switch (j)
      {
        case 0  : tache=atoi(nombre);    // on a lu le nø de la tƒche
                  break;
        case 1  : poids[tache]=atoi(nombre);// on a lu le poids de la tache
                  break;
        default : ajout_arc(*tableau, atoi(nombre), tache, 0);
      }
      j++;
      strcpy(ligne, esp+1);
    }
    if (j==2)
      ajout_arc(*tableau, 0, tache, 0);
  }

  for(i=1;i<(*nbsommets)-1; i++)
    if ( (*tableau)[i]==NULL )
      ajout_arc(*tableau, i, (*nbsommets)-1, poids[i]);
    else
    {
      actuel=(*tableau)[i];
      while(actuel!=NULL)
      {
        actuel->poids=poids[i];
        actuel=actuel->lien;
      }
    }

  free(poids);
}

/*------------------------------------------------------------------------
  lecture_probleme

  Cette fonction cr‚e un graphe repr‚sent‚ par un tableau contenant des
  pointeurs sur des listes chaŒn‚es d'entiers repr‚sentants les arcs du
  graphe. Elle lit les informations n‚cessaires dans un fichier pour cr‚er
  ce graphe repr‚sentatif du problŠme d'ordonnancement.
  Les paramŠtres transmis sont :
  un pointeur sur le pointeur de d‚but du tableau de pointeurs (ainsi pass‚
  par paramŠtre) et le nombre de sommets (lui aussi pass‚ par paramŠtre).
--------------------------------------------------------------------------*/
void lecture_probleme(elem ***tableau, int *nbsommets)
{
FILE *fic;
char ligne[128],
     fichier[128],
     nombre[128],
     *esp;
int i,
    j,
    tache,
    *poids;
elem *actuel;

  printf("\nNom du fichier … ouvrir : ");
  scanf("%s", fichier);

  fic=fopen(fichier, "r");
  if (fic!=NULL)
  {
    fscanf(fic, "%d", nbsommets);

    *nbsommets+=2;         // 2 sommets virtuels en plus

    *tableau=(elem **)malloc( (*nbsommets) * sizeof(elem *));
    poids=(int *)malloc(*nbsommets*sizeof(int));
    for(i=0;i<*nbsommets;i++)
    {
      (*tableau)[i]=NULL;
      poids[i]=0;
    }

    for(i=0;i<(*nbsommets)-1;i++)
    {
      fgets(ligne, 128, fic);
      printf("%s\n", ligne);
      // dans ligne on a un truc de type : tache, poids, contrainte(s)
      j=0;
      while (strlen(ligne)!=0)
      {
        esp=strchr(ligne, ' ');
        strncpy(nombre, ligne, esp-ligne);
        nombre[esp-ligne]='\0';

        switch (j)
        {
          case 0  : tache=atoi(nombre);    // on a lu le nø de la tƒche
                    break;
          case 1  : poids[tache]=atoi(nombre);// on a lu le poids de la tache
                    break;
          default : ajout_arc(*tableau, atoi(nombre), tache, 0);
        }
        j++;
        strcpy(ligne, esp+1);
      }
      if (j==2)
        ajout_arc(*tableau, 0, tache, 0);
    }

    for(i=1;i<(*nbsommets)-1; i++)
      if ( (*tableau)[i]==NULL )
        ajout_arc(*tableau, i, (*nbsommets)-1, poids[i]);
      else
      {
        actuel=(*tableau)[i];
        while(actuel!=NULL)
        {
          actuel->poids=poids[i];
          actuel=actuel->lien;
        }
      }

    fclose(fic);
    free(poids);
  }
  else
    printf("Fichier introuvable\n");

  getch();
}

/*------------------------------------------------------------------------
  affgraph

  Cette fonction affiche un graphe repr‚sent‚ par un tableau contenant des
  pointeurs sur des listes chaŒn‚es d'entiers repr‚sentants les arcs du
  graphe.
  Les paramŠtres transmis sont :
  un pointeur sur le d‚but du tableau de pointeurs et le nombre de sommets
  du graphe.
--------------------------------------------------------------------------*/
void affgraph(elem **tableau, int nbsommets)
{
int i;
elem *actuel;

  clrscr();
  for(i=0;i<nbsommets;i++)
  {
    printf("Sommet : %d\n", i);
    actuel=tableau[i];
    if (actuel==NULL)
      printf("\tAucun arc\n");
    else
    {
      do
      {
        printf("\tArc vers %d, poids %d\n", actuel->val, actuel->poids);
        actuel=actuel->lien;
      }while (actuel!=NULL);
    }
  }
}

/*------------------------------------------------------------------------
  calcplustot

  cette fonction va calculer les dates au plus t“t de maniŠre r‚cursive :
  Elle trouve tous les successeurs du sommet qu'on lui a indiqu‚.
  Elle v‚rifie alors si leur date au plus t“t doit ˆtre mise … jour puis
  se rappelle avec comme sommet origine le sommet qu'elle vient de traiter.
---------------------------------------------------------------------------*/
void calcplustot(int **court, int *plustot, int depart, int nbsommets)
{
int j;

  for(j=0;j<nbsommets;j++)
  {
    if (court[depart][j]!=-1)
    {
      if (court[depart][j]+plustot[depart] > plustot[j])
        plustot[j] =court[depart][j]+plustot[depart];
      calcplustot(court, plustot, j, nbsommets);
    }
  }
}

/*------------------------------------------------------------------------
  calcplustard

  cette fonction va calculer les dates au plus tard de maniŠre r‚cursive :
  Elle trouve tous les pr‚d‚cesseurs du sommet qu'on lui a indiqu‚.
  Elle v‚rifie alors si leur date au plus tard doit ˆtre mise … jour puis
  se rappelle avec comme sommet origine le sommet qu'elle vient de traiter.
---------------------------------------------------------------------------*/
void calcplustard(int **court, int *plustard, int arrivee, int nbsommets)
{
int i;

  for(i=0;i<nbsommets;i++)
  {
    if (court[i][arrivee]!=-1)
    {
      if (plustard[arrivee]-court[i][arrivee] < plustard[i])
        plustard[i] =plustard[arrivee]-court[i][arrivee];
      calcplustard(court, plustard, i, nbsommets);
    }
  }
}

/*------------------------------------------------------------------------
  dates

  cette fonction va calculer les dates au plus t“t et au plus court.
---------------------------------------------------------------------------*/
void dates(elem **graphe, int nbsommets)
{
int **court,
    *plustard,
    *plustot,
    i,
    j;

elem *actuel;

  court=(int **)malloc(nbsommets*sizeof(int *));
  plustard=(int *)malloc(nbsommets*sizeof(int));
  plustot=(int *)malloc(nbsommets*sizeof(int));
  for(i=0;i<nbsommets;i++)
  {
    plustot[i]=0;
    plustard[i]=32767;
    court[i]=(int *)malloc(nbsommets*sizeof(int));
    for(j=0;j<nbsommets;j++)
    {
      actuel=graphe[i];
      while ((actuel!=NULL)&&(actuel->val!=j))
      {
        actuel=actuel->lien;
      }
      if (actuel==NULL)
        court[i][j]=-1;
      else
        court[i][j]=actuel->poids;

    }
  }

  for(i=0;i<nbsommets;i++)
  {
    for(j=0;j<nbsommets;j++)
      if (court[i][j]!=-1)
        printf("%2d", court[i][j]);
      else
        printf(" x");
    printf("\n");
  }

  //Ici, on d‚termine les dates au plus t“t.
  plustot[0]=0;
  calcplustot(court, plustot, 0, nbsommets);
  //Ici, on d‚termine les dates au plus tard.
  plustard[nbsommets-1]=plustot[nbsommets-1];
  calcplustard(court, plustard, nbsommets-1, nbsommets);
  // et on les affiche
  for(j=0;j<nbsommets;j++)
  {
    printf("tƒche : %2d, plustot : %2d, plustard : %2d\n",j,plustot[j], plustard[j]);
  }


//  getch();
  for(i=0;i<nbsommets;i++)
    free(court[i]);
  free(court);
  free(plustot);
  free(plustard);
}

/*------------------------------------------------------------------------
  critique

  Cette fonction affiche les tƒches critiques.
--------------------------------------------------------------------------*/
void critique(elem **graphe, int nbsommets)
{
int **court,
    *plustard,
    *plustot,
    i,
    j;

elem *actuel;

  court=(int **)malloc(nbsommets*sizeof(int *));
  plustard=(int *)malloc(nbsommets*sizeof(int));
  plustot=(int *)malloc(nbsommets*sizeof(int));
  for(i=0;i<nbsommets;i++)
  {
    plustot[i]=0;
    plustard[i]=32767;
    court[i]=(int *)malloc(nbsommets*sizeof(int));
    for(j=0;j<nbsommets;j++)
    {
      actuel=graphe[i];
      while ((actuel!=NULL)&&(actuel->val!=j))
      {
        actuel=actuel->lien;
      }
      if (actuel==NULL)
        court[i][j]=-1;
      else
        court[i][j]=actuel->poids;

    }
  }
  //Ici, on d‚termine les dates au plus t“t.
  plustot[0]=0;
  calcplustot(court, plustot, 0, nbsommets);
  //Ici, on d‚termine les dates au plus tard.
  plustard[nbsommets-1]=plustot[nbsommets-1];
  calcplustard(court, plustard, nbsommets-1, nbsommets);
  // et on trouve les tƒches critiques : plustot=plustard
  printf("Les tƒches critiques sont :\n");
  for(i=1;i<nbsommets-1;i++)
    if (plustot[i]==plustard[i])
      printf("%3d", i);

  for(i=0;i<nbsommets;i++)
    free(court[i]);
  free(court);
  free(plustot);
  free(plustard);
}

/*------------------------------------------------------------------------
  libere

  Cette fonction libŠre la m‚moire allou‚e … un graphe repr‚sent‚ par un
  tableau de pointeurs sur des liste chaŒn‚es d'entiers.
--------------------------------------------------------------------------*/
void libere(elem ***tableau, int nbsommets)
{
elem *actuel;
int i;

  for(i=0;i<nbsommets;i++)
  {
	while ((*tableau)[i]!=NULL)
	{
	  actuel=(*tableau)[i];
	  (*tableau)[i]=actuel->lien;
	  free(actuel);
	}
  }
  free(*tableau);
  *tableau=NULL;
}

/*------------------------------------------------------------------------
  pasdegraphe

  Cette fonction affiche un message … l'attention de l'utilisateur s'il
  veut utiliser un graphe vide.
--------------------------------------------------------------------------*/
void pasdegraphe(void)
{
  textcolor(LIGHTRED);
  cprintf("               Le graphe est vide !!!!\r\n");
  textcolor(LIGHTBLUE);
  cprintf("Vous devez en saisir un ou le charger depuis un fichier\r\n");
  getch();
}

/*------------------------------------------------------------------------
  main

  c'est la fonction principale, elle met en place le menu permettant de
  tester les diff‚rentes fonctions pr‚sentes dans le TD.
--------------------------------------------------------------------------*/
void main(void)
{
int nbsommets=0;
elem **tableau=NULL;
char rep;

  do
  {
	clrscr();
	textcolor(GREEN);
	cprintf("                 Recherche op‚rationnelle\r\n");
	cprintf("               TP4 ProblŠmes d'ordonnancement\r\n\r\n");
	textcolor(LIGHTGRAY);
	cprintf("1 - Saisir un problŠme au clavier\r\n");
	cprintf("2 - Charger un problŠme depuis un fichier\r\n");
	cprintf("3 - Afficher le graphe du problŠme\r\n");
	cprintf("4 - Donner les dates au plus t“t et au plus tard\r\n");
	cprintf("5 - Donner les tƒches critiques\r\n");
    cprintf("\r\n");
	cprintf("Q - Quitter\r\n\r\n");
	textcolor(BROWN);
	cprintf("Votre choix : ");
	textcolor(CYAN);

	rep=toupper(getche());
	clrscr();
	switch(rep) {
	  case '1' : libere(&tableau, nbsommets);
				 saisie_probleme(&tableau, &nbsommets);
				 break;
	  case '2' : libere(&tableau, nbsommets);
				 lecture_probleme(&tableau, &nbsommets);
				 break;
	  case '3' : if (tableau!=NULL)
				 {
				   affgraph(tableau, nbsommets);
				   getch();
				 }
				 else
				   pasdegraphe();
				 break;
	  case '4' : if (tableau!=NULL)
                 {
                   dates(tableau, nbsommets);
                   getch();
                 }
                 else
                   pasdegraphe();
                 break;
	  case '5' : if (tableau!=NULL)
                 {
                   critique(tableau, nbsommets);
                   getch();
                 }
                 else
                   pasdegraphe();
                 break;
    }
  }while ((rep!='Q') && (rep!=27));

  libere(&tableau, nbsommets);
}