#include "tipos.h"

int rlf()
{
	register i;
	int v,j,color_actual=0;
	
	for(i=1;i<=n;i++)
		uno[i]->color=0;                 
	
	while( (v=grado_maximo_no_coloreado(1)) != -1)
	{	
		/*  Colorear el de grado maximo y etiquetar
	   		sus adyacentes no coloreados como inadmisibles */
	   
		uno[v]->color = ++color_actual;
	
		for(i=1;i<=uno[v]->adya[0];i++)
		{
			j = uno[v]->adya[i];
			if(uno[j]->color == 0) uno[j]->color = -1;
		}

    	while( (v=grado_maximo_no_coloreado(2)) != -1)
    	{
			uno[v]->color =color_actual;
	
			for(i=1;i<=uno[v]->adya[0];i++) 
			{
				j = uno[v]->adya[i];
				if(uno[j]->color == 0) uno[j]->color = -1;
			}
    	}
    	
    	for(i=1;i<=n;i++)
			if(uno[i]->color==-1) uno[i]->color=0;
	}                               
	
    return color_actual;	
} 

int xrlf(int TrialNum,int CandNum)
{
	register i;
	int v,j,color_actual=0;
	int best_v,best_valor,best_grado;
	int a,aa,u,grado,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<=TrialNum ; a++)
		{   
			admis = n - col;
			while(admis>0)
		    {   
		    	/* Se toma el de grado mayor de entre
		    	   CandNum al azar */
		    
				best_v=-1;best_grado=-1;	                                  
	        	for(aa=1;aa<=CandNum;aa++)
	        	{
					v=random_no_color_admis(admis);
					grado=0;
   					for(j=1;j<=uno[v]->adya[0];j++)
   					if((candi[0]==0 && uno[ uno[v]->adya[j] ]->color==0)
   				   	   || uno[ uno[v]->adya[j] ]->color==-1) 
   					           grado++;
   					
   					if(grado>best_grado) {
   						best_grado=grado;
   						best_v=v;
   					}
   				}
   				
   				if(best_v==-1) abortar("Problemas en xrlf 1");
					
				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];
	}  
	    
    return color_actual;	
}