/*********************** ONEHALFAROUNDMST.CPP *********************************
* TSP Algorithms : OneHalfAroundMST                                24.12.2008 *
*                                                                             *
* - Find a minimum-weight spanning tree T of G;                               *
* - Conduct a DFS of T: associate a DFS index L(v) with each vertex;          *
* - Output the following cycle:                                               *
*   C = vi1,vi2,…,vin,vi1 where L(vij) = j                                    *
*                                                             Beycan Kahraman *
******************************************************************************/

#include "OneHalfAroundMST.h"

#define SHOW_MST false
#define SHOW_MATCHING false
#define SHOW_EULER false

OneHalfAroundMST::OneHalfAroundMST(short dist[][SZ], int n) : AlgorithmTSP(dist, n)
{
	mst_cost = 0;
	count = 0;
	node_order = new int[2*SZ];
	match_n_used = new bool[2*SZ];
	for(int i=0; i<SZ; ++i){
		node_order[i] = 0;
		match_n_used[i] = true;
	}
	Run();
}

bool pred2(const std::pair<int,int>& lhs, const std::pair<int,int>& rhs)
{  
	return (lhs.second < rhs.second);  
}

void OneHalfAroundMST::KruskalLikeMST()
{
	count = 0;

	for(int i=0; i<n; ++i)
		for(int j=i+1; j<n; ++j)
			edges.push_back(edge(i*n + j,dist[i][j]));

	sort(edges.begin(), edges.end(), pred2);

	for(int i=0; i<n; ++i)
		best_cycle[i] = -i-1;
	min_cycle = 0;

	while(min_cycle < n-1)
	{
		edge shortest = edges[count++];
		int dist_first = shortest.first / n;
		int dist_second = shortest.first % n;

		if(best_cycle[dist_first] < 0 && best_cycle[dist_second] < 0)
		{
			best_cycle[dist_first] = min_cycle;
			++node_order[dist_first];
			best_cycle[dist_second] = min_cycle;
			++node_order[dist_second];
			sequence[min_cycle++] = shortest.first;
			mst_cost += shortest.second;
		}
		else if(best_cycle[dist_first] < 0)
		{
			best_cycle[dist_first] = best_cycle[dist_second];
			++node_order[dist_first];
			++node_order[dist_second];
			sequence[min_cycle++] = shortest.first;
			mst_cost += shortest.second;
		}
		else if(best_cycle[dist_second] < 0)
		{
			best_cycle[dist_second] = best_cycle[dist_first];
			sequence[min_cycle++] = shortest.first;
			mst_cost += shortest.second;
			++node_order[dist_first];
			++node_order[dist_second];
		}
		else if(best_cycle[dist_first] != best_cycle[dist_second])
		{
			++node_order[dist_first];
			++node_order[dist_second];
			dist_first = best_cycle[dist_first];
			dist_second = best_cycle[dist_second];
			for(int i=0; i<n; ++i)
				if(best_cycle[i] == dist_second)
					best_cycle[i] = dist_first;
			sequence[min_cycle++] = shortest.first;
		}
	}
}

// sequence[] --> MST   /n  %n
// mst_cost   --> MST COST

void OneHalfAroundMST::FindMinMatching() // HEURISTIC
{
	bool *odd = new bool[n];
	int cnt = 0;

	for(int i=0; i<n; ++i)
		if(node_order[i] % 2 == 1){
			odd[i] = true;
			++cnt;
		}else
			odd[i] = false;

	for(unsigned i=0; i<edges.size(); ++i)
	{
		if(odd[edges[i].first/n] && odd[edges[i].first%n])
		{
			matches.push_back(edges[i]);
			odd[edges[i].first/n] = false;
			odd[edges[i].first%n] = false;
			if(SHOW_MATCHING)
				printf("(%d,%d) ", edges[i].first/n, edges[i].first%n);
			cnt -= 2;
			if(cnt == 0)
				break;
		}
	}
	if(SHOW_MATCHING)
		printf("\n\n");
/*
	for(unsigned i=0; i<matches.size(); ++i)
		for(unsigned j=i+1; j<matches.size(); ++j)
		{
			if( dist[matches[i].first/n][matches[j].first/n] + dist[matches[i].first%n][matches[j].first%n] <
				matches[i].second + matches[j].second )
			{
				cnt = matches[i].first;
				matches[i].first = cnt - matches[i].first%n + matches[j].first/n;
				matches[i].second = dist[matches[i].first/n][matches[i].first%n];

				matches[j].first = n*(matches[i].first%n) + matches[j].first%n;
				matches[j].second = dist[matches[j].first/n][matches[j].first%n];
			}
			else if( dist[matches[i].first/n][matches[j].first%n] + dist[matches[i].first%n][matches[j].first/n] <
				matches[i].second + matches[j].second )
			{
				cnt = matches[i].first;
				matches[i].first = cnt - matches[i].first%n + matches[j].first%n;
				matches[i].second = dist[matches[i].first/n][matches[i].first%n];

				matches[j].first = n*(cnt%n) + matches[j].first/n;
				matches[j].second = dist[matches[j].first/n][matches[j].first%n];
			}
		}
	if(SHOW_MATCHING)
		for(unsigned i=0; i<matches.size(); ++i)
			printf("(%d,%d) ", matches[i].first/n, matches[i].first%n);

	if(SHOW_MATCHING)
		printf("\n");*/

	for(int i=0; i<n-1; ++i)
		matches.push_back(edge(sequence[i], dist[sequence[i]/n][sequence[i]%n]));

	if(SHOW_MST)
	{
		for(int i=0; i<n-1; ++i)
			printf("(%d,%d) ", sequence[i]/n, sequence[i]%n);
		printf("\n");
	}
}

void OneHalfAroundMST::FindEulerHamilton(int nd, int k){
	if(k == matches.size()+1)
	{
		euler = false;
		for(int i=0; i<2*SZ; ++i)
			match_n_used[i] = true;
		return;
	}
	for(unsigned i=0; i<matches.size(); ++i)
		if(match_n_used[i])
		{
			if(matches[i].first/n == nd)
			{
				match_n_used[i] = false;
				FindEulerHamilton(matches[i].first%n, k+1);
				if(euler)
					match_n_used[i] = true;
				else
				{
					node_order[k] = matches[i].first%n;
					if(SHOW_EULER)
						printf("(%d,%d) ", nd, node_order[k]);
					min_cycle += dist[nd][matches[i].first%n];
					return;
				}
			}
			else if(matches[i].first%n == nd)
			{
				match_n_used[i] = false;
				FindEulerHamilton(matches[i].first/n, k+1);
				if(euler)
					match_n_used[i] = true;
				else
				{
					node_order[k] = matches[i].first/n;
					if(SHOW_EULER)
						printf("(%d,%d) ", nd, node_order[k]);
					min_cycle += dist[nd][matches[i].first/n];
					return;
				}
			}
		}
}

void OneHalfAroundMST::CalculateTSP()
{
	KruskalLikeMST();

	euler = true;
	node_order[0] = 0;
	min_cycle = 0;

	FindMinMatching();

	FindEulerHamilton(0, 1);
	if(SHOW_EULER)
		printf("\n");
}

void OneHalfAroundMST::Run()
{
	__int64 freq, start, end, diff;

	QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
	QueryPerformanceCounter((LARGE_INTEGER*)&start);

	//duration = clock();

	/*	Twice Around MST Algorithm runs here ...	*/

	CalculateTSP();

	//duration = clock() - duration;

	QueryPerformanceCounter((LARGE_INTEGER*)&end);
	diff = ((end - start) * 1000000) / freq;

	duration = (unsigned int)(diff & 0xffffffff);
}

OneHalfAroundMST::~OneHalfAroundMST(void)
{
}
