#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.poids[source-1][i];
      if (g.adj[i][dest-1]==1)
	res_out += g.poids[i][dest-1];
    }
  if (res_in!=res_out)
    printf("Warning, Graph is not consevative \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.poids[i][j]>g.flot[i][j])
	  {
	    printf("Flot %d non adminissible (>%d) sur arc %d -> %d \n",
		   g.poids[i][j],g.flot[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.poids[i][sommet];
	      if (g.adj[sommet][i] != 0)
		flot_out+=g.poids[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.poids[i][j]<g.flot[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.poids[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.poids[next][visitor]=g.poids[next][visitor]+1;
		  visitor=next;
		}
	      else
		{
		  next=-(g.marque[visitor])-1;
		  g.poids[visitor][next]=g.poids[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.poids[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.poids[i][dest-1];
      if (g.adj[source-1][i]==1)
	s+=g.poids[source-1][i];
    }
  if (s!=d)
    printf("problem s=%d, d=%d\n",s,d);
  return d;
}
