// Adrien Bertrand
// Alexandre Gensse
// TIPE 2010-2011 - ISEN Toulon

// Version 1.2.1337 (2)


/*#include "GfxLibSupport.h"
#include <math.h>
#include "TPfct.h"*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
#include <stdbool.h>

#define Limitxy 10000
#define XI coords[0][i]
#define XJ coords[0][j]
#define YI coords[1][i]
#define YJ coords[1][j]
#define alpha 1.2
#define beta 0.9
#define txevap 0.4
#define txenrich 0.9
#define NOMBREIT 30
#define txstart 0.01


// TODO : EMPECHER GENERATION DE MM VILLE


int coords[2][Limitxy+1];
bool distanceVilles(int,float[][],int[][]);
int indiceVilleSuivante(int,float[][],float[][],int,int[]);
/*
extern int LargeurFenetre;
extern int HauteurFenetre;


void traceAxes(void)
{
     couleurCourante(255,215,0);
     epaisseurDeTrait(2);
     ligne(0,500,1000,500);
     ligne(500,0,500,1000);
}

void traceCourbePoint(x,y)
{
     couleurCourante(0,255,255);
     epaisseurDeTrait(4);
     point(convertitCoordonnee(x),convertitCoordonnee(y));
}

void traceCourbeSegment(x1,y1,x2,y2)
{
     couleurCourante(50,255,200);
     epaisseurDeTrait(2);
        x1=convertitCoordonnee(x1);
        y1=convertitCoordonnee(y1);
        x2=convertitCoordonnee(x2);
        y2=convertitCoordonnee(y2);
        ligne(x1,y1,x2,y2);
}
*/

bool genererVilles(int nombreVille) // Genere des coordonnÈes alÈatoires
{
    int i;
    int randomx,randomy;

    coords[0][0]=coords[1][0]=5000; // CoordonnÈes de la premiere ville

    srand(time(NULL)); // Initialisation du random
    for(i=1;i<=nombreVille;i++) // Calcul des coordonnÈes
    {
         randomx= rand()%(1+Limitxy);
         randomy= rand()%(1+Limitxy);
         coords[0][i]=randomx;
         coords[1][i]=randomy;

    }

    for(i=0;i<=nombreVille;i++)
    printf("%i\n",coords[0][i]);
    printf("\n");
    for(i=0;i<=nombreVille;i++)
    printf("%i\n",coords[1][i]);

    return true;
}


bool distanceVilles(int nombreVille,float dist[][nombreVille+1],int coords[2][Limitxy+1])
     // Calcule la distance entre chaque couple de villes
{
     int i,j;

     for(i=0;i<=nombreVille;i++) // Pour chaque x
     {
          for(j=0;j<=nombreVille;j++) // Pour chaque y
          {
//               printf("\n%i - %i    ",i,j);
               dist[i][j]=sqrt((YJ-YI)*(YJ-YI)+(XJ-XI)*(XJ-XI)); // Calcul [xy]
//               printf("%f",dist[i][j]);
          }
//          printf("\n");
     }
     return true;
}

int calculeIndiceProba(int nombreVille,float proba[]) // En fonction du tableau de proba, return l'indice suivant
{
        int i,indice=0;
        float sommeProba[nombreVille+1],u;

        sommeProba[0]=proba[0];

        for(i=1;i<=nombreVille;i++)
        {
           sommeProba[i]=sommeProba[i-1]+proba[i];
        }
//        printf(" \n----------------------------------------Somme proba : %g",sommeProba[nombreVille]);
        u=rand()*sommeProba[nombreVille]/32767.0f; // u = nombre aleatoire
//        printf("\n variable u : %f",u);

        for(i=0;i<=nombreVille;i++)
        {
           if(u<sommeProba[i])
           {
              indice=i;
              break;
           }
        }
    return indice;
}


int indiceVilleSuivante(int nombreVille,float dist[][nombreVille+1],float pher[][nombreVille+1],int indiceVilleActuelle,int ordreVille[])
    // Fonction qui calcule les probas, et retourne la ville suivante

{
    int i,j,l;
    float pnum=0,pden=0,proba[nombreVille+1];

    for(i=0;i<=nombreVille+1;i++) proba[i]=0; // On rÈinitialise les probas

    /*for(i=0;i<=nombreVille;i++)
    printf("------------%f\n",dist[indiceVilleActuelle][i]);*/

    for(j=1;j<=nombreVille;j++) //Pour chaque ville, calcule du dÈnominateur de la fonction
    {
            if(dist[indiceVilleActuelle][j]!=0) // Si ville j different villeActuelle
            {
            pden=pden+(pow(pher[indiceVilleActuelle][j],alpha)*pow((1/dist[indiceVilleActuelle][j]),beta)); // ajout au denominateur
            }
    }

    for(j=0;j<=nombreVille;j++) // Pour chaque ville
    {
        if (dist[indiceVilleActuelle][j]!=0) // Si ville j different villeActuelle
        {
        pnum=(pow(pher[indiceVilleActuelle][j],alpha)*pow((1/dist[indiceVilleActuelle][j]),beta)); // calcul de la proba numerateur de ville j
        proba[j]=pnum/pden; // calcul proba[j]
        }

        for(l=0;l<=nombreVille;l++) // si on est deja allÈ ‡ la ville j, on met proba ‡ zÈro
        {
           if (ordreVille[l]==j) proba[j]=0;
        }
//        printf("\nproba de la ville %i : %f",j,proba[j]);
    }
    return calculeIndiceProba(nombreVille,proba);
}


void evaporerPher(int nombreVille,float pher[][nombreVille+1]) // Evaporation des pheromones
{
int tmp,tmp2;

    for (tmp=0;tmp<=nombreVille;tmp++) // pour chaque ville
    {
        for (tmp2=0;tmp2<=nombreVille;tmp2++) // pour chaque 2∞ ville
        {
          pher[tmp][tmp2]=(1-txevap)*pher[tmp][tmp2]; // evaporation des pheromones entre ces deux villes
        }
    }
}

void posagePher(int nbv, int nbf, float dist[][nbv+1],float pher[][nbv+1],int ordreVille[nbv+1])
     // posage des pheromones
{
   int i;
   for(i=0;i<nbv;i++)
   pher[i][i+1]=pher[i+1][i]=1/(dist[ordreVille[0]][ordreVille[nbv]]*nbf); // pher depend de la distance parcourue au total
}

void inverserVilles(int nbv,int ordreVille[], float dist[][nbv+1])
{
    int i,j,tmp,levier=1;
    float distot=0,distot2=0;
    printf("\nINVERSER");
    levier=0;
    printf(" --------levier = %i ",levier);
    for(i=0;i<nbv;i++)
    {
        printf("\n----++++++++++++++++------i=%i",i);

        for(j=0;j<nbv;j++)
        {
           printf("\n-j1=%i",j);
           distot=distot+dist[ordreVille[j]][ordreVille[j+1]];
        } printf("distot  = %f",distot);

           tmp=ordreVille[i];
           ordreVille[i]=ordreVille[i+1];
           ordreVille[i+1]=tmp;
           levier=1;

        for(j=0;j<nbv;j++)
        {
           printf("\n--j2=%i",j);
           distot2=distot2+dist[ordreVille[j]][ordreVille[j+1]];
        } printf("distot2  = %f",distot2);

        if (distot<=distot2)
        {
           tmp=ordreVille[i];
           ordreVille[i]=ordreVille[i+1];
           ordreVille[i+1]=tmp;
        } else inverserVilles(nbv,ordreVille,dist);

        distot=0;
        distot2=0;
    }

}

void go(int nbv,float dist[][nbv+1],float pher[][nbv+1]) // Lancement du calcul
{

    int i,j,k,indiceActuel,indiceSuivant,nbf,ordreVille[nbv+1],ordreVilleOpt[nbv+1];
    float distancetot=0,distancetot2=0;

    for(i=0;i<=nbv;i++) // Pour chaque couple de ville on initialise le taux de pheromones ‡ txstart
    {
       for(j=0;j<=nbv;j++)
            pher[i][j]=txstart;
    }

    printf("\n\nNombre de fourmis ? \n");
    scanf("%i",&nbf); // EntrÈe du nombre de fourmis
    printf("\n");
    if (nbf<=0) main(); // Si nombre incorrect on recommence

    for(k=1;k<=NOMBREIT;k++) // Pour Chaque itÈration
    {

    for(j=1;j<nbf+1;j++) // Pour chaque fourmis
    {
//    printf("\n\nNumero de la fourmi : %i",j);
    ordreVille[0]=0; // On rÈinitialise ordreVille[]
    for(i=1;i<=nbv;i++)
    ordreVille[i]=-1;

    indiceActuel=0; // On part de zÈro
    //printf("\n - - - FOURMI Numero %i, iteration numero %i",j,k);

    for(i=0;i<nbv;i++) // On calcule l'ordre des villes
    {
//       printf("\n\nIndice actuel : %i\n",indiceActuel);
       indiceSuivant=indiceVilleSuivante(nbv,dist,pher,indiceActuel,ordreVille); //Calcul indiceSuivant
       ordreVille[i+1]=indiceSuivant;
       indiceActuel=indiceSuivant;
    }

    //printf("\nOrdre final :\n");
    //printf("    %i",ordreVille[0]);
    //for(i=1;i<=nbv;i++)
    //printf(" - %i",ordreVille[i]);
    //printf("\n\n");
    for(i=0;i<nbv;i++) // Calcul de la distance totale parcourue
    {
            distancetot2=distancetot2+dist[ordreVille[i]][ordreVille[i+1]];
    }
    if(distancetot2<distancetot || distancetot==0)
            {
                 distancetot=distancetot2;
                 for(j=0;j<=nbv;j++)
                 {
                    ordreVilleOpt[j]=ordreVille[j];
                 }
            }
//    printf("\n\n\t Distance parcourue : %f\n",distancetot2);
    distancetot2=0;
    posagePher(nbv,nbf,dist,pher,ordreVille); // on pose les pheromones aprÈs l'evaporation
    }
    evaporerPher(nbv,pher); // on evapore les pheromones a la fin de l'iteration
    printf("Iteration numero : %i\n",k);
    }

    inverserVilles(nbv,ordreVilleOpt,dist);
    distancetot=0;
    for(j=0;j<nbv;j++)
        {
           distancetot=distancetot+dist[ordreVille[j]][ordreVille[j+1]];
        }

    printf("\n\n\t Distance Optimale : %f\n",distancetot);
    printf("\nOrdre final :\n");
    printf("    %i",ordreVilleOpt[0]);
    for(i=1;i<=nbv;i++)
    printf(" - %i",ordreVilleOpt[i]);
    printf("\n\n");


    printf("\n\n");
    for(i=0;i<=nbv;i++)
    {
       //printf(" Ville numero %3i  :  %i  -  %i\n",i,coords[0][ordreVilleOpt[i]],coords[1][ordreVilleOpt[i]]);
       printf("%i\n",coords[0][ordreVilleOpt[i]]);
    }
    printf("\n\n");
        for(i=0;i<=nbv;i++)
    {
       printf("%i\n",coords[1][ordreVilleOpt[i]]);
    }
}


int main(void)
{
    bool done=false;
    int nbv;


    printf("\nNombre de villes ?\n"); // entrÈe du nombre de ville
    scanf("%i",&nbv);
    if (nbv<=1) main();
    nbv=nbv-1; // On a deja la ville zÈro donc on en enleve une


    float dist[nbv+1][nbv+1]; // initialisation des matrices carrÈes [nbv+1][nbv+1]
    float pher[nbv+1][nbv+1];

    done=genererVilles(nbv); // on gÈnere les villes
    if (!(done)) printf("ERROR 1 : genererVilles()");
    done=false;

    done=distanceVilles(nbv,dist,coords); // on calcule les coordonnÈes
    if (!(done)) printf("ERROR 1 : genererVilles()");
    done=false;


    retry:

    go(nbv,dist,pher); // et on y go !

    printf("\n\n");


    system("PAUSE");
    system("cls");
    goto retry;
    main();
    return 0;


}