#include "tipos.h"

int grasp(int ngiters,int tipo)
{ 
/* El tipo de mejora indica: 1 xgreedy, 2 tabucol, 3 simulated annealing */
                   
	int i,ii=0;
	int cc,cm,mejoras=0,best_color=10000;
	double p,media,stdv; 
	time_t g1,g2;
	
	for(i=1;i<=ngiters;i++)
	{	
		
		//g1 = clock();
		cc = construir(); 
		
		/*g2 = clock();
        printf("\nconstrucción  = %4.2f",((float)g2 - g1)/CLK_TCK);
         */
         
		if(cc < best_color)
			best_color=cc;
        
        /*p = 1 - ((double) best_color / (double) cc);
 		if(i>5 && stdv>0 && (p-media)/stdv > 3 )
 		{
 			ii++;
	 		continue;
	 	}*/
        
        //g1 = clock();
		cm = mejora(cc,tipo);
	
		if(cm != -1 )
		{   
			while(cm!=-1)
			{
				if( cm!=-1 && cm < best_color)
					best_color=cm;
				cm=mejora(cm,tipo);    
			}	
			mejoras++;
		}	
		else cm=cc;
		
		/*g2 = clock();
        printf("   mejora  = %4.2f",((float)g2 - g1)/CLK_TCK);
       */ 	
		/*p=((double)cc-(double)cm)/(double)cc;
    	estadistica(&media,&stdv,p);
		printf("\n %d %d",cc,cm);	*/
	} 
	
/*if(comprueba_color(cc)!=1) abortar("Error grasp");  
    printf("\nmejoras=%d  saltados = %d",mejoras,ii); */
	return best_color;
}                       


int mejora(int ncolor,int tipo)
{
	int a,b,i,*colores;
	int legal,min,menor,antemenor;
	
	colores=reserva_vector(ncolor);
	
	for(i=1;i<=n;i++)	
		colores[uno[i]->color]++;
		
	min=10000;
	for(i=1;i<=ncolor;i++)
	{
		if(colores[i]<min)
		{
			min=colores[i];
			menor=i;
		}
	}
	
	min=10000;	
	for(i=1;i<=ncolor;i++)
	{
		if(i!=menor && colores[i]<min)
		{
			min=colores[i];
			antemenor=i;
		}
	}
	free(colores);
	
	/* Junta las dos clases en una (la de indice menor) y
	   corre las restantes (de la mayor a la ultima) una */
	
	a = __min(menor,antemenor);
	b = __max(menor,antemenor);
	
	for(i=1;i<=n;i++)                                
	{                          
		if(uno[i]->color==b) uno[i]->color=a;
		if(uno[i]->color>b)  (uno[i]->color)--;
	}
	
	ncolor--;
	num_color=ncolor;
	
	if(tipo==1)      legal = xgreedy((2*n)/noimpiter,num_color);
	else if(tipo==2) legal = tabucol(1000,n/4); 
	else			 legal = sa_2(15);
	
	if(legal==0) return ncolor;
	else		 return -1;
} 


int xgreedy(int max_iter,int rep)
{
/* Considera una solucion inicial dada con num_color colores.
   Realiza una busqueda greedy aleatorizada minimizando el numero 
   de aristas ilegales. Si el minimo es 0, ha encontrado una
   coloracion legal con esos colores.*/
   
   int *ilegales,f; 
   int new_color;
   int no_mejora,vert,i,find,f_change;
   
   ilegales=reserva_vector(num_color);
   
   f=ilegal(ilegales);
   no_mejora=0;	   
   while(f>0 && no_mejora<max_iter)
   { 	
   		vert = random_vert_ilegal();
   		
   		/* Realizamos rep pruebas */
   		i=1;
   		find=0;
   		while(i++<=rep && find==0)
   		{                           
        	new_color = getrandom(1,num_color);
			if(new_color == uno[vert]->color) continue;
			f_change=c_ileg(vert,new_color);
		    if(f_change<0)
		    {
	            find=1; 
	            no_mejora=0;
				f += f_change;
		    	actualiza_clases(ilegales,vert,new_color);
			    if(f != ilegales[0]) abortar("grasp xgreedy");
			}   
		}
		if(find==0)		no_mejora++;
	} 
	free(ilegales);
	return f;
}
	
	
	


int construir()
{
	register i;
	int v,j,color_actual=0;
	int best_v,best_valor;
	int a,u,valor;
	int *candi,*best_candi;
	int col;      /* Num de vertices coloreados */
	int admis;    /* Num de vertices no coloreados admisibles */
	 
	 
	candi      = reserva_vector(n);
	best_candi = reserva_vector(n);   
	col=0; 
	for(i=1;i<=n;i++)  uno[i]->color=0;                 
	
	while( col < n)
	{
		++color_actual; 
		best_valor=-1;
		
		/* Para cada color se hacen TrialNum pruebas*/
		for(a=1 ; a<=citer ; a++)
		{   
			admis = n - col;
			while(admis>0)
		    {   
		    	/* Se toma el de grado mayor de entre
		    	   CandNum al azar */   
		    	   
		        best_v=random_grasp_vert(candi[0]);
				uno[best_v]->color=color_actual;
	        	admis--;                       
	        	candi[++candi[0]]=best_v;
	        	for(i=1;i<=uno[best_v]->adya[0];i++)
				{
					j = uno[best_v]->adya[i];
					if(uno[j]->color == 0)
					{
						admis--;
						uno[j]->color = -1;
					}
				}
			}
	        
	        /* Se calcula la bondad de esta prueba */
	        
	        valor=0;
	        for(i=1 ;i<=candi[0];i++)
	        {   
	        	u = candi[i];
	        	for(j=1;j<= uno[u]->adya[0];j++)
	        	{
	        		v = uno[u]->adya[j];
	        		if(uno[v]->color==-1)
	        			valor++;
	        	}
	        }
	        if(valor>best_valor)
	        {
	        	best_valor = valor;
	        	for(i=0;i<=candi[0];i++) best_candi[i]=candi[i];
	        }                          
			candi[0]=0;
	        for(i=1;i<=n;i++)           
	        {
	        	if(uno[i]->color==color_actual ||
	        	   uno[i]->color==-1)
	        	{
	        			admis++;   
	        	   		uno[i]->color=0;	
	        	}
	        }
	    }
	    
	    for(i=1;i<=best_candi[0];i++)
	    	uno[best_candi[i]]->color=color_actual;
	    col += best_candi[0];
	}  
	
	free(candi);free(best_candi);    
    return color_actual;	
}