/*********************** TWICEAROUNDMST.CPP ***********************************
* TSP Algorithms : TwiceAroundMST                                  21.11.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 "TwiceAroundMST.h"

TwiceAroundMST::TwiceAroundMST(short dist[][SZ], int n) : AlgorithmTSP(dist, n)
{
	mst_cost = 0;
	count = 0;
	Run();
}

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

/* 
// NOTE: Beycan Kahraman [22.11.2008]
//
// The problem with Kruskal Algorithm is that, we should search for
// all n.(n-1)/2 edges to find the minimum cost edge for each n step. 
// Therefore, we should process at least n.n.(n-1)/2 steps to find 
// the minimum spanning tree, assuming that no cycles are created.
// If there are any, we should searh all edges again.
//
// However, modifying the algorithm by sorting these n.(n-1)/2 edges
// in LOG[n.(n-1)/2].n.(n-1)/2 steps could relax the performance.
*/

void TwiceAroundMST::KruskalLikeMST()
{
	typedef std::pair<int,int> edge;
	typedef std::vector<edge> vector_edges;
	vector_edges edges;
	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(), pred);

	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;
			best_cycle[dist_second] = min_cycle;
			sequence[min_cycle++] = shortest.first;
			mst_cost += shortest.second;
		}
		else if(best_cycle[dist_first] < 0)
		{
			best_cycle[dist_first] = best_cycle[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;
		}
		else if(best_cycle[dist_first] != best_cycle[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;
		}
	}
}

void TwiceAroundMST::RecursiveDeepFirstSearch() // BEFORE : count = 0;
{
	int myCount = count;
	if(count == n)
		return;
	for(int i=0; i<n-1; ++i)
		if(sequence[i] > 0)
		{
			if(sequence[i]/n == best_cycle[myCount])
			{
				best_cycle[count+1] = sequence[i]%n;
				min_cycle += dist[best_cycle[count]][best_cycle[count+1]];
				sequence[i] = -1;
				++count;
				RecursiveDeepFirstSearch();
			}
			else if(sequence[i]%n == best_cycle[myCount])
			{
				best_cycle[count+1] = sequence[i]/n;
				min_cycle += dist[best_cycle[count]][best_cycle[count+1]];
				sequence[i] = -1;
				++count;
				RecursiveDeepFirstSearch();
			}
		}
}

void TwiceAroundMST::DeepFirstSearch()
{
	min_cycle = 0;
	best_cycle[0] = 0;
	count = 0;

	RecursiveDeepFirstSearch();

	min_cycle += dist[best_cycle[0]][best_cycle[n-1]];
}

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

	QueryPerformanceFrequency((LARGE_INTEGER*)&freq);
	QueryPerformanceCounter((LARGE_INTEGER*)&start);
	
	//duration = clock();

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

	KruskalLikeMST();

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

	DeepFirstSearch();

	//duration = clock() - duration;

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

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

TwiceAroundMST::~TwiceAroundMST(void)
{
}
