#include "bellman.h"

/* Le tableau suivant doit servir à contenir les degrés extérieurs 
des sommets du graphe */
static int * degreExt;

/* La fonction met les degrés extérieurs des sommets du graphe dans
   le tableau. */
static void calculDegreExt(void)
{
  int i;
  PERE * adrPere;

  for (i = 0; i < ordre; i++) degreExt[i] = 0;
  for (i = 0; i < ordre; i++)
    {
      adrPere = graphe[i];
      while (adrPere != NULL)
	{
	  degreExt[adrPere->nomPere]++;
	  adrPere = adrPere->suivant;
	}
    }
  /* Les deux instructions qui suivent ne sont utiles que 
     pour la période de tests */
  printf("Les degres exterieurs calcules sont :\n");
  ecrireValeurs(degreExt); 
}

/******************  fonction triTopologique  *******
  La fonction commence par allouer le tableau degreExt. 
  La fonction triTopologique tente d'effectuer un tri topologique des 
  sommets du graphe. 
  - S'il y a un circuit dans le graphe, la fonction retourne 0.
  - S'il n'y pas de circuit, la fonction remplit le tableau num qui
  doit contenir la numérotation topologique. Les numéros topologiques 
  sont compris entre 0 et ordre - 1. La fonction remplit aussi le tableau 
  deNum qui donne l'inverse du tableau num : si num[sommet] = numero, 
  alors deNum[numero] = sommet. La fonction retourne 1.
  La fonction desalloue le tableau degreExt.
*/
int triTopologique(void)
{
  int i;
  int numero = ordre-1;
  int sommet;
  PERE * adrPere;
  int unPere;

  degreExt = (int *) malloc(ordre*sizeof(int));
  if (graphe == NULL)
    {
      printf("manque de place\n");
      exit(1);
    }
  calculDegreExt();
  for (i = 0; i < ordre; i++)
    if (degreExt[i] == 0) empiler(i);
  while(!estVide())
    {
      sommet = depiler();
      num[sommet] = numero;
      deNum[numero--] = sommet;
      adrPere = graphe[sommet];
      while (adrPere != NULL)
	{
	  unPere = adrPere->nomPere;
	  degreExt[unPere]--;
	  if (degreExt[unPere] == 0) empiler(unPere);
	  adrPere = adrPere->suivant;
	}
    }
  if (numero >= 0)
    {
      free(num);
      free(deNum);
      free(degreExt);
      return 0;
    }
  /* Les deux instructions qui suivent ne sont utiles que 
     pour la période de tests */
  printf("Les numeros topologiques calcules sont :\n");
  ecrireValeurs(num); 
  printf("Inverse de la numerotation topologique :\n");
  ecrireValeurs(deNum); 
  free(degreExt);
  return 1;
}