/*****************************
 * Practica 9 MP
 * Curso 2008-2009
 *
 * Vicente Lujan Mansilla
 * Lorena Margareto Bisquert
 *****************************/
#include <stdlib.h>
#include <iostream>
#include <fstream>
#include <time.h>
#include <vector>
#include <math.h>
#include <assert.h>
#include <vector>

#include "Graph.h"

void f_aux(Graph &g, int nodoIni, int nodoUlt, int &tMedio);
void f_auxNP(Graph &g, int nodoIni, int nodoUlt, int &tMedio);
void backTracking(int i, Graph &g, int nodoIni, int nodoUlt, float tiempo, float &mejorTiempo, vector<int> &camino, vector<int> &solucion);
void backTrackingNP(int i, Graph &g, int nodoIni, int nodoUlt, float tiempo, float &mejorTiempo, vector<int> &camino, vector<int> &solucion);
void evaluar(int ini, int fin, int inc, int min, int max, ostream &fAcc, ostream &fBack, ostream &fVoraz);	
void evaluarNP(int ini, int fin, int inc, int min, int max, ostream &fBackNP);	
vector<int> concierto(Graph & g, int nodo, float &tiempoTotal);

using namespace std;

const float INFINITO = 9e9;

int main()
{	
	srand(time(NULL));
		
	ofstream f1, f2, f3, f4;
	
	f1.open("bt.dat");
	f2.open("sol_bt.dat");
	f3.open("sol_voraz.dat");
	f4.open("bt_nopoda.dat");
	
	evaluar(5, 14,1, 1, 76, f1, f2, f3);
	evaluarNP(5, 14, 1, 1, 76, f4);
	
	f1.close();
	f2.close();
	f3.close();
	f4.close();
	
	return 0;
}

void f_aux(Graph &g, int nodoIni, int nodoUlt, int &tMedio)
{
	vector<int>camino(g.size()+1);				
	vector<int>solucion(g.size()+1);		
	float mejorTiempo = INFINITO;

	solucion[0] = 0;		
	g(0,0) = 1;		
	
	backTracking(1, g, nodoIni, nodoUlt, 0, mejorTiempo, camino, solucion);
	
	tMedio = mejorTiempo;
}

void f_auxNP(Graph &g, int nodoIni, int nodoUlt, int &tMedio)
{
	vector<int>camino(g.size()+1);				
	vector<int>solucion(g.size()+1);			
	float mejorTiempo = INFINITO;

	solucion[0] = 0;		
	g(0,0) = 1;		
	
	backTrackingNP(1, g, nodoIni, nodoUlt, 0, mejorTiempo, camino, solucion);
	
	tMedio = mejorTiempo;
}


void backTracking(int i, Graph &g, int nodoIni, int nodoUlt, float tiempo, float &mejorTiempo, vector<int> &camino, vector<int> &solucion)
{
	if(i==g.size())
	{
		if((tiempo + g(nodoUlt, nodoIni)) < mejorTiempo)
		{
			camino[camino.size()-1] = nodoIni;
			solucion = camino;
			mejorTiempo = tiempo + g(nodoUlt, nodoIni);
		}
	}
	else
	{
		for(int j=0; j<g.size(); j++)
		{
			if((g(j, j) ==0) && ((tiempo + g(nodoUlt, j)) < mejorTiempo))
			{
				g(j, j) = 1;
				camino[i] = j;
				backTracking(i+1, g, nodoIni, j, (tiempo + g(nodoUlt,j)), mejorTiempo, camino, solucion);
				g(j, j) = 0;
			}
		}
	}
}

void backTrackingNP(int i, Graph &g, int nodoIni, int nodoUlt, float tiempo, float &mejorTiempo, vector<int> &camino, vector<int> &solucion)
{
	if(i==g.size())
	{
		if((tiempo + g(nodoUlt, nodoIni)) < mejorTiempo)
		{
			camino[camino.size() - 1] = nodoIni;
			solucion = camino;
			mejorTiempo = tiempo + g(nodoUlt, nodoIni);
		}
	}
	else
	{
		for(int j=0; j<g.size(); j++)
		{
			if((g(j, j) ==0))
			{
				g(j, j) = 1;
				camino[i] = j;
				backTrackingNP(i+1, g, nodoIni, j, (tiempo + g(nodoUlt,j)), mejorTiempo, camino, solucion);
				g(j, j) = 0;
			}
		}
	}
}

vector<int> concierto(Graph & g, int nodo, float &tiempoTotal)
{
	vector<int> ruta(g.size()+1);						
	vector<bool> T(g.size());				
	int ultimo, nmin;																
	float min;
	
	for(int i=0; i<T.size(); i++)
		T[i] = false;
	
	ruta[0] = nodo;
	ultimo = nodo;
	
	T[nodo-1] = true;

	for(int i=1; i<g.size(); i++)
	{
		min = INFINITO;								
			
		for(int j=1; j<g.size(); j++) 
		{
			if((g(ultimo, j) < min) && (ultimo != j) && (T[j-1] == false))
			{
				min = g(ultimo, j);
				nmin = j;
			}
		}
		tiempoTotal += min;
		
		ruta[i] = nmin;
		ultimo = nmin;	
		T[nmin-1] = true;
	}
	ruta[g.size()] = nodo;
	tiempoTotal += g(ultimo, nodo);
	
	return ruta;
}

void evaluar(int ini, int fin, int inc, int min, int max, ostream &fAcc, ostream &fBack, ostream &fVoraz)
{
	int rep = 20;
	int nodoUlt = 0, nodoIni = 0;
	int tMedio;
	float tVor = 0;
	
	int auxAcc;				
	int auxBack;	
	int auxVor;		

	vector<int> ruta;

    for(int talla=ini; talla<fin; talla+=inc)																		
    {
		Graph g(talla);
	  	g.initAccesos();
			
		auxAcc = 0;
		auxBack = 0;
		auxVor = 0;			
		tMedio = 0;
			
		for(int i=0; i<rep; i++)
		{
			tVor = 0;
			g.grafoAleatND(min, max);											
			g.initAccesos();
				
			f_aux(g, nodoIni, nodoUlt, tMedio);
			auxAcc += g.getAccesos();	
			auxBack += tMedio;
			ruta = concierto(g, nodoIni, tVor);				
			auxVor += tVor;
		}
		fAcc << talla << " " << auxAcc/rep << endl; 
		fBack << talla << " " << auxBack/rep << endl; 
		fVoraz << talla << " " << auxVor/rep << endl;
	}
}

void evaluarNP(int ini, int fin, int inc, int min, int max, ostream &fBackNP)
{
	int rep = 20;
	int nodoUlt = 0, nodoIni = 0;
	int tMedio;
    			
	int auxAcc;				
	
	for(int talla=ini; talla<fin; talla+=inc)																		
	{
		Graph g(talla);
	      	g.initAccesos();
	      	auxAcc = 0;
			
	      	for(int i=0; i<rep; i++)
	      	{
         		g.grafoAleatND(min, max);												
			g.initAccesos();
				
			f_auxNP(g, nodoIni, nodoUlt, tMedio);
			auxAcc += g.getAccesos();					
				 
		}
		fBackNP << talla << " " << auxAcc/rep << endl; 	
	}
}



