#include "tipos.h"


void estadistica(double *media,double *stdv,double p)
{                             
	static long int num=0;
	static double suma1=0,suma2=0;
	
	num++;
	
	suma1 += p*p;
	suma2 += p; 
	
	if(num>4)
	{
		*media = suma2/num;
		*stdv  = sqrt(((num*suma1)-(suma2*suma2))/(num*(num-1)));
	}
}	



int primer_color_legal(int i,int start)
{
/* Devuelve el primer color legal para i comenzado
   desde el color start y terminando en num_color.
   Devuelve un -1 si no lo encuentra */
   
    int no_legal,color,j;

	color=start;
	while(color<=num_color)
	{
		no_legal=0;				   
   		for(j=1;j<=uno[i]->adya[0];j++)
			if(uno[uno[i]->adya[j]]->color==color)
				no_legal++; 
		if(no_legal==0) return color;
		color++;
	}
	return -1;
}
	

int comprueba_color(int num_colores)
{ 
/* Devuelve un 1 si la coloracion es legal */

	int i,j;
	
	for(i=1;i<=n;i++)
	{
		if(uno[i]->color<=0 ||
		   uno[i]->color>num_colores)
		   		return -1;
		for(j=1;j<=uno[i]->adya[0];j++)
			if(uno[i]->color==uno[uno[i]->adya[j]]->color)
				return -1;
	}
	return 1;
}


int random_vert_ilegal()
{   
/* Si en n/2 pruebas al azar no pilla uno ilegal,
   toma el primero que encuentra a partir del i */
   
	int i,j,find;
	
	find=0;
	while(find++ <= n/2)
	{
		i=getrandom(1,n);
		for(j=1;j<=uno[i]->adya[0];j++)
		{
			if(uno[ uno[i]->adya[j]]->color==
			   uno[i]->color)
			   		return i;
		}
	}         
	i=getrandom(1,n);
	find=0;
	while(find++<=n)
	{  
	 	for(j=1;j<=uno[i]->adya[0];j++)
		{
			if(uno[ uno[i]->adya[j]]->color==
			   uno[i]->color)
			   		return i;
		} 
		i++;
		if(i>n) i=1;
	}
	return -1;
} 

int estrella()
{           
/* Un vertice estrella es adyacente a dos o mas
   con su mismo color. Esta funcion devuelve el 
   primer estrella encontrado o un -1 si no hay 
   ninguno.*/
   
	int i,j,no_legales;
	
	i=1;
	while(i<=n)
	{
		no_legales=0;
		for(j=1;j<=uno[i]->adya[0];j++)
		{
			if(uno[ uno[i]->adya[j]]->color==
			   uno[i]->color)
			   no_legales++;
		}
		if(no_legales>1)
			return i;
		i++;
	}               
	return -1;
}
	
	




int random_grasp_vert(int iter)
{
/* Devuelve un vertice al azar de entre la lista
   reducida de admisibles */
   
   int i,total,grado,j;          
   int *lista,*lgrado;
   int peor_j,peor_grado;
   
   lista = reserva_vector(csize);
   lgrado = reserva_vector(csize);
   i=1;
   total=0;
   
   /* Iniciar la lista */
   while(i<=n && total<csize)
   {    
   		if(uno[i]->color==0)
   		{
   			total++;
   			lista[total]=i;
   			grado=0;
   			for(j=1;j<=uno[i]->adya[0];j++)
   			{
		   		if((iter==0 && uno[ uno[i]->adya[j] ]->color==0)
   				   	   || uno[ uno[i]->adya[j] ]->color==-1) 
   					           grado++;
   			}
   			lgrado[total]=grado;
   		} 
   		i++;
   	}
   	if(total<csize)
   	{
   		j=getrandom(1,total); 
   		i=lista[j];
   		free(lista);free(lgrado);
   		return i;
   	} 
   	
   	/* Completar la lista */
    while(i<=n)
    {    
   		if(uno[i]->color==0)
   		{
   			grado=0;
   			for(j=1;j<=uno[i]->adya[0];j++)
   			{
		   		if((iter==0 && uno[ uno[i]->adya[j] ]->color==0)
   				   	   || uno[ uno[i]->adya[j] ]->color==-1) 
   					           grado++;
   			}
   			
   			/* Si supera al peor lo reemplaza */
   			peor_j=0;
   			peor_grado=1000;
   			for(j=1; j<=csize ;j++)
   			{
   				if(lgrado[j]<peor_grado)
   				{
   					peor_grado=lgrado[j];
   					peor_j=j;
   				}
   			}
			if(grado>peor_grado)
			{               
				lista[peor_j]=i;
			 	lgrado[peor_j]=grado;
			}
   		} 
   		i++;
   	}
   	j=getrandom(1,csize); 
   	i=lista[j];
   	free(lista);free(lgrado);
   	return i;
}
   
   
   
   
   
   
int random_no_color_admis(int admis)
{
/* Devuelve un vertice al azar entre los no coloreados admisibles.*/
   
   int i,j,index;
   
   i = getrandom(1,admis);
   
   j=index=1;
   while(uno[index]->color !=0)
   		index++;
   
   while(j<i)
   {    
   		index++;
   		if(uno[index]->color==0) j++;		
   }
   return index;
}	
   

int grado_maximo_no_coloreado(int iter)
{
/* Calcula el vertice de grado maximo en el subgrafo
   inducido por los vertices no coloreados si iter=1.
   Para iter>1 calcula el grado inadmisible */
   
   int i,j,grado,imax,max;
   
   imax=max=-1;
   
   for(i=1;i<=n;i++)
   {
   		if(uno[i]->color==0) 
   		{
   		    /* Calcula el grado del i */
   			grado=0;
   			for(j=1;j<=uno[i]->adya[0];j++)
   				if(  (iter==1 && uno[ uno[i]->adya[j] ]->color==0)
   				   || uno[ uno[i]->adya[j] ]->color==-1) 
   					grado++;
   					
   			if(grado>max) {
   				max=grado;
   				imax=i;
   			}
   		}	
   	}
   	return imax;
}	

int no_adyacentes(int a,int b)
{
/* Devuelve un 0 si son adyacentes, 1 si lo son */

	int i;
	
	for(i=1 ; i<= uno[a]->adya[0] ; i++)
	{
		if(uno[a]->adya[i] == b)
			return 0;
	}
	return 1;
} 


void abortar(char *texto)
{
	printf("%s",texto);
	exit(5);
}

void imprime_color()
{   
	int i,j,cont;

	for(i=1;i<=num_color;i++)
	{
		printf("\ncolor %2d = ",i);
		j=0;cont=1;
		while(cont<=c[i][0])
		{
			j++;
			if(c[i][j]!=0)
			{
				printf(" %d",c[i][j]);
				cont++;
			}
		}
	}
}

void imprime_grafo()
{
	int i,j;
	
	for(i=1;i<=n;i++)
	{
		printf("\n Vértice %2d = ",i);
		for(j=1;j<=uno[i]->adya[0];j++)
			printf(" %d",uno[i]->adya[j]);
    }
}