#include "Tsp.h"

namespace cosi {

namespace algorithms {

namespace graph {

Tsp::Tsp(cosi::commstruct::graph::U_RealWeightedGraph* pN) {
	mN = pN ;
	//check that the graph is complete
	if (mN->Size() != mN->Order() * (mN->Order() - 1)) {
		//std::cout << "WARNING : The graph is not a complete graph"<< std::endl ;
	}
}

Tsp::~Tsp() {
}

void Tsp::Run() {
	cosi::commstruct::graph::U_RealWeightedGraph* M;
	MinimumSpanningTree* Mst = new MinimumSpanningTree(mN);
	IdUndirectedGraph::v_iterator V;
	V = mN->v_begin() ;
	Mst->Run(*V) ;
	M = Mst->Get() ;

	//Find the Euler tour
	mTour.clear() ;
	mTour.push_back(*V) ;
	DfsInit(M) ;
	DfsVisit(*V) ;
	delete mMd ;
	delete M ;
}

std::list<int> Tsp::Get() {
	return mTour ;
}

void Tsp::DfsVisit(int Root) {
	mColor[Root] = GRAY ;
	IdUndirectedGraph::list_iterator Adj ;
	for( Adj = mMd->adj_begin(Root) ; Adj != mMd->adj_end(Root) ; Adj++ ) {
		if ( mColor[*Adj] == WHITE ) {
			mTour.push_back(*Adj) ;
			DfsVisit(*Adj) ;
		}
	}
	mColor[Root] = BLACK ;
}

void Tsp::DfsInit(cosi::commstruct::graph::U_RealWeightedGraph* pM) {
	//double all edges in the graph
	mMd = new cosi::commstruct::graph::U_RealWeightedGraph;
	IdUndirectedGraph::v_iterator U, V;
	for (U = pM->v_begin() ; U != pM->v_end() ; U++) {
		for (V = pM->v_begin() ; V != pM->v_end() ; V++) {
			if ( !mMd->InV(*U)) {
				mMd->AddVertex(*U) ;
				mColor[*U] = WHITE ;
			}
			if ( !mMd->InV(*V)) {
				mMd->AddVertex(*V) ;
				mColor[*V] = WHITE ;
			}
			if (pM->InE(*U, *V) && !mMd->InE(*U, *V)) {
				mMd->AddEdge(*U, *V) ;
				mMd->AddEdge(*U, *V) ;
			}
		}
	}
}

}

}

}
