/***************************************************************************
                             Recherche Op‚rationnelle
                                     TP3

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>

// 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_graphe

  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.
  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_graphe(elem ***tableau, int *nbsommets, int *oriente)
{
int i, org, dest, arcs, poids;
char rep;

  clrscr();
  printf("Que d‚sirez vous saisir : \n");
  printf("1 - Un graphe non-orient‚\n");
  printf("2 - Un graphe orient‚\n");

  do
    rep=getche();
  while((rep!='1')&&(rep!='2')&&(rep!=27));
  if (rep!=27)
  {

    *oriente=rep-'1';
    if (*oriente)
      printf("\nGraphe orient‚\n");
    else
      printf("\nGraphe non-orient‚\n");

    // saisie du nombre de sommets
    printf("\nNombre de sommets dans le graphe : ");
    scanf("%d", nbsommets);

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

    // saisie du nombre d'arcs
    if (*oriente)
      printf("Nombre d'arcs dans le graphe (… saisir maintenant) : ");
    else
      printf("Nombre d'arˆtes dans le graphe (… saisir maintenant) : ");
    scanf("%d", &arcs);

    // saisie des arcs

    i=0;
    while(i<arcs)
    {
      if (*oriente)
        printf("Origine de l'arc nø%d : ",i);
      else
        printf("Premier sommet de l'arˆte nø%d : ", i);
      scanf("%d", &org);
      if (org<*nbsommets)
      {
        if (*oriente)
          printf("Destination de l'arc nø%d : ",i);
        else
          printf("DeuxiŠme sommet de l'arˆte nø%d : ", i);
        scanf("%d", &dest);
        if (dest<*nbsommets)
        {
          printf("Poids : ");
          scanf("%d", &poids);
		  ajout_arc(*tableau, org, dest, poids);
		  if (!(*oriente))
		  {
			ajout_arc(*tableau, dest, org, poids);
            printf("Ici\n");
          }
        }
        else
        {
	  printf("Ce sommet n'existe pas\n");
  	  i--;
        }
      }
      else
      {
        printf("Ce sommet n'existe pas\n");
        i--;
      }
      i++;
    }
  }
}

/*------------------------------------------------------------------------
  supp_arc

  Cette fonction supprime un arc d'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, les sommets de d‚part et
  d'arriv‚e de l'arc … supprimer et enfin le nombre de sommets du graphe.
--------------------------------------------------------------------------*/
void supp_arc(elem **tableau, int x, int y, int nbsommets, int oriente)
{
elem *actuel, *prec;

  if (x<=nbsommets)
  {
    actuel=tableau[x];
    prec=NULL;
    if (actuel!=NULL)
    {
      while ((actuel != NULL) && (actuel->val != y))
      {
        prec=actuel;
        actuel=actuel->lien;
      }

      if (actuel!=NULL)                 // si on a trouv‚
      {
         if (prec!=NULL)
           prec=actuel->lien;
         else
           tableau[x]=actuel->lien;
         free(actuel);
         printf("Suppression effectu‚e\n");
         supp_arc(tableau, y, x, nbsommets, oriente);
      }
      else
        printf("Ce lien est introuvable\n");
    }
  }
  else
    printf("Sommet introuvable\n");
}

/*------------------------------------------------------------------------
  lecture_graphe

  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
  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_graphe(elem ***tableau, int *nbsommets)
{
char fichier[255];
int nbarcs;
FILE *fic;
int i, x, y, poids;

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

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

    *tableau=(elem **)malloc( (*nbsommets) * sizeof(elem *));
    for(i=0;i<*nbsommets+1;i++)
      (*tableau)[i]=NULL;

    for(i=0;i<nbarcs;i++)
    {
      fscanf(fic, "%d %d %d", &x, &y, &poids);
      printf("\nx : %d\ty : %d", x, y);
	  ajout_arc(*tableau,  x, y, poids);
    }
    fclose(fic);
  }
  else
    printf("Erreur : %s", sys_errlist[errno]);

  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);
    }
  }
}

/*------------------------------------------------------------------------
  produit

  Cette fonction calcule un produit de matrices
--------------------------------------------------------------------------*/
void produit( int **A, int **B, int **R, int nbsommets)
{
 int i,j,k;

  for (i=0;i<nbsommets;i++)
   for (j=0;j<nbsommets;j++)
   {
      R[i][j]=0;
    for (k=0;k<nbsommets;k++)
      R[i][j]+=A[i][k]*B[k][j];
   }
}

/*------------------------------------------------------------------------
  mat_plus_court

  Cette fonction va afficher la matrice des plus courts chemins.
--------------------------------------------------------------------------*/
void mat_plus_court(elem **tableau, int nbsommets, int cmp)
{
int **A,
    **B,
    **R,
    **court,
    **PI,
    *chemin,
    i,
    j,
    k,
    l,
    col;

elem *actuel;

  A=(int **)malloc(nbsommets*sizeof(int *));
  B=(int **)malloc(nbsommets*sizeof(int *));
  R=(int **)malloc(nbsommets*sizeof(int *));
  court=(int **)malloc(nbsommets*sizeof(int *));
  PI=(int **)malloc(nbsommets*sizeof(int *));

  for(i=0;i<nbsommets;i++)
  {
    A[i]=(int *)malloc(nbsommets*sizeof(int));
    B[i]=(int *)malloc(nbsommets*sizeof(int));
    R[i]=(int *)malloc(nbsommets*sizeof(int));
    court[i]=(int *)malloc(nbsommets*sizeof(int));
    PI[i]=(int *)malloc(nbsommets*sizeof(int));
    for(j=0;j<nbsommets;j++)
    {
      if (i==j)
        A[i][j]=1;
      else
        A[i][j]=0;
      actuel=tableau[i];
      while ((actuel!=NULL)&&(actuel->val!=j))
      {
        actuel=actuel->lien;
      }
      if (actuel==NULL)
        B[i][j]=0;
      else
        B[i][j]=1;

      R[i][j]=B[i][j];
      court[i][j]=0;
      PI[i][j]=-1;
    }
  }

  for(k=1;k<=nbsommets;k++)
  {
    // multiplication M
    produit(A,B,R,nbsommets);

    // on met la matrice r‚sultat R dans la matrice A et on met … jour court
    for(i=0;i<nbsommets;i++)
       for(j=0;j<nbsommets;j++)
       {
         A[i][j]=R[i][j];
         if((R[i][j] >= 1) && (court[i][j] == 0))
         {
           court[i][j]=k;

           if (k==1)
             PI[i][j]=i;
           else
           {
             l=0;
            // je vais chercher un pr‚decesseur de j au rang k-1
             while (PI[i][j]==-1)
             {
             // je parcours la colonne j … la recherche d'un pr‚d‚cesseur
             // potentiel (dont le nombre de chemins est ‚gal … k-1)
               while (court[l][j]!=k-1)
                 l++;

             // a ce niveau, le sommet PI[l][j] est candidat puisqu'il
             // faut k-1 arcs pour aller de celui-ci au sommet j
             // il reste … v‚rifier que l'on peut aller de i … ce
             // sommet en k-1 arcs
               if ( court[i][ PI[l][j] ] == k-1)
                 PI[i][j]=PI[l][j];     // si oui, on affecte
               else
                 l++;                   // si non, on passe au suivant

             }
           }
         }
       }
  }

  if (!cmp)
  {
    printf("affichage de court");
    for (i=0;i<nbsommets;i++)
    {
      printf("\n");
      for (j=0;j<nbsommets;j++)
        printf("%2d",court[i][j]);
    }
    printf("\n\n");

    printf("affichage de PI");
    for (i=0;i<nbsommets;i++)
    {
      printf("\n");
      for (j=0;j<nbsommets;j++)
        printf("%2d",PI[i][j]);
    }
    printf("\n\n");
    getch();

    clrscr();
    // on va maintenant afficher les chemins reconstitu‚s
    chemin=(int *)malloc((nbsommets+1)*sizeof(int));
    for(i=0;i<nbsommets;i++)
      for(j=0;j<nbsommets;j++)
      {
        for(k=0;k<nbsommets;k++)
          chemin[k]=-1;

        if (PI[i][j]==-1)
        {
          printf("On ne peut pas aller de %d vers %d.\n", i, j);
        }
        else
        {
          printf("Pour aller de %d vers %d, il faut %d arcs :", i, j, court[i][j]);
          // on va retrouver les sommets par lesquels passer en construisant
          // le tableau chemin.
          chemin[0]=j;

          l=j;
          for(k=1;k<court[i][j]+1;k++)
          {
            chemin[k]=PI[i][l];
            col=l;
            l=0;
            while (court[i][l]!=court[i][col]-1)
              l++;
          }
          for(k=court[i][j];k>0;k--)
            printf("%2d ->", chemin[k]);
          printf("%2d", chemin[k]);

          printf("\n");
        }

        if (((i*nbsommets+j)%20==0) && (i!=0))
        {
          printf("Appuyez sur une touche pour continuer\n");
          getch();
          clrscr();
        }
      }

    printf("Appuyez sur une touche pour continuer\n");
  }

  // lib‚ration de la m‚moire
  for(i=0;i<nbsommets;i++)
  {
    free(A[i]);
    free(B[i]);
    free(R[i]);
    free(court[i]);
    free(PI[i]);
  }
  free(A);
  free(B);
  free(R);
  free(court);
  free(PI);
  free(chemin);
}

/*------------------------------------------------------------------------
  pasdansS

  cette fonction renvoie 1 si l'‚l‚ment pass‚ n'est pas dans le tableau
  pass‚ en paramŠtre.
---------------------------------------------------------------------------*/
int pasdansS(int val, int *tab, int nbsommets)
{
int i;

  i=0;
  while ((tab[i]!=val)&&(i<nbsommets))
    i++;

  if (i==nbsommets)
    return 1;
  else
    return 0;
}

/*------------------------------------------------------------------------
  trier

  Cette fonction va trier le graphe selon l'algorithme de tri bulle
--------------------------------------------------------------------------*/
void trier(int *file, int *lambda, int dernier)
{
int i,
    mouchard=1,
    temp;


  while (mouchard==1)
  {
    mouchard=0;
    for (i=0;i<dernier;i++)
      if (lambda[ file[i] ] > lambda[ file[i+1] ])
      {
        temp=file[i];
        file[i] = file[i+1];
        file[i+1] = temp;
        mouchard=1;
      }
  }
}
/*------------------------------------------------------------------------
  dijkstra

  Cette fonction va parcourir le graphe selon l'algorithme de Dijkstra.
--------------------------------------------------------------------------*/
void dijkstra(elem **tableau, int nbsommets, int org, int cmp)
{
#define infini 16000
int *lambda,
    *file,
    *S,
    *PI,
    *chemin,
    i,
    j,
    k,
    indexS=0,
    xi;
elem *actuel;

  lambda=(int *)malloc(nbsommets*sizeof(int));
  file=(int *)malloc(nbsommets*sizeof(int));
  S=(int *)malloc(nbsommets*sizeof(int));
  PI=(int *)malloc(nbsommets*sizeof(int));
  chemin=(int *)malloc(nbsommets*sizeof(int));

// initialisation des tableaux
  for(i=0;i<nbsommets;i++)
  {
    lambda[i]=infini;
    file[i]=i;
    S[i]=-1;
    PI[i]=-1;
  }
  file[org]=file[0];
  file[0]=org;
  lambda[org]=0;
  S[0]=org;

  //tant que S!=X et que le premier de la file peut ˆtre atteint depuis org
  while ((indexS!=nbsommets) && (lambda[ file[0] ] != infini))
  {
    xi=file[0];     //on prend le premier de la file
    S[indexS]=xi;   //on l'ajoute aux sommets trait‚s
    indexS++;       //un sommet de plus

    // pour tous les successeurs xj de xi
    actuel=tableau[xi];   //on prend lien actuel
    while (actuel!=NULL)
    {
      // si xj n'est pas dans S
      if (pasdansS(actuel->val, S, nbsommets))
        if (lambda[actuel->val] > lambda[xi]+actuel->poids)
        {
          // MAJ de PI
          PI[actuel->val]=xi;
          // MAJ de lambda
          lambda[actuel->val]=lambda[xi]+actuel->poids;
        }

      actuel=actuel->lien;
    }
    // on enlŠve xi de la file (on la recr‚e en prenant ceux qui
    // ne sont pas dans S)
    j=0;
    for(i=0;i<nbsommets;i++)
      if (pasdansS(i, S, nbsommets))
      {
        file[j]=i;
        j++;
      }

    // puis on la trie
    trier(file, lambda, j);

  }

  if (!cmp)
  {
    clrscr();
  // affichage des lambda
    printf("lambda\n");
    for(i=0;i<nbsommets;i++)
      printf("%2d ", lambda[i]);
    printf("\n");

  // affichage du tableau S
    printf("Tableau S\n");
    for(i=0;i<nbsommets;i++)
      printf("%2d ", S[i]);
    printf("\n");

  // affichage du tableau PI
    printf("Tableau PI\n");
    for(i=0;i<nbsommets;i++)
      printf("%2d ", PI[i]);
    printf("\n");
    getch();

  // reconstitution des chemins
    for (i=0;i<nbsommets;i++)
    {
      if (PI[i]==-1)
      {
        printf("On ne peut pas aller de %d … %d\n", org, i);
      }
      else
      {
        printf("Pour aller de %d … %d cela coute %d : ", org, i, lambda[i]);
        for(j=0;j<nbsommets;j++)
          chemin[j]=-1;

        k=0;
        j=i;
        while (PI[j]!=-1)
        {
	      chemin[k]=j;
          k++;
          j=PI[j];
        }
        chemin[k]=org;

        for(j=k;j>0;j--)
          printf("%2d ->", chemin[j]);
        printf("%2d", chemin[0]);

        printf("\n");
      }
    }
  }
// lib‚ration de la m‚moire
  free(lambda);
  free(file);
  free(S);
  free(PI);
  free(chemin);
}

/*-------------------------------------------------------------------------
  compare_mat_dij

  Cette fonction permet de r‚aliser la comparaison entre la m‚thode de
  la matrice et la m‚thode de dijkstra
--------------------------------------------------------------------------*/
void compare_mat_dij(elem **graphe, int nbsommets)
{
time_t avant, apres;
int i;

  time(&avant);
  mat_plus_court(graphe, nbsommets, 1);
  time(&apres);
  printf("Matrice des plus courts chemins, temps ‚coul‚ : %d\n", apres-avant);

  time(&avant);
  for (i=0;i<nbsommets;i++)
    dijkstra(graphe, nbsommets, i, 1);
  time(&apres);
  printf("M‚thode de Dijkstra, temps ‚coul‚ : %d\n", apres-avant);
}

/*------------------------------------------------------------------------
  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, org, dest, oriente=1, poids;
elem **tableau=NULL;
char rep;

  do
  {
	clrscr();
	textcolor(GREEN);
	cprintf("                 Recherche op‚rationnelle\r\n");
	cprintf("         TP3 Recherche des chemins de poids minimal\r\n\r\n");
	textcolor(LIGHTGRAY);
	cprintf("1 - Saisir un graphe au clavier\r\n");
	cprintf("2 - Charger un graphe depuis un fichier\r\n");
	cprintf("3 - Afficher le graphe\r\n");
	if (oriente)
	{
	  cprintf("4 - Ajouter un arc dans le graphe\r\n");
	  cprintf("5 - Supprimer un arc dans le graphe\r\n");
	}
	else
	{
	  cprintf("4 - Ajouter une arˆte dans le graphe\r\n");
	  cprintf("5 - Supprimer une arˆte dans le graphe\r\n");
	}
	cprintf("6 - Matrice des plus courts chemins en nombre d'arcs\r\n");
	cprintf("7 - Algorithme de Dijkstra, chemins les moins couteux\r\n");
	cprintf("8 - Comparaison Matrice - Dijkstra\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_graphe(&tableau, &nbsommets, &oriente);
				 break;
	  case '2' : libere(&tableau, nbsommets);
				 lecture_graphe(&tableau, &nbsommets);
				 oriente=1;
				 break;
	  case '3' : if (tableau!=NULL)
				 {
				   affgraph(tableau, nbsommets);
				   getch();
				 }
				 else
				   pasdegraphe();
				 break;
	  case '4' : if (tableau!=NULL)
				 {
				   printf("\nOrigine ? ");
				   scanf("%d", &org);
				   printf("Destination ? ");
				   scanf("%d", &dest);
                   printf("Poids ? ");
                   scanf("%d", &poids);
				   ajout_arc(tableau, org, dest, poids);
				   if (!oriente)
					 ajout_arc(tableau, dest, org, poids);
				 }
				 else
				   pasdegraphe();
				 break;
	  case '5' : if (tableau!=NULL)
				 {
				   printf("\nOrigine ? ");
				   scanf("%d", &org);
				   printf("Destination ? ");
				   scanf("%d", &dest);
				   supp_arc(tableau, org, dest, nbsommets, oriente);
				   getch();
				 }
				 else
				   pasdegraphe();
				 break;
	  case '6' : if (tableau!=NULL)
                 {
                   mat_plus_court(tableau, nbsommets, 0);
                   getch();
                 }
                 else
                   pasdegraphe();
                 break;
	  case '7' : if (tableau!=NULL)
                 {
                   printf("Depuis quel sommet ? ");
                   scanf("%d", &org);
                   if (org<nbsommets)
                     dijkstra(tableau, nbsommets, org, 0);
                   else
                     printf("Ce sommet n'existe pas !");
                   getch();
                 }
                 else
                   pasdegraphe();
                 break;
	  case '8' : if (tableau!=NULL)
                 {
                   compare_mat_dij(tableau, nbsommets);
                   getch();
                 }
                 else
                   pasdegraphe();
                 break;
    }
  }while ((rep!='Q') && (rep!=27));

  libere(&tableau, nbsommets);
}