/*****************************
 * Practica 8 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 INFINITO = 999;

void crearEtse(Graph &g, float grado_conect);
void dijkstra(Graph &g, int nodo, vector<float> &pvecino, vector<int> &vecino);
void evaluar(int ini, int fin, int inc, int conec, int rep, ostream & salida);

int main()
{	
	ofstream f1, f2, f3, f4;

	f1.open("25dij.dat");
	evaluar(12, 124, 8, 25, 20, f1);
	f1.close();

	f2.open("50dij.dat");
	evaluar(12, 124, 8, 50, 20, f2);
	f2.close();

	f3.open("75dij.dat");
	evaluar(12, 124, 8, 75, 20, f3);
	f3.close();

	f4.open("100dij.dat");
	evaluar(12, 124, 8, 100, 20, f4);
	f4.close();

	return 0;
}

void crearEtse(Graph &g, float grado_conect)
{
     int Np = g.size()/4;
    
     /*Inicializacion de pesos a la constante INFINITO*/
     for(int i=0; i<g.size(); i++)
     {
             for(int j=0 ; j<g.size(); j++)
  		             g(i, j) = INFINITO;
     }

     for(int i=0; i<4; i++)
     	g.conectar(i, (i+1)*Np-1, grado_conect);
     
     
     for(int i=0; i<3; i++)
     	g(i*Np, (i+1)*Np) = 1 + rand()%g.size();

}

void dijkstra(Graph &g, int nodo, vector<float> &pvecino, vector<int> &vecino)
{
	vector<bool> B(g.size());
	float min;
	int m;

	for(int i = 0; i < g.size(); i++) //Diagonales inicializadas a 0
		g(i,i) = 0;
		
	for(int i=0; i<g.size(); i++)
	{
		B[i] = false;
		vecino[i] = nodo;
		pvecino[i] = g(nodo, i);
	}
	B[nodo] = true;

	for(int i=1; i<g.size(); i++)
	{
		min = INFINITO;
		
		for(int j=0; j<g.size(); j++) //Buscamos el arco minimo
		{
			if(B[j]==false && pvecino[j]>0 && pvecino[j]<min)
			{
				min = pvecino[j];
				m = j;
			}
		}
		B[m] = true;

		for(int j=0; j<g.size(); j++) //Actualizacion de los arcos
		{
			if(B[j]==false && (pvecino[m]+g(m,j))<pvecino[j])
			{
				pvecino[j] = pvecino[m] + g(m, j);
				vecino[j] = m;
			}
		}
	}
}

void evaluar(int ini, int fin, int inc, int conec, int rep, ostream &salida)
{
	int acc;
	
	for(unsigned talla=ini; talla<=fin; talla+=inc) 
	{
		Graph g(talla);
		vector<float> pvecino(talla);
		vector<int> vecino(talla);

		acc = 0;

		for(int i=1; i<=rep; i++)
   		{
			crearEtse(g, conec);
			g.initAccesos();
			dijkstra(g, 0, pvecino, vecino);
			acc += g.getAccesos();
		}
		salida << talla << " " << acc/rep << endl;

	}
}
