/**********************************************************************
 ***** Pierre Hyvernat, cours info505 "Algorithmes de graphes"    *****
 *****                                                            *****
 ***** Filière : néant (c'est moi le prof !)                      *****
 ***** TP1, correction possible                                   *****
 *****                                                            *****
 *********************************************************************/


#include "graphes.h"
#include <stdio.h>
#include <stdlib.h>


/* Q1 : la fonction d'affichage
 * Rien à dire : cette fonction est triviale... */
void afficheGrapheListe(GrapheListe G)
{
  int s;
  int n = G->nb_sommets;
  int m = 0;
  ListeAdj L;
  printf("Le graphe a %i sommets :\n", n);
  for (s = 0; s < n; s++) {
    for (L = G->Adj[s]; L != NILL; L = L->suivant) {
      printf("  %i  --(%i)-->  %i\n", s, L->poids, L->but);
      m++;
    }
  }
  printf("Le graphe a %i arcs\n", m);
}


/* Q2 : fonctions de conversion */
/* Pour convertir des listes d'adjacences vers une matrice, j'ajoute les
 * poids.
 * Attention : en presence de poids negatifs, cela peut faire disparaitre des
 * arcs car un arc de poids -1 va annuler un arc de poids 1... */
GrapheMatr listeVersMatrice(GrapheListe G)
{
  int i, j;
  int n = G->nb_sommets;
  GrapheMatr H = grapheMatrVide(n);
  for (i = 0; i < n; i++) {            // Attention : grapheMatrVide() ne met rien dans la matrice
    for (j = 0; j < n; j++) {          // il faut donc le faire explicitement
      H->Matr[i][j] = 0;
    }
  }
  ListeAdj L;
  for (i = 0; i < n; i++) {
    for (L = G->Adj[i]; L != NILL; L = L->suivant) {
      H->Matr[i][L->but] = L->poids;
    }
  }
  return (H);
}

/* La fonction qui va en sens inverse est plus simple */
GrapheListe matriceVersListe(GrapheMatr H)
{
  int n = H->nb_sommets;
  GrapheListe G = grapheListeVide(n);
  int i, j, p;
  for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
      if ((p = H->Matr[i][j]) != 0)
        ajoute(i, p, j, &(G->Adj[i]));
    }
  }
  return (G);
}


/* Q3 : fonction qui renverse tous les arcs.
 * Sa complexité est en O(n+m) */
GrapheListe transpose(GrapheListe G)
{
  int i, p, b;
  ListeAdj L;
  int n = G->nb_sommets;
  GrapheListe H = grapheListeVide(n);
  for (i = 0; i < n; i++) {
    for (L = G->Adj[i]; L != NILL; L = L->suivant) {
      p = L->poids;
      b = L->but;
      ajoute(b, p, i, &(H->Adj[b]));
    }
  }
  return (H);
}


/* Q4 : parcours en largeur, mais on renvoie un GrapheListe pour la forêt
 * couvrante... */
GrapheListe parcoursLargeur(GrapheListe G)
{
  int s, u, v;
  int n = G->nb_sommets;
  GrapheListe pere = grapheListeVide(n);
  int etat[n];
  Tile F = tileVide();
  ListeAdj L;

  for (s = 0; s < n; s++) {
    etat[s] = NON_VU;
  }

  for (s = 0; s < n; s++) {
    if (etat[s] == NON_VU) {
      entile(s, 0, 0, F);
      etat[s] = VU;
      while (!tileEstVide(F)) {
        defile(F, &u, NULL, NULL);
        for (L = G->Adj[u]; L != NULL; L = L->suivant) {
          v = L->but;
          if (etat[v] == NON_VU) {
            etat[v] = VU;
            ajoute(v, 1, u, &(pere->Adj[v]));
            ajoute(u, 1, v, &(pere->Adj[u]));
            entile(v, 0, 0, F);
          }
        }
      }
    }
  }
  return (pere);
}


/* Q5 : fonction qui calcule la distance :
 * c'est un copié-collé de la fonction précédente, avec les modifications
 * pertinentes... */
int *distances(GrapheListe G, int depart)
{
  int n = G->nb_sommets;
  int u, v;
  int *distances = malloc(n * sizeof(int));
  Tile F = tileVide();
  ListeAdj L;

  for (u = 0; u < n; u++) {
    distances[u] = -1;
  }

  entile(depart, 0, 0, F);
  distances[depart] = 0;
  while (!tileEstVide(F)) {
    defile(F, &u, NULL, NULL);
    for (L = G->Adj[u]; L != NULL; L = L->suivant) {
      v = L->but;
      if (distances[v] == -1) {
        distances[v] = distances[u] + 1;
        entile(v, 0, 0, F);
      }
    }
  }
  return (distances);
}

/* pour la distance entre deux sommets, on peut faire simplement :
  int distance(GrapheListe G, int a, int b) {
    int *d = distances(G, a);
    int *l = d[b];
    free(d);
    return(l);
  }
   ou, si on veut s'arreter dès que possible : */
int distance(GrapheListe G, int depart, int arrivee)
{
  int n = G->nb_sommets;
  int distances[n];
  int u, v;
  Tile F = tileVide();
  ListeAdj L;

  for (u = 0; u < n; u++) {
    distances[u] = -1;
  }

  entile(depart, 0, 0, F);
  distances[depart] = 0;
  while (!tileEstVide(F)) {
    defile(F, &u, NULL, NULL);
    for (L = G->Adj[u]; L != NULL; L = L->suivant) {
      v = L->but;
      if (distances[v] == -1) {
        distances[v] = distances[u] + 1;
        if (v == arrivee) {
          return (distances[v]);
        }
        entile(v, 0, 0, F);
      }
    }
  }
  return (-1);
}


/* Q6 (bonus) : fonction qui calcule le diametre d'un graphe non-orienté
 * connexe et donne deux sommets eloignés dans a et b
 */
int diametre(GrapheListe G, int *a, int *b)
{
  int i, max;
  int n = G->nb_sommets;
  int *d = distances(G, 0);
  *a = 0;
  max = 0;
  for (i = 0; i < n; i++) {
    if (d[i] > max) {
      printf(" - %i\n", i);
      max = d[i];
      *a = i;
    }
  }
  free(d);
  d = distances(G, *a);
  *b = *a;
  max = 0;
  for (i = 0; i < n; i++) {
    if (d[i] > max) {
      printf(" + %i\n", i);
      max = d[i];
      *b = i;
    }
  }
  free(d);
  return (max);
}


/* Q7 : fonction pour résoudre un labyrinthe donné par un graphe.
 * Pour trouver un chemin de l'entrée vers la sortie, je traverse le graphe
 * en partant de la sortie... */
int *resoudLabyrinthe(GrapheListe G, int entree, int sortie)
{
  int n = G->nb_sommets;
  int *pere = malloc(n * sizeof(int));
  int u, v;
  Tile F = tileVide();
  ListeAdj L;

  for (u = 0; u < n; u++) {
    pere[u] = -2;
  }

  pere[sortie] = -1;
  entile(sortie, 0, 0, F);
  while (!tileEstVide(F)) {
    defile(F, &u, NULL, NULL);
    for (L = G->Adj[u]; L != NULL; L = L->suivant) {
      v = L->but;
      if (pere[v] == -2) {
        pere[v] = u;
        if (v == entree) {
          return (pere);
        }
        entile(v, 0, 0, F);
      }
    }
  }
  free(pere);
  return (NULL);
}

/* Comme je parcours le graphe en partant de la sortie, il est tres facile
 * d'afficher le chemin dans l'ordre... */
void afficheChemin(int *pere, int entree, int sortie)
{
  int i, d;
  if (pere == NULL) {
    printf
        ("Il n'y a pas de chemin pour aller de la case %i vers la case %i.\n",
         entree, sortie);
  } else {
    printf("On part de la case %d, et :\n", entree);
    for (i = entree, d = 1; i != sortie; i = pere[i], d++) {
      printf("  - on va dans la case %i,\n", i);
    }
    printf
        ("  - on arrive dans la case %i. Il fallait %i déplacements pour arriver jusqu'ici...\n",
         sortie, d);
  }
}


/* Q8 : fonction qui transforme le tableau "pere" en un tableau utilisable par
 * les fonctions d'affichages des grilles rectangulaires ou hexagonales.
 *
 * OUPS, erreur de ma part : il fallait aussi la taille du graphe... */

char *transformePere(GrapheListe G, int *pere, int depart, int arrivee)
{

  if (pere == NULL) {
    return (NULL);
  }

  int i;
  int n = G->nb_sommets;
  char *S = malloc(n * sizeof(char));
  for (i = 0; i < n; i++) {
    S[i] = ' ';
  }
  S[depart] = '@';
  S[arrivee] = '$';
  for (i = pere[arrivee]; i != depart; i = pere[i]) {
    S[i] = '.';
  }
  return (S);
}