#include "tipos.h"

static long int iteraciones;

int simple_tabu()
{       
	int best_color,legal=0;
	
	best_color = num_color=2*cota_sup; 
	iteraciones=0;  
	
	do {
	    num_color--;
		color_inicial_aleat();
		legal =	tabucol(10000,n/2);
		if(legal==0)
		{ 
			if(comprueba_color(num_color)!=1)
				 abortar("Error tabu");
			best_color = num_color;
		} 
	}	
	while(legal==0);   
    
    /*printf("\nIteraciones tabu = %ld",iteraciones);*/
	return best_color;
}



int tabucol(int max_iter,int rep)
{
/* Considera una solucion inicial dada con num_color colores.
   Realiza una busqueda minimizando el numero de 
   aristas ilegales. Si el minimo es 0, ha encontrado una
   coloracion legal con esos colores.
   
   tabu_v[0] = ultima posicion escrita.*/
   
   int *tabu_v,*tabu_c,*ilegales,f; /* tabu_v[0]=num elementos */
   int new_color,best_try,best_try_f;
   int iter,vert,i,find,f_change;
   
   tabu_v=reserva_vector(7);
   tabu_c=reserva_vector(7);
   ilegales=reserva_vector(num_color);
   
   f=ilegal(ilegales);
   iter=0;	   
   while(f>0 && iter<max_iter)
   { 	
   		iter++;   
   		vert = random_vert_ilegal();
   		
   		/* Realizamos rep pruebas */
   		i=1;
   		best_try_f=1000;
   		find=0;
   		while(i<=rep && find==0)
   		{                           
   			i++;iteraciones++;
        	new_color = getrandom(1,num_color);
			if(new_color != uno[vert]->color)
			{      
				f_change=c_ileg(vert,new_color);
		        if(f_change<0)
		        {
		        	best_try   = new_color;
		        	best_try_f = f_change;	
		            find=1;
		        }
		        else if(f_change<best_try_f &&
		        	    es_tabu(tabu_v,tabu_c,vert,new_color)==0   )
		        {
		        	best_try   = new_color;
		        	best_try_f = f_change;	
		        }
		    }
		}  
		if(best_try_f !=1000)	
		{
			f += best_try_f;
			mete_tabu(tabu_v,tabu_c,vert,uno[vert]->color);		
		    actualiza_clases(ilegales,vert,best_try);
		    if(f != ilegales[0]) abortar("tabu");
		    
		} 
		
		/*if(f>0)	f=mejora_estrella(f);*/
	} 
	free(tabu_v);free(tabu_c);free(ilegales);
	return f;
}


int mejora_estrella(int f)
{
/* Si existe algun vertice estrella trata de encontrar una coloracion
   legal con esos colores realizando un maximo de 3 movimientos */
   
   int vert,col_vert,nuevo_color;
   int v2,v3,col_v2;
   int f1,f2,f3,j,no_legal;  
   
   
   vert=estrella();
   if(vert==-1) return f;
   
   col_vert=uno[vert]->color;
   nuevo_color=primer_color_legal(vert,1);  
   if(nuevo_color==-1) return f;
   f1=c_ileg(vert,nuevo_color);  
   uno[vert]->color=nuevo_color;
   if(f+f1==0) return 0;

   for(v2=1;v2<=n;v2++)
   {
   		if(v2==vert) continue;
   		
   		no_legal=0;
   		for(j=1;j<=uno[v2]->adya[0];j++)
		{
			if(uno[ uno[v2]->adya[j]]->color==
			   uno[v2]->color)
			   		no_legal++;
		}
        if(no_legal==0) continue;
        
        col_v2= uno[v2]->color;
        nuevo_color=primer_color_legal(v2,1);  
        if(nuevo_color==-1) continue;
        f2 = c_ileg(v2,nuevo_color); 
        uno[v2]->color=nuevo_color;
		if(f+f1+f2==0) return 0;
		        
        for(v3=v2+1;v3<=n;v3++)
   		{
   			if(v3==vert) continue;
   		
   			no_legal=0;
   			for(j=1;j<=uno[v3]->adya[0];j++)
			{
				if(uno[ uno[v3]->adya[j]]->color==
			   		uno[v3]->color)
			   		no_legal++;
			}
        	if(no_legal==0) continue;
        	
        	nuevo_color=primer_color_legal(v3,1);
        	if(nuevo_color==-1) continue; 
            f3 = c_ileg(v3,nuevo_color); 
            
            if(f+f1+f2+f3==0)
            { 
	        	uno[v3]->color=nuevo_color;
	        	return 0;
	        }    
	    }
	    uno[v2]->color=col_v2;
	}
	uno[vert]->color=col_vert;
	return f;
}
        
   
   
   
   
		    
		    
void mete_tabu(int *tabu_v,int *tabu_c,int vert,int c)
{
	tabu_v[0]++;
	if(tabu_v[0]==8) tabu_v[0]=1;
	
	tabu_v[ tabu_v[0] ]=vert;
	tabu_c[ tabu_v[0] ]=c;
}

int es_tabu(int *tabu_v,int *tabu_c,int vert,int c)
{
	int i;
	
	for(i=1;i<=7;i++)
	{
		if(tabu_v[i]==vert &&
		   tabu_c[i]==c)
		   		return 1;
	}
	return 0;
}   
		    
		
		
int c_ileg(int vert,int new_color)
{
	int j,new,old; 
	
	new=old=0;	
	for(j=1;j<=uno[vert]->adya[0];j++)
	{
		if(uno[ uno[vert]->adya[j]]->color==
			   uno[vert]->color)
			   		old++;
		if(uno[ uno[vert]->adya[j]]->color==
			   new_color)
			   		new++;
	}
	return new-old;
}
		     
   
int ilegal(int *ilegales)
{                    
	int i,j;
	
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=uno[i]->adya[0];j++)
		{
			if(uno[ uno[i]->adya[j]]->color==
			   uno[i]->color)
			   		ilegales[uno[i]->color]++;
		}	        
	}
	
	for(i=1;i<=num_color;i++)
	{
		ilegales[i] /= 2;
		ilegales[0] += ilegales[i];
	}
	return ilegales[0];
}



void actualiza_clases(int *ilegales,int vert,int new_color)
{
	int j;
	
	for(j=1;j<=uno[vert]->adya[0];j++)
	{
		if(uno[ uno[vert]->adya[j]]->color==uno[vert]->color)
		{
			   		ilegales[uno[vert]->color]--;
			   		ilegales[0]--;
		}
		if(uno[ uno[vert]->adya[j]]->color==new_color)
		{
			   		ilegales[new_color]++;
			   		ilegales[0]++;
		}
	}
	uno[vert]->color = new_color;
}