/*********************************************************************
 *                 Traveller Salesman algorithm implemented          *
 * By              : Arash DAKLAN                                    *
 * Date            : September 2015                                  *
 * Course Program  : initiation a l'algorithmique system             *
 * Proffessor      :   Xavier Gandibleux                             *
 * *******************************************************************/



/* Warning: This program, when executed in /bin generates two groups of
   files and saves them in the currently empty directory /temp. The
   files of these two groups have extensions .xe or .txt. The previous
   are the scripts produced by the program te become exetutable later
   via chmod comand and when executed produce the plots by gnuplot. The
   .txt files are the data file produced by program and used by the .xe
   files in the process of drawing the plot by gnuplot.
   The program reads the dat from a text file in the format already
   prepared. It is possible to use any data file in the format of the
   existing in the dirctory /dat.
*/

#include<stdio.h>
#include<math.h>
#include<time.h>

#define N 16

/**********************************************************************
 *                         Function Prototypes                        *
 *********************************************************************/

//We use this function to initialize hamiltonian_path matrix and also
//to initialize a test matrix in the fucntion produce_hamiltonia_path
//in odere to prevent a city from being chosen twice

void initialize_1D(int n, int array_1D[n]);

void initialize_2D(int n, float array_2D[n][n]);


//This function produces a symmetrin N by N matrix containig the
//distnaces between cities
void produce_distance_array(int n, float distance[n][n],
			   float coordinate[n][2]);

//This function produces the final result we are searching for the
//wnated hamiltonian path is being produced as a series of numbers
//each correspoinding to a city. We read in the main routine the
//elements of this array in order and one by one then we choose the
//corresponding name of the city from the matrix defined and
//initialized in main
void produce_hamiltonian_path(int n, int hamiltonian_p[n]);


//This function modifies the hamiltonian path replacing it with the one that always
//choses the nearest city to the current one
void modified_hamiltonian(int n, int hamiltonian_p[n], float distance[n][n]);


//This function measures the path-length travelled by the traveller
float path_length(int n, float[n][n], int hamiltonian_p[n]);

//This fucntion finds the nearest city fo a given city
int find_nearest(int index, int n, int test[n], float distance[n][n]);

//This function finds if with a change in the order of the cities we
//can make the travel shorter
void find_opt_path(int n, float distance[n][n],
		   int hamiltonian_p[n]);
/*
//This function implements the 2-opt algorithme. This function calls
//two other functions to do this job. One is the one right above, called
//find_opt_path which finds if there is a shorter path and after finding
//the corresponging answer, changes the order of the cities. In this
//last process it calls repeatedly another fucntion called swap() which
//just swaps two elemnts of the matrix passed to it as the addresses.
void opt_hamiltonian(int nb, int hamiltonian_p[nb+1],
		     float distance[nb][nb]);
*/

//This is the function that receives an array and the addresses of
//two elemts to be changed and changes them.
void swap(int *first, int *second);

// Thes two last functions are to display the matrixes
void display_1D(int n, int array_1D[n]);

void display_2D(int n, int m, float array_2D[n][m]);


//This function saves the results in a file to be managed then to
//plot the diagram with gjuplot
void gnu_results(int n, int hamiltonian_p[n], float coordinate[n][2],
		 float distance[n][n], char file_name[10]);


//This function generates the script files to be used for ploting
//the final reslt with gnuplot
void gnu_plot_file(char file_name[10], char source[10], char title[25],
		   char destination[10], float path_langth);




char city_names[N][25] = {"Carquefou", "Nort-sur-Erdre", "Ancenis", "Saint-Luce-sur-Loire", "Rouans", "Vertou", "Clisson", "Machecoul", "Vieillevigne", "Savenay",
			    "Orvault", "Saint-Herblain", "Reze", "Vallet",
			    "Saint-Philbert-de-GL", "Bouin"};



/**********************************************************************
 *                            MAIN FUNCTION                           *
 *********************************************************************/

int main(void)
{
  /*Partie declaration */

  float total_distance;
  int hamiltonian_path[N];
  float array_distance[N][N];
  float coordinate[N][2];




  /*Partie Execution*/

  //initializing the arrays
  initialize_1D(N, hamiltonian_path);
  initialize_2D(N, array_distance);

  //this parts generates the distance array and the array for the hamiltonian path
  produce_distance_array(N, array_distance, coordinate);
  produce_hamiltonian_path(N, hamiltonian_path);


  printf("\nHere comes the hamiltonian path for the cities: \n\n");
  display_1D(N, hamiltonian_path);

  //evaluates the entire travelled length
  total_distance = path_length(N, array_distance, hamiltonian_path);

  printf("The total distqnce is = %f\n", total_distance);
  //Produces the data in a text file to be used by gnuplot-script
  gnu_results(N, hamiltonian_path, coordinate, array_distance, "./../temp/hamiltonian.txt");

  //generates a script for gnuplot.
  gnu_plot_file("./../temp/hamiltonian.xe", "./../temp/hamiltonian.txt", "Hamiltonian Path",  "./../temp/plot_1.png", total_distance);



  printf("\nThe modified hamiltonian path is:\n ");
  modified_hamiltonian(N, hamiltonian_path, array_distance);
  display_1D(N, hamiltonian_path);


  //evaluates teh total distance
  total_distance = path_length(N, array_distance, hamiltonian_path);
  //generates the datd file to be used by gnuplot-script
  gnu_results(N, hamiltonian_path, coordinate, array_distance, "./../temp/modified.txt");

  //generates gnuplot script file
  gnu_plot_file("./../temp/modified.xe", "./../temp/modified.txt",
		"Modified Hamiltonian Path", "./../temp/plot_2.png",
		total_distance);


  printf("The distance traveled in this modified version = %f\n",
	 total_distance);

  find_opt_path(N, array_distance, hamiltonian_path);
  printf("\nThe List of the cities after otimization\n ");

  display_1D(N, hamiltonian_path);

  //evaluates teh totla distance
  total_distance = path_length(N, array_distance, hamiltonian_path);


  printf("\nTotal distance traveled in optimized algorithm = %5.2f\n", total_distance);

  //generates the data file to be used by gnuplot-script
  gnu_results(N, hamiltonian_path, coordinate, array_distance,"./../temp/optimum.txt");

  //generates gnuplot script-file
  gnu_plot_file("./../temp/optimum.xe", "./../temp/optimum.txt", "2-Opt", "./../temp/plot_3.png", total_distance);
  system("/bin/gnuplot ./../temp/hamiltonian.xe");
  system("/bin/gnuplot ./../temp/modified.xe");
  system("/bin/gnuplot ./../temp/optimum.xe");







  return 0;
}

/**********************************************************************
 *                       Definition of Functions                      *
 *********************************************************************/

//This fucntion gets an integer for the dimension of the array and the
//address of the array and returns nothing

void initialize_1D(int n, int array_1D[n])
{
  int i;
  for (i = 0; i < n; i++)
    array_1D[i] = 0;
}

//This function gets an integer for the dimension of a square matrix
//and the address of a matrix whose elements are floating point reals
//and returns nothing

void initialize_2D(int n, float array_2D[n][n])
{
  int i, j;

  for (i = 0; i < n; i++)
    for (j = 0; j < n; j++)
      array_2D[i][j] = 0;
}

//This function gets an integer for the dimension of the matrix and
//the address of the matrix as its argument and changes the lements of
//the matrix to which it has got the address. the elements
//distance[i][j] are the distance between the cities i and j, and
//because we have considered the distance betweeen cities to be
//symmteric, the resulting matrxi is symmetric
void produce_distance_array(int n, float distance[n][n],
			    float coordinate[n][2])
{
  int i, j, k = 0;  //indexes of the matrix

  //coordinates of the two cities which we want to measure their
  //distance
  float x_1, y_1, x_2, y_2;

  //the square root of this variable will be the distance we are
  //interested in
  float distance_squared;

  for (i = 0; i < n; i++)
    {
      for (j =0; j < 2; j++)
	{
	  scanf("%f", &x_1);
	  coordinate[i][j] = x_1;
	}
    }

  for (i = 0; i < n; i++)
    {
      x_1 = coordinate[i][k++];
      y_1 = coordinate[i][k];
      k=0;
      for (j = 0; j < n; j++)
	{
	  if(i < j )
	    {
	      x_2 = coordinate[j][k++];
	      y_2 = coordinate[j][k];
	      distance_squared = pow((x_1 - x_2), 2.0) +
		pow((y_1 - y_2), 2.0);
	      distance[i][j] = sqrt(distance_squared);
	      distance[j][i] = distance[i][j];
	    }
	  k = 0;
	}
      k =0;
    }

}

//This is the function that produces what we want: The Hamiltonian Path
//This function getes an integer as the dimension of the 1_d array and
//using a random process produces the sequence of numbers corresponding
//to cities in a way that each city comes just once. If we connect the
//last member to the firts element then we have the result we wanted
void produce_hamiltonian_path(int n, int hamiltonian_p[n])
{
  int i = 0, j;

  //This array is going to be initialized with zeros. Then each time a
  //random number has been chosen the corresponding element of this array
  //will be set to 1 and when producing the random number we can chech
  //if it has been chosen before or not.
  int test[n];

  srand(time(NULL));

  initialize_1D(n , test);

  while(i < n)
    {
      j = rand() % n;

      if (test[j] == 0)
	{
	  hamiltonian_p[i] = j;
	  i++;
	  test[j] = 1;
	}
    }

}

//This function calculates the total length travelled by the traveller
float path_length(int n, float distance_array[n][n],
		  int hamiltonian_p[n])
{
  float sum = 0;
  int i = 0;

  /*the next variable is here to save the index of the first city. We will use this
    to add the disatnce betwen the first and the last cities to the sum the for-loop
    calculates.
*/
  int fix;

  // the next two variables are going to used to index the elements of the disatnce array
  int row_index;
  int col_index;

  fix = row_index = hamiltonian_p[i];

  for (i = 1; i < n; i++)
    {
      col_index = hamiltonian_p[i];
      sum += distance_array[row_index][col_index];
      row_index = col_index;

    }
  sum += distance_array[col_index][fix];
  return sum;
}

//This function gets as argumnet the indexof city and finds the nearest city to it and
//returns the index to the city it finds
int find_nearest(int index, int n, int test[n], float distance[n][n])
{
  int i = 0, j;
  float min;
  int min_index; //this is the variable that will be returned to the caller function
  if (index != i)
    {
      while(test[i] == 1)
	i++;
      min = distance[index][i];
    }
  else
    {
      i++;
      while(test[i] == 1)
	i++;
      min = distance[index][i];
    }
  min_index = i;
  j = i;
  for(i = j+1; i < n ; i++)
    {
      if (test[i] == 0 && distance[index][i] < min)
	{
	  min = distance[index][i];
	  min_index = i;
	}

    }
  return min_index;
}

//This function is the modified hamiltonian path which selects the cities one by one
//based on their distance to the curent city. Based on this new algorithm traveller
//in each city selects the city nearest to the one (s)he currently resides.
void modified_hamiltonian(int n, int hamiltonian_p[n], float distance[n][n])
{
  int i = 0 , index;
  int test[n];
  initialize_1D(n , test);
  index = rand() % n;
  test[index] = 1;
  hamiltonian_p[i] = index;

  for(i = 1; i < n; i++)
    {
      index = find_nearest(index, n, test, distance);
      hamiltonian_p[i] = index;
      test[index] = 1;
    }
}


//This function gets a 2-D array whose elements are the distances
//between the cities and and one one dimensional array of
//hamiltonian path and checks if there are shorter paths. If yes
//modifies the hamiltonian_path matrix and repeats this action, until
//reaches to the point where no change is possible to make a shorter
//path.
void find_opt_path(int n, float distance[n][n],
		   int hamiltonian_p[n])
{
  int i, j, number;
  int opt_i=0, opt_j=0, m, p, m_1, p_1;
  float  difference , min_path;

   do
    {
      min_path = 0;
      for(i = 0; i < n-2; i++)
	{
	  for (j = (i + 2)%n; j != (n+i-2)%n; j = (j+1)%n)
	    {
	      m = hamiltonian_p[i]; p = hamiltonian_p[j];
	      m_1 = hamiltonian_p[i+1]; p_1=hamiltonian_p[(j+1)%n];
	      difference = distance[m][p] + distance[m_1][p_1]
		- distance[m][m_1] - distance[p][p_1];

	  if (difference < min_path)
	    {
	      min_path =  difference;
	      opt_i = i;
	      opt_j = j;
	    }
	   }
	}

      number = ((opt_j - opt_i + n) % n ) / 2;
      for (i =0; i < number; i++)
	{
	  opt_i++;
	  swap (&hamiltonian_p[opt_i%n], &hamiltonian_p[opt_j]);
	  opt_j--;
	  if (opt_j < 0) opt_j = opt_j + n;

	}

	} while (min_path < 0);
}

//

void gnu_results(int n, int hamiltonian_p[n], float coordinate[n][2],
		 float distance[n][n], char file_name[10])
{
  int i, j, k, index, index_p;
  float total_distance;
  FILE *fwrite;

  total_distance = path_length(n, distance, hamiltonian_p);
  fwrite = fopen(file_name, "w");
  fprintf(fwrite, "%s", "# x_1-----y_1----------city-------------------x_2---------y_2\n");
  fprintf(fwrite, "#The total ditance travelled = %5.2f\n\n", total_distance);
  for (i=0, j=0, k=0; i < n; i++)
    {
      index = hamiltonian_p[i];
      index_p = hamiltonian_p[k%n];
      fprintf(fwrite, "%7.2f", coordinate[index_p][j++]);
      fprintf(fwrite, "%7.2f", coordinate[index_p][j--]);
      fprintf(fwrite, "  %-25s", city_names[index]);
      k++;
      index_p =hamiltonian_p[k%n];
      fprintf(fwrite, "%10.2f", coordinate[index_p][j++]);
      fprintf(fwrite, "%10.2f\n", coordinate[index_p][j--]);
    }
  fclose(fwrite);
}


//This function generates the script files to be used for ploting
//the final reslt with gnuplot

void gnu_plot_file(char file_name[10], char source[10], char title[25],
		   char destination[10], float path_length)
{
  FILE *fp;
  fp = fopen(file_name, "w");
  if (fp == NULL)
    fprintf(stderr, "Imposible to open %s\n", file_name);

  fprintf(fp, "#!/usr/bin/gnuplot -persist\n");
  fprintf(fp, "set terminal push\n");
  fprintf(fp, "set terminal png\n");
  fprintf(fp, "set output \"%s\"\n", destination);
  fprintf(fp, "set title \"%s %5.2f km\" \n", title, path_length);
  fprintf(fp, "set xlabel \"X\"\n");
  fprintf(fp, "set ylabel \"Y\"\n");
  fprintf(fp, "set xrang[0:100]\n" );
  fprintf(fp, "set yrang[0:100]\n");
  fprintf(fp, "plot \"%s\" u 1:2:($4-$1):($5-$2) with vectors,\"\" u 1:2:3 with labels\n", source);
  fprintf(fp, "set terminal x11\n");
  fprintf(fp, "set output\n");
  fprintf(fp, "set terminal pop\n");
  fprintf(fp, "set terminal x11\n");
  fprintf(fp, "replot");
  fflush(fp);
  fclose(fp);
}



void swap(int *first, int *second)
{
  int temp;

  temp = *first;
  *first = *second;
  *second = temp;
}

//These two last functions dipaly the result
void display_1D(int n, int array_1D[n])
{
  int i, j;
  for (i =0; i < n; i++)
    {
      j = array_1D[i];
      printf("%s\n", city_names[j]);
    }
}


void display_2D(int n, int m, float array_2D[n][n])
{
  int i, j;
  for (i = 0; i < n; i++)
    {
      for (j = 0; j < m; j++)
	printf("Tab[%d][%d] = %5.2f \n", i+1, j+1, array_2D[i][j]);
      printf("\n");
    }
}