/***************************************************************************
							 Recherche Op‚rationnelle
									 TP1

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

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


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

   Cette fonction ajoute un arc … un graphe repr‚sent‚ sous la forme
   d'un couple de tableaux alpha beta. Les paramŠtres transmis sont :
   deux pointeurs sur ces tableaux, le sommet de d‚part, le sommet d'arriv‚e,
   le nombre de sommets et le nombre d'arcs d‚j… existants.
   La fonction existante devra faire le n‚cessaire pour mettre … jour la
   variable nombre d'arcs.
--------------------------------------------------------------------------*/
void ajout_arc(int *alpha, int **beta,int x, int y, int nbsommets, int nbarcs)
{
int i, minmax;

  if (*beta==NULL)                          // si pas encore de liens
  {
	 *beta=(int *)malloc(sizeof(int));
	 (*beta)[0] = y;
  }
  else
  {
	*beta=(int *)realloc(*beta, nbarcs*sizeof(int));

	minmax=nbarcs;
    for(i=0;i<nbarcs;i++)
      if (alpha[i]> alpha[x])
        if (alpha[i] < minmax)
          minmax = alpha[i];

    i=nbarcs;
    while (i>minmax)
    {
      (*beta)[i]=(*beta)[i-1];
      i--;
    }
    (*beta)[minmax]=y;
  }

  for (i=0;i<=nbsommets;i++)
	if ((i!=x) && (alpha[i]>=alpha[x]))
      alpha[i]++;
}

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

   Cette fonction supprime un arc … un graphe repr‚sent‚ sous la forme
   d'un couple de tableaux alpha beta. Les paramŠtres transmis sont :
   un pointeur sur le premier ‚l‚ment de alpha et un pointeur sur le tableau
   beta (pass‚ ainsi en paramŠtre), le sommet de d‚part, le sommet d'arriv‚e,
   le nombre de sommets et le nombre d'arcs d‚j… existants.
   L'arc sera supprim‚ … condition qu'il existe.
--------------------------------------------------------------------------*/
void supp_arc(int *alpha, int **beta,int x,int y, int nbsommets, int *nbarcs)
{
int i, j, k;

  j=alpha[x];
  i=0;                                          // recherche de l'arc
  while (((*beta)[j+i]!=y) && (j+i<alpha[x+1] ))
    i++;


  if ((*beta)[j+i]==y)                // si trouv‚
  {                                   // on supprime

    for(k=j+i; k<*nbarcs-1; k++)
      (*beta)[k]=(*beta)[k+1];

    (*nbarcs)--;
    *beta=(int *)realloc(*beta,*nbarcs);

    for(k=0;k<=nbsommets;k++)
      if ( ( alpha[k]>=alpha[x]) && (k!=x))
	alpha[k]--;

    printf("l'arc %d vers %d a ‚t‚ supprim‚.", x, y);

  }
  else printf("\nL'arc demand‚ n'a pas ‚t‚ trouv‚.");
}

/*------------------------------------------------------------------------
  saisie_graphe

   Cette fonction effectue la saisie d'un graphe complet. Elle demande donc
   le nombre de sommets, le nombre d'arcs voulus par l'utilisateur. Ceci
   provoquera la mise … jour des mˆmes valeurs dans la fonction appelante.
   Elle fait appel … la fonction d'ajout d'arc d‚crite plus haut.
   Les paramŠtres transmis sont :
   deux pointeurs sur alpha et beta (pass‚s ainsi en paramŠtre),
   le nombre de sommets et le nombre d'arcs d‚j… existants.
--------------------------------------------------------------------------*/
void saisie_graphe(int **alpha, int **beta,int *nbsommets, int *nbarcs)
{
int i, org, dest, arcs, oriente=0;
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=getch();
  while((rep!='1')&&(rep!='2')&&(rep!=27));
  if (rep!=27)
  {

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

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

    *alpha=(int *)malloc((*nbsommets+1)*sizeof(int));
    for(i=0;i<*nbsommets+1;i++)
      (*alpha)[i]=0;

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

    *beta=NULL;
    if (oriente)
      *nbarcs=arcs;
    else
      *nbarcs=2*arcs;

    // saisie des arcs
    i=0;
    do
    {
      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)
          ajout_arc(*alpha, beta, org, dest, *nbsommets, i);
        else
        {
          printf("Ce sommet n'existe pas");
	  i--;
        }
      }
      else
      {
        printf("Ce sommet n'existe pas");
		i--;
      }
      i++;
    }while(i<arcs);
  }
}

/*------------------------------------------------------------------------
   aff_graph

   Cette fonction affiche un graphe repr‚sent‚ sous la forme d'un couple de
   tableaux alpha beta. Les paramŠtres transmis sont :
   un pointeur sur le premier ‚l‚ment de alpha et un pointeur sur le premier
   ‚l‚ment de beta, le nombre de sommets et le nombre d'arcs d‚j… existants.
--------------------------------------------------------------------------*/
void affgraph(int *alpha, int *beta,int nbsommets, int nbarcs)
{
int i;

  printf("\ntableau beta :\n");
  for(i=0; i<nbarcs; i++)
    printf(" %3d ", beta[i]);

  printf("\ntableau alpha :\n");
  for(i=0; i<nbsommets+1; i++)
    printf(" %3d ", alpha[i]);

  getch();
}

/*------------------------------------------------------------------------
   lecture_graph

   Cette fonction cr‚e un graphe repr‚sent‚ sous la forme d'un couple de
   tableaux alpha beta en lisant les donn‚es n‚cessaires dans un fichier.
   Les paramŠtres transmis sont :
   un pointeur les tableaux alpha et beta (pass‚s ainsi en paramŠtres), le
   nombre de sommets et le nombre d'arcs d‚j… existants.
--------------------------------------------------------------------------*/
void lecture_graphe(int **alpha, int **beta, int *nbsommets, int *nbarcs)
{
char fichier[255];
FILE *fic;
int  x, y, sommets, arcs, i;

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

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

    *alpha=(int *)malloc( ((*nbsommets)+1) * sizeof(int));
    for(i=0;i<(*nbsommets)+1;i++)
      (*alpha)[i]=0;

    for(i=0;i<*nbarcs;i++)
    {
      fscanf(fic, "%d %d", &x, &y);
      printf("\n%d\t%d", x, y);
      ajout_arc(*alpha, beta, x, y, *nbsommets, i+1);
    }
    fclose(fic);
  }
  else
    printf("Erreur : %s", sys_errlist[errno]);
  getch();
}

/*------------------------------------------------------------------------
  ajout_arc_tab

  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.
  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_tab(elem **tableau, int x, int y)
{
elem *actuel, *temp;

  temp=(elem *)malloc(sizeof(elem));
  temp->val=y;
  temp->lien=NULL;

  if (tableau[x]==NULL)
  {
    tableau[x]=temp;
  }
  else
  {
    actuel=tableau[x];
    while (actuel->lien!=NULL)
	  actuel=actuel->lien;

    actuel->lien=temp;
  }
}

/*------------------------------------------------------------------------
  saisie_graphe_tab

  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), le nombre de sommets et le nombre d'arcs.
--------------------------------------------------------------------------*/
void saisie_graphe_tab(elem ***tableau, int *nbsommets, int *nbarcs)
{
int i, org, dest, arcs, oriente=1;
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=getch();
  while((rep!='1')&&(rep!='2')&&(rep!=27));
  if (rep!=27)
  {

    oriente=rep-'1';
    if (oriente)
      printf("Graphe orient‚\n");
    else
      printf("Graphe 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 : ");
    else
      printf("Nombre d'arˆtes dans le graphe : ");
    scanf("%d", &arcs);

    // saisie des arcs

    *nbarcs=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)
        {
          ajout_arc_tab(*tableau, org, dest);
          if (!oriente)
          {
            ajout_arc_tab(*tableau, dest, org);
            (*nbarcs)++;
          }

		  (*nbarcs)++;
        }
        else
        {
	  printf("Ce sommet n'existe pas\n");
  	  i--;
        }
      }
      else
      {
        printf("Ce sommet n'existe pas\n");
        i--;
      }
      i++;
    }
  }
}

/*------------------------------------------------------------------------
  supparc_tab

  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 supparc_tab(elem **tableau, int x, int y, int nbsommets)
{
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");
      }
      else
        printf("Ce lien est introuvable\n");
    }
  }
  else
    printf("Sommet introuvable\n");
}

/*------------------------------------------------------------------------
  lecture_graphe_tab

  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), le nombre de sommets et le nombre d'arcs.
--------------------------------------------------------------------------*/
void lecture_graphe_tab(elem ***tableau, int *nbsommets, int *nbarcs)
{
char fichier[255];
FILE *fic;
int des, sommets, arcs, inutile, i, x, y;

  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", &x, &y);
      printf("\nx : %d\ty : %d", x, y);
      ajout_arc_tab(*tableau,  x, y);
	}
    fclose(fic);
  }
  else
	printf("Erreur : %s", sys_errlist[errno]);

  getch();
}


/*------------------------------------------------------------------------
  affgraph_tab

  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_tab(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\n", actuel->val);
		actuel=actuel->lien;
	  }while (actuel!=NULL);
	}
  }
}

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


void visiter(elem **tableau,int sommet, int *tab)
{
elem *actuel;
  if (tab[sommet]==0)
	  actuel=tableau[sommet];
	  do{
	   actuel=actuel->lien;
	  }while(actuel!=NULL);


}

void courts_chemins(elem **tableau, int org, int nbsommets_tab)
{
 int *tab;
 int i;

 tab = (int *)malloc(nbsommets_tab*sizeof(int));
 for (i=0;i<nb_sommets_tab;i++)
   tab[i]=0;

 visiter(org, tab);

 free(tab);
}
/*------------------------------------------------------------------------
  main

  c'est la fonction principale, elle met en place le menu permettant de
  teste rles diff‚rentes fonctions pr‚sentes dans le TD.
--------------------------------------------------------------------------*/
void main(void)
{
int nbsommets, nbarcs, nbsommets_tab, nbarcs_tab, org, dest;
int *alpha=NULL, *beta=NULL;
elem **tableau;
char rep;

  do
  {
    clrscr();
	textcolor(GREEN);
    cprintf("              Recherche op‚rationnelle\r\n");
	cprintf("                         TD1\r\n");
    cprintf("\r\n\r\n");
    textcolor(YELLOW);
    cprintf("Codage par des tableaux\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");
    cprintf("4 - Supprimer un arc dans le graphe\r\n\r\n");
    textcolor(YELLOW);
    cprintf("Codage par un tableau de pointeurs\r\n");
    textcolor(LIGHTGRAY);
    cprintf("5 - Saisir un graphe au clavier\r\n");
    cprintf("6 - Charger un graphe depuis un fichier\r\n");
	cprintf("7 - Afficher le graphe\r\n");
	cprintf("8 - Supprimer un arc dans le graphe\r\n\r\n");
	cprintf("9 - Calcul des plus courts chemins\r\n");
	cprintf("8 - Supprimer un arc dans le graphe\r\n\r\n");
	cprintf("Q - Quitter\r\n\r\n");
	textcolor(BROWN);
	cprintf("Votre choix : ");
	textcolor(CYAN);

	rep=toupper(getche());
	switch(rep) {
	  case '1' : saisie_graphe(&alpha, &beta, &nbsommets, &nbarcs);
				 break;
	  case '2' : lecture_graphe(&alpha, &beta, &nbsommets, &nbarcs);
				 break;
	  case '3' : affgraph(alpha, beta, nbsommets, nbarcs);
				 break;
	  case '4' : printf("\nOrigine de l'arc ? ");
				 scanf("%d", &org);
				 printf("Destination de l'arc ? ");
				 scanf("%d", &dest);
				 supp_arc(alpha, &beta, org, dest, nbsommets, &nbarcs);
				 getch();
				 break;
	  case '5' : saisie_graphe_tab(&tableau, &nbsommets_tab, &nbarcs_tab);
				 break;
	  case '6' : lecture_graphe_tab(&tableau, &nbsommets_tab, &nbarcs_tab);
				 break;
	  case '7' : affgraph_tab(tableau, nbsommets_tab);
				 getch();
				 break;
	  case '8' : printf("\nOrigine de l'arc ? ");
				 scanf("%d", &org);
				 printf("Destination de l'arc ? ");
				 scanf("%d", &dest);
				 supparc_tab(tableau, org, dest, nbsommets_tab);
				 getch();
				 break;
	  case '9' : printf("\nElement d'origine ?");
				 scanf("%d", &org);
				 courts_chemins(tableau, org, nbsommets_tab);
				 getch();
				 break;

	}
  }while ((rep!='Q') && (rep!=27));

  free(alpha);
  free(beta);
  libere(tableau, nbsommets_tab);
}