/*****************************
 * Practica 7 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 <list>
#include <assert.h>
#include <vector>

#include "Graph.h"

using namespace std;

const int REP = 200;
const int INFINITO = 999;

vector<int> concierto(Graph &g, int nodo);
void costeTeorico(unsigned ini, unsigned fin, int inc, ostream &salida);

int main()
{	
	ofstream f1;

	f1.open("voraz.dat");
	costeTeorico(10, 100, 10, f1);
	f1.close();

	return 0;
}

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

	return ruta;
}

void costeTeorico(unsigned ini, unsigned fin, int inc, ostream &salida)
{	
	int acc;

	for(unsigned talla=ini; talla<=fin; talla+=inc) 
	{
		Graph g(talla);
		vector<int> ruta(talla);
		acc = 0;

		for(int i=1; i<=REP; i++)
   		{
			g.grafoAleatND(1, 5);
			g.accesos = 0;
			ruta = concierto(g, 2);
			acc += g.getAccesos();
		}

		salida << talla << " " << acc/REP << endl;

		cout << "/*RUTA " << talla << "*/" << endl;
		for(int i=1; i<=g.size(); i++)
			cout << ruta[i] << " ";
		cout << endl;
	}
}







