/***************************************************************************
                             Recherche Op‚rationnelle
                                     TP2

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‚ 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)
{
elem *actuel, *prec, *temp;

  if (tableau!=NULL)
  {
    temp=(elem *)malloc(sizeof(elem));
    temp->val=y;
    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;
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)
        {
		  ajout_arc(*tableau, org, dest);
		  if (!(*oriente))
		  {
			ajout_arc(*tableau, dest, org);
            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, oriente;
FILE *fic;
int 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(*tableau,  x, y);
    }
    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\n", actuel->val);
        actuel=actuel->lien;
      }while (actuel!=NULL);
    }
  }
}
/*------------------------------------------------------------------------
  parcours_largeur

  Cette fonction affiche les plus courts chemins … partir d'un sommet.
--------------------------------------------------------------------------*/
void parcours_largeur(elem **tableau, int *PI, int org, int nbsommets)
{
int *file,              // file de gestion
	*dejavisite,        // tableau pour savoir qui est d‚j… visit‚
	entree,             // index o— ajouter dans la file
	sortie,             // index de l'‚l‚ment … sortir de la file
	x,                  // premier sommet de la file dans l'algo
	i;
elem *actuel;

  file=(int *)malloc(sizeof(int)*nbsommets);
  dejavisite=(int *)malloc(sizeof(int)*nbsommets);

  for(i=0;i<nbsommets;i++)
	dejavisite[i]=0;

  for(i=0;i<nbsommets;i++)
	PI[i]=-1;

  printf("Ordre de traitement :\n");
  entree=sortie=0;                // file vide

  if (!dejavisite[org])
  {
	file[entree]=org;
	entree++;
	if (entree>=nbsommets)
	  entree=0;

	while (entree!=sortie)
	{
	  x=file[sortie];
	  dejavisite[x]=1;
	  // traitement
	  printf("%d ", x);

	  sortie++;               // on d‚file x
	  if (sortie>=nbsommets)
		sortie=0;

	  // on va enfiler tout ses successeurs
	  actuel=tableau[x];
	  while (actuel!=NULL)
	  {
		if (!(dejavisite[actuel->val]))
		{
		  PI[actuel->val]=x;
		  file[entree]=actuel->val;
		  dejavisite[actuel->val]=1;
		  entree++;
		  if (entree>=nbsommets)
			entree=0;
		}
		actuel=actuel->lien;
	  }
	}
  }
  free(file);
  free(dejavisite);
}

/*------------------------------------------------------------------------
  aff_chemins

--------------------------------------------------------------------------*/
void aff_chemins(elem **tableau, int org, int nbsommets)
{
int *PI, i, dest, nbarcs, *chemins;
int index;

  chemins=(int *)malloc(sizeof(int)*nbsommets);

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

  parcours_largeur(tableau, PI, org, nbsommets);

  printf("\nTableau PI\n");
  for(i=0;i<nbsommets;i++)
	printf("%4d", PI[i]);


  for(dest=0;dest<nbsommets;dest++)
  {
	for(i=0;i<nbsommets;i++)
	  chemins[i]=-1;

	index=0;
	i=dest;
	nbarcs=0;
	while (PI[i]!=-1)
	{
	  chemins[index]=i;
	  index++;
	  i=PI[i];
	  nbarcs++;
	}
	chemins[index]=org;
	printf("\nPour aller de %d vers %d il faut %d arcs", org, dest, nbarcs);
	i=0;
	printf("\n\tChemin: ") ;
	for (i=index;i>=0;i--)
	 printf("%2d", chemins[i]);

  }

  getch();
  free(PI);
}
/*------------------------------------------------------------------------
  visit_prof

--------------------------------------------------------------------------*/
void visit_prof(elem **tableau, int *dejavisite, int org)
{
elem *actuel;

  if (!(dejavisite[org]))
  {
	// pr‚traitement
	dejavisite[org]=1;
	// recursion
	actuel=tableau[org];
	while (actuel!=NULL)
	{
	  if (!(dejavisite[actuel->val]))
	  {
		visit_prof(tableau, dejavisite, actuel->val);
	  }
	  actuel=actuel->lien;
	}
	// postraitement
  }
}

/*------------------------------------------------------------------------
  aff_accessibles

  Cette fonction affiche les sommets accessibles depuis le sommet org
--------------------------------------------------------------------------*/
void aff_accessibles(elem **tableau, int org, int nbsommets)
{
int *dejavisite,
	i;

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

  visit_prof(tableau, dejavisite, org);

  printf("Les sommets accessibles depuis le sommet %d sont :\n", org);
  for(i=0;i<nbsommets;i++)
	if (dejavisite[i])
	  printf("%2d", i);

  getch();
}

/*------------------------------------------------------------------------
  rend_accessibles

  Cette fonction rends tous les sommets accessibles depuis le sommet org
--------------------------------------------------------------------------*/
void rend_accessibles(elem **tableau, int org, int nbsommets)
{
int *dejavisite,
	i;

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

  visit_prof(tableau, dejavisite, org);

  for(i=0;i<nbsommets;i++)
	if (!dejavisite[i])
	  ajout_arc(tableau, org, i);

}

/*------------------------------------------------------------------------
  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
  teste rles diff‚rentes fonctions pr‚sentes dans le TD.
--------------------------------------------------------------------------*/
void main(void)
{
int nbsommets=0, org, dest, oriente=1;
elem **tableau=NULL;
char rep;

  do
  {
	clrscr();
	textcolor(GREEN);
	cprintf("                 Recherche op‚rationnelle\r\n");
	cprintf("                 TP2 Parcours de graphes\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 - Afficher les chemins les plus courts depuis un sommet\r\n");
	cprintf("7 - Afficher les sommets accessibles depuis un autre sommet\r\n");
	cprintf("8 - Rendre tous les sommets accessibles depuis un sommet\r\n\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);
				   ajout_arc(tableau, org, dest);
				   if (!oriente)
					 ajout_arc(tableau, dest, org);
				 }
				 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)
				 {
				   printf("\nSommet d'origine ? ");
				   scanf("%d", &org);
				   aff_chemins(tableau, org, nbsommets);
				 }
				 else
				   pasdegraphe();
				 break;
	  case '7' : if (tableau!=NULL)
				 {
				   printf("\nSommet d'origine ? ");
				   scanf("%d", &org);
				   aff_accessibles(tableau, org, nbsommets);
				 }
				 else
				   pasdegraphe();
				 break;
	  case '8' : if (tableau!=NULL)
				 {
				   printf("\nSommet d'origine ? ");
				   scanf("%d", &org);
				   rend_accessibles(tableau, org, nbsommets);
				 }
				 else
				   pasdegraphe();
				 break;
    }
  }while ((rep!='Q') && (rep!=27));

  libere(&tableau, nbsommets);
}