#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "graphe_flot_type.h"
#include "util_flot.h"

int cut(GRAPHE_FLOT g, int source, int dest)
{
  int N, res_in = 0, res_out = 0;
  N = g.nb_sommets;
  for (int i = 0; i < N; i++)
  {
    if (g.adj[source - 1][i] == 1)
      res_in += g.flot[source - 1][i];
    if (g.adj[i][dest - 1] == 1)
      res_out += g.flot[i][dest - 1];
  }
  if (res_in != res_out)
    printf("Warning, Graph is not conservative \n");
  return res_out;
}

int flot_admissible(GRAPHE_FLOT g)
{
  int N, result = 1;
  N = g.nb_sommets;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      if (g.adj[i][j] != 0)
        if (g.flot[i][j] > g.capacite[i][j])
        {
          printf("Flot %d non adminissible (>%d) sur arc %d -> %d \n",
                 g.flot[i][j], g.capacite[i][j], i + 1, j + 1);
          result = 0;
        }
  return result;
}

int flot_conservatif(GRAPHE_FLOT g, int source, int dest)
{
  int N, result = 1;
  N = g.nb_sommets;
  for (int sommet = 0; sommet < N; sommet++)
  {
    int flot_in, flot_out;
    if ((sommet != source - 1) && (sommet != dest - 1))
    {
      flot_in = 0;
      flot_out = 0;
      for (int i = 0; i < N; i++)
      {
        if (g.adj[i][sommet] != 0)
          flot_in += g.flot[i][sommet];
        if (g.adj[sommet][i] != 0)
          flot_out += g.flot[sommet][i];
      }
      if (flot_in != flot_out)
      {
        printf("Warning: flot non conservatif pour noeud %d: in(%d), out(%d)\n",
               sommet + 1, flot_in, flot_out);
        result = 0;
      }
    }
  }
  return result;
}

/* modifie le graphe en argument et renvoit le nouveau flot */
int ford_fulkerson(GRAPHE_FLOT g, int source, int dest)
{
  int N = g.nb_sommets;
  int finit = 0;
  int step = 0;
  for (int i = 0; i < N; i++)
  {
    g.marque[i] = 0;
  }
  g.marque[source - 1] = 1;
  printf("Starting Ford-Fulkerson\n");
  printf("source = %d\n", source);
  printf("dest = %d\n", dest);
  printf("Cut=%d\n", cut(g, 11, 10));
  while (!finit)
  {
    step++;
    finit = 1;
    for (int i = 0; i < N; i++)
    {
      if (g.marque[i])
      {
        printf("treating %d\n", i + 1);
        for (int j = 0; j < N; j++)
          if ((g.adj[i][j] == 1) && (!g.marque[j]))
          {
            printf("checking %d -> %d\n", i + 1, j + 1);

            if (g.flot[i][j] < g.capacite[i][j])
            {
              g.marque[j] = i + 1;
              printf("marking  %d with %d\n", j + 1, i + 1);
              finit = 0;
            }
          }
        for (int j = 0; j < N; j++)
          if ((g.adj[j][i] == 1) && (!g.marque[j]))
            if (g.flot[j][i] > 0)
            {
              printf("checking %d -> %d\n", j + 1, i + 1);

              g.marque[j] = -(i + 1);
              printf("marking  %d with %d\n", j + 1, -(i + 1));
              finit = 0;
            }
      }
    }
    /* printf("Step %d, marque: \n",step); */
    /* for (int i=0; i<N; i++) */
    /* 	printf(" %d ",g.marque[i]); */
    /* getc(stdin); */
    if (g.marque[dest - 1] != 0)
    {
      printf("Found a chain:");
      int visitor = dest - 1, next;
      while (visitor != source - 1)
      {
        printf(" %d .... ", visitor + 1);
        if (g.marque[visitor] > 0)
        {
          next = g.marque[visitor] - 1;
          g.flot[next][visitor] = g.flot[next][visitor] + 1;
          visitor = next;
        }
        else
        {
          next = -(g.marque[visitor]) - 1;
          g.flot[visitor][next] = g.flot[visitor][next] - 1;
          visitor = next;
        }
        if (g.marque[visitor] == 0)
        {
          printf("error");
        }
      }
      // affiche_flot_mat(stdout,g);
      printf("new Cut=%d\n", cut(g, 11, 10));
      for (int i = 0; i < N; i++)
      {
        g.marque[i] = 0;
      }
      g.marque[source - 1] = 1;
    }
  }
  return 0;
}

int *dijkstra_flot(GRAPHE_FLOT g, int source)
{
  int *dist, N, tous_marques = 0;

  N = g.nb_sommets;
  dist = (int *)malloc(N * sizeof(int));
  if (dist == (int *)NULL)
  {
    printf("Error: no more memory\n");
    exit(EXIT_FAILURE);
  }

  for (int i = 0; i < N; i++)
    dist[i] = 214748364; /* Attention, si on utilise  2^31-1 ca ne marche pas
                            (debordement de capacité) -> j'ai enlevé les unité */
  dist[source - 1] = 0;

  for (int i = 0; i < N; i++)
    g.marque[i] = 0;

  g.marque[source - 1] = 1;

  tous_marques = 0;
  while (!tous_marques)
  {
    // un tour de la formule de Dijkstra
    for (int i = 0; i < N; i++)
    {
      int min = 214748364;
      if (g.marque[i] == 0)
      { /* prédecesseurs de i: colone i */
        for (int j = 0; j < N; j++)
        {
          if (g.adj[j][i] == 1)
          {
            /* min_j(dist[j]+P(ji)) */
            int temp = dist[j] + g.flot[j][i];
            min = temp < min ? temp : min;
          }
        }
        min = min < dist[i] ? min : dist[i];
        dist[i] = min;
        // printf("p[%d][%d]=%d\n",source,i,min);
      }
    }
    int min = 214748364, index_min = 0;
    tous_marques = 1;
    // Marquage de la distance min trouvé
    for (int i = 0; i < N; i++)
    {
      if (g.marque[i] == 0)
      {
        // printf("%d non marqué\n",i+1);
        tous_marques = 0;
        if (dist[i] < min)
        {
          min = dist[i];
          index_min = i;
        }
      }
    }
    g.marque[index_min] = 1;
  }
  for (int i = 0; i < g.nb_sommets; i++)
    printf("dist[%d]=%d\n", i + 1, dist[i]);
  return dist;
}

int valeur_flot(GRAPHE_FLOT g, int source, int dest)
{
  int s = 0, d = 0;

  for (int i = 0; i < g.nb_sommets; i++)
  {
    if (g.adj[i][dest - 1] == 1)
      d += g.flot[i][dest - 1];
    if (g.adj[source - 1][i] == 1)
      s += g.flot[source - 1][i];
  }
  if (s != d)
    printf("problem s=%d, d=%d\n", s, d);
  return d;
}
