#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define N 50

//Travelling sales man problem , travelling between 6 cities.

//initializing the path lengths between cities and the paths to be included
//in population

void initialize(int pathlen[][6],int path[][6])
{
	int i,j,k;

	//obtaining pathlengths
	for(i=0;i<6;i++)
	{
		for(j=0;j<6;j++)
		{
			if(j<i)           //path length from a to b will be same as b to a
			{
				pathlen[i][j]=pathlen[j][i];
			}

			if(j==i)         // path length from a to a will be 0
			{
				pathlen[i][j]=0;

			}

			if(j>i)         // rest initialized
			{
				do{
				pathlen[i][j]= random(20);
				}while(!pathlen[i][j]);
			}
		}

	}

	// display the path lengths

	printf("\n\tThe PATH LENGTHS ARE: \n" );

	for(i=0;i<6;i++)
	{
		for(j=0;j<6;j++)
		{
			printf(" %5d ",pathlen[i][j]);
		}
		printf("\n\n");
	}


	// generating the population

	for(i=0;i<20;i++)
	{
		for(j=0;j<6;j++)
		{
			path[i][j]=random(6);

			for(k=j-1;k>=0;k--)
			{
				if(path[i][j]==path[i][k])  //checking to avoid repeatition
				{
					path[i][j] = random(6);
					k=j;
				}
			}
		}
	}



}

// evaluating the fitness function or total distance

void evaluate(int pathlen[6][6],int path[20][6],int fx[20])
{
	int sum =0,i,j,a,b;

	//obtaing the sum of the path taken
	for(i=0;i<20;i++)
	{
		sum=0;
		for(j=0;j<5;j++)
		{
			a=path[i][j];
			b=path[i][j+1];
			sum=sum+pathlen[a][b];
		}
		fx[i]=sum;

	}

	//display the paths generated
	printf("\n");
	printf("\n\tPATH \t\tf(x) \n\n");
	for(i=0;i<20;i++)
	{
		printf("\t");
		for(j=0;j<6;j++)
		{
			printf(" %d",path[i][j]);
		}
		printf("\t%d",fx[i]);
		printf("\n");
	}

}

//selecting the two points for cross over and then performing partial Crossover

void selection(int fx[20],int pos[2],int posmax[2])
{
	int min1=fx[0],min2=fx[0],i,max1=fx[0],max2=fx[0];
	pos[0]=0;
	pos[1]=0;
	posmax[0]=0;
	posmax[1]=0;
	//calculating the minimum postion
	for(i=1;i<20;i++)
	{
		if(fx[i]<min1)
		{
			min1=fx[i];
			pos[0]=i;

		}
	}
	//calaculating the second minimum position

	for(i=1;i<20;i++)
	{
		if(fx[i]<min2&&i!=pos[0])
		{
			min2=fx[i];
			pos[1]=i;

		}
	}

	//calculating the max position

	for(i=1;i<20;i++)
	{
		if(fx[i]>max1)
		{
			max1=fx[i];
			posmax[0]=i;

		}
	}
	//calculating the second max position

	for(i=1;i<20;i++)
	{
		if(fx[i]>max2&&i!=posmax[0])
		{
			max2=fx[i];
			posmax[1]=i;

		}

	}
	printf("\n\tFIRST MINIMUM=%4d \tPOSITION=%4d\n\tSECOND MINIMUN=%4d \tPOSITION=%4d\n\tFIRST MAXIMUM=%4d \tPOSITION=%4d\n\tSECOND MAXIMUM=%4d \tPOSITION=%4d\n",min1,pos[0],min2,pos[1],max1,posmax[0],max2,posmax[1]);

}

//PERFORMING PARTIAL CROSSOVER

void crossover(int pos[2],int path[][6],int child[2][6])
{
	int crosspt1,crosspt2,j,i,temp,temp1[2][6],temp2;
	//TAKING 2 CROSS POINTS
	do
	{
		crosspt1=random(5);
	}while(crosspt1>2) ;
	do
	{
		crosspt2=random(5);
	}while(crosspt2<=3);
	clrscr();
	printf("\n\n\t The CROSSOVER POINTS ARE : %d , %d ",crosspt1,crosspt2);
	printf("\n\n\tTHE PATHS FOR CROSSOVER ARE");
	printf("\n\n\t\t");

	for(j=0;j<6;j++)
	{
		child[0][j]=path[pos[0]][j];
		printf(" %d",child[0][j]);
	}
	printf("\n\t\t");
	for(j=0;j<6;j++)
	{
		child[1][j]=path[pos[1]][j];
		printf(" %d",child[1][j]);
	}

	int cnt=0;
	//swapping the paths between two crosspoints

	for(j=crosspt1+1;j<=crosspt2;j++)
	{
		temp1[1][cnt]=child[0][j];
		temp1[0][cnt]=child[1][j];
		temp=child[0][j];
		child[0][j]=child[1][j];
		child[1][j]=temp;
		cnt++;

	}
	//performing partial crossover

	int k,m;
	for(m=0;m<2;m++)
	{
		for(i=0;i<crosspt1+1;i++)   //taking the path before crosspoint
		{
			for(j=0;j<cnt;j++)   //comparing the path within crossover point
			{
				if(child[m][i]==temp1[m][j]) //if found then
				{
					if(m==0)   //for child 1
					{
						temp2=temp1[1][j];   //take the path from child2 crossover

						for(k=0;k<6;k++)
						{
							if(child[m][k]==temp2) //if still the path repeats then repeat the process again
							{ temp2=child[1][k];
							  k=0;
							}
						}

						child[m][i]=temp2;   //finally putting the value in child

					}
					else  //for child 2
					{
						temp2=temp1[0][j];
						for(k=0;k<6;k++)
						{
							if(child[m][k]==temp2)
							{temp2=child[0][k];
							 k=0;

							}
						}
						child[m][i]=temp2;
					}


				}


			}
		}
	}

	for(m=0;m<2;m++)
	{
		for(i=crosspt2+1;i<6;i++)   //now chehcking the path after the second cross point
		{
			for(j=0;j<cnt;j++)   //comparing the path within crossover point
			{
				if(child[m][i]==temp1[m][j])  //if found then
				{
					if(m==0)   //for child 1
					{
						temp2=temp1[1][j];   //take the path from child2 crossove
						for(k=0;k<6;k++)
						{
							if(child[m][k]==temp2) //if still the path repeats then repeat the process again
							{temp2=child[1][k];
							 k=0;
							 }
						}
						child[m][i]=temp2;  //finally assigning the value
					}
					else   //for child 2
					{

						temp2=temp1[0][j];
						for(k=0;k<cnt;k++)
						{
							if(child[m][k]==temp2)
							{temp2=child[0][k];
							 k=0;
							 }
						}
						child[m][i]=temp2;
					}

				}


			}
		}
	}
	//display AfTER  CROSSOVER
	printf("\n\tAFTER CROSSOVER\n\t\t");

	for(j=0;j<6;j++)
	{
		printf(" %d",child[0][j]);
	}
	printf("\n\t\t");
	for(j=0;j<6;j++)
	{
		printf(" %d",child[1][j]);
	}


}

//insering the paths in population removing those having maximum populaiton

void insert(int child[2][6],int posmax[2],int path[20][6])
{
	for(int j=0;j<6;j++)
	{
		path[posmax[0]][j]=child[0][j];
		path[posmax[1]][j]=child[1][j];
	}


}

// performing mutation

void mutation(int child[2][6])
{
	int sel=random(2);
	int pos1=random(6);
	int pos2=random(6);
	int temp=child[sel][pos1];
	child[sel][pos1]=child[sel][pos2];
	child[sel][pos2]=temp;
}

void main()
{
	clrscr();
	randomize();

	int pathlen[6][6],path[20][6],fx[20],pos[2],posmax[2],child[2][6];


	printf("\n\t\t\t TRAVELLING SALESMAN PROBLEM ");
	printf("\n\t\t\t_____________________________");
	printf("\n\n\n\t\tTHE TRAVELLING SALES MAN PROBLEM DEALS WITH THE FACT");
	printf("\n\n\t\tTHAT A SALESMAN TRAVELS BETWEEN CITIES TAKING THE PATH");
	printf("\n\n\t\tTHAT IS OF MINIMUN DISTANCE.");

	printf("\n\n\n\t\tTO OBTAIN THE MINIMUM DISTANCE WE USE GENETIC ALGO");
	printf("\n\n\t\tWHERE WE TAKE AN INITIAL POPULATION OF 20 PATHS AND ");
	printf("\n\n\t\tAND THEN THROUGH FITNESS FUNCTION WE OBTAIN THE PATHS ");
	printf("\n\n\t\tWITH MINIMUN DISTANCE AND REPLACE THEM WITH THE CHILDS ");
	printf("\n\n\t\tAFTER PARTIAL CROSSOVER WITH MAXIMUM DISTANCE.");

	
	getch();
	clrscr();
	initialize(pathlen,path);
	evaluate(pathlen,path,fx);
	getch();
	selection(fx,pos,posmax);
	crossover(pos,path,child);
	mutation(child);
	getch();
	insert(child,posmax,path);

	for(int i=1;i<N;i++)
	{
		evaluate(pathlen,path,fx);
		selection(fx,pos,posmax);
		crossover(pos,path,child);
		mutation(child);
		insert(child,posmax,path);

	}
	evaluate(pathlen,path,fx);
	selection(fx,pos,posmax);
	crossover(pos,path,child);
	insert(child,posmax,path);

	evaluate(pathlen,path,fx);
	getch();
}