/********************************** RUN.CPP ***********************************
* TSP Algorithms : Run                                             21.11.2008 *
*                                                                             *
* Initialize the TSP algorithms and runs them, gets the results               *
* in order to save as a graph file.                                           *
*                                                             Beycan Kahraman *
******************************************************************************/

// EKLENEMEYECEK KADAR KARIŽIK: 
// http://www.adaptivebox.net/CILib/code/tspcodes_link.html

#pragma once

#include <iostream>
#include <vector>
#include <windows.h>
#include "algorithms/BruteForce.h"
#include "algorithms/NearestNeighbor.h"
#include "algorithms/SimpleApproach.h"
#include "algorithms/TwiceAroundMST.h"
#include "algorithms/OneHalfAroundMST.h"
#include "archieve/randomc.h"
#include "archieve/GraphMaker.h"
#include "archieve/Distances.h"

#define DIVIDE_BF_T 100000
#define DIVIDE_SA_T 1000
#define DIVIDE_NN_T 1
#define DIVIDE_TA_T 10
#define DIVIDE_HA_T 5000

using namespace std;

int main()
{
	AlgorithmTSP *algorithm_tsp;
	GraphMaker *graph_maker;
	CRandomMersenne random_mersenne(21112008);

	/*	Modifying triangles that do not hold the triangle equality  */
	for(int i=1; i<SZ; ++i)
		for(int j=i+1; j<SZ; ++j)
			for(int k=j+1; k<SZ; ++k)
				if(dist[i][j] + dist[j][k] <= dist[i][k])
				{
					dist[i][k] = dist[i][j] + dist[j][k] - random_mersenne.IRandom(1,dist[i][k]/10);
					dist[k][i] = dist[i][k];
				}
				else if(dist[i][k] + dist[j][k] <= dist[i][j])
				{
					dist[i][j] = dist[i][k] + dist[j][k] - random_mersenne.IRandom(1,dist[i][j]/10);
					dist[j][i] = dist[i][j];
				}
				else if(dist[i][j] + dist[i][k] <= dist[j][k])
				{
					dist[j][k] = dist[i][j] + dist[i][k] - random_mersenne.IRandom(1,dist[j][k]/10);
					dist[k][j] = dist[j][k];
				}

	cout << "Starting in ";
	for(int i=3; i>0; --i)
	{
		cout << i << " seconds...";
		Sleep(1000);
		cout << "\b\b\b\b\b\b\b\b\b\b\b\b";
	}

	cout << endl << endl;
	cout << "          --------------------------------------------------" << endl;
	cout << "          PERFORMANCE & OUTCOME COMPARISON of TSP ALGORITHMS" << endl;
	cout << "          --------------------------------------------------" << endl << endl;
	cout << "\t\t\t   NODES\t DURATION\t TOTAL COST" << endl << endl;

	vector<float> cost_brute_force;
	vector<float> cost_simple_approach;
	vector<float> cost_nearest_neighbor;
	vector<float> cost_twice_around_mst;
	vector<float> cost_one_half_around_mst;

	vector<float> duration_brute_force;
	vector<float> duration_simple_approach;
	vector<float> duration_nearest_neighbor;
	vector<float> duration_twice_around_mst;
	vector<float> duration_one_half_around_mst;

	/*	Simulating TSP Algorithms	*/
	for(int i=3; i<=SZ; ++i)
	{
		if(i < 13)
		{
			algorithm_tsp = new BruteForce(dist, i);
			cout << "Brute Force          >>    \t\t";
			cout << " t : " << algorithm_tsp->GetDuration() << char(230) << "s\t";
			cout << " c : " << algorithm_tsp->MinCycyle() << "km" << endl;
			cost_brute_force.push_back((float)algorithm_tsp->MinCycyle());
			duration_brute_force.push_back((float)algorithm_tsp->GetDuration() / DIVIDE_BF_T);
			delete algorithm_tsp;
		}
		
		algorithm_tsp = new SimpleApproach(dist, i);
		cout << "Simple Approach      >>    n : " << i << "\t";
		cout << " t : " << algorithm_tsp->GetDuration() << char(230) << "s\t";
		cout << " c : " << algorithm_tsp->MinCycyle() << "km" << endl;
		cost_simple_approach.push_back((float)algorithm_tsp->MinCycyle());
		duration_simple_approach.push_back((float)algorithm_tsp->GetDuration() / DIVIDE_SA_T);
		delete algorithm_tsp;

		algorithm_tsp = new NearestNeighbor(dist, i);
		cout << "Nearest Neighbor     >>    \t\t";
		cout << " t : " << algorithm_tsp->GetDuration() << char(230) << "s\t";
		cout << " c : " << algorithm_tsp->MinCycyle() << "km" << endl;
		cost_nearest_neighbor.push_back((float)algorithm_tsp->MinCycyle());
		duration_nearest_neighbor.push_back((float)algorithm_tsp->GetDuration() / DIVIDE_NN_T);
		delete algorithm_tsp;

		algorithm_tsp = new TwiceAroundMST(dist, i);
		cout << "Twice Around MST     >>    \t\t";
		cout << " t : " << algorithm_tsp->GetDuration() << char(230) << "s\t";
		cout << " c : " << algorithm_tsp->MinCycyle() << "km" << endl;
		cost_twice_around_mst.push_back((float)algorithm_tsp->MinCycyle());
		duration_twice_around_mst.push_back((float)algorithm_tsp->GetDuration() / DIVIDE_TA_T);
		delete algorithm_tsp;

		algorithm_tsp = new OneHalfAroundMST(dist, i);
		cout << "One Half Around MST  >>    \t\t";
		cout << " t : " << algorithm_tsp->GetDuration() << char(230) << "s\t";
		cout << " c : " << algorithm_tsp->MinCycyle() << "km" << endl;
		cost_one_half_around_mst.push_back((float)algorithm_tsp->MinCycyle());
		duration_one_half_around_mst.push_back((float)algorithm_tsp->GetDuration() / DIVIDE_HA_T);
		delete algorithm_tsp;

		cout << endl;
	}

	graph_maker = new GraphMaker("TSP Algorithms - Total Costs (81)", "Number of Nodes", "Total Costs");
	graph_maker->Add(cost_brute_force, "B.F.");
	graph_maker->Add(cost_simple_approach, "S.App");
	graph_maker->Add(cost_nearest_neighbor, "N.Neigh.");
	graph_maker->Add(cost_twice_around_mst, "2~MST");
	graph_maker->Add(cost_one_half_around_mst, "1.5~MST");
	graph_maker->Create("tsp_algorithms_costs.png");
	delete graph_maker;

	graph_maker = new GraphMaker("TSP Algorithms - Duration (81)", "Number of Nodes", "Duration");
	graph_maker->Add(duration_brute_force, "B.F./10^5");
	graph_maker->Add(duration_simple_approach, "S.App/10^3");
	graph_maker->Add(duration_nearest_neighbor, "N.Neigh.");
	graph_maker->Add(duration_twice_around_mst, "2~MST/10");
	graph_maker->Add(duration_one_half_around_mst, "1.5~MST/5000");
	graph_maker->Create("tsp_algorithms_duration.png");
	delete graph_maker;

	system("pause");
	system("tsp_algorithms_costs.png");
	return 0;
}