color_kit.c

C语言开发的微粒群优化算法源程序

	
// First non assigned node


//printf("\n color_0 ici1");
for (i=0;i<M.size;i++)
{
	if (color.x[i]>NA) continue;
			first=i;
			goto coloring;	
}

 // All nodes are already colored!!
c_diff=diff_color(color);
if (c_diff<=cmax) colort.adm=1; else colort.adm=0;
return colort;


coloring:

//printf("\n color_0 ici2, first %i",first);


i=0;

try_i:
//printf("\n i %i/ ",i);
if (color.x[i]>NA) // Already colored in initial coloring
{
	i=i+1;
	if (i>=M.size) goto success;
		goto try_i;
} 

c_max=(int) param.H.max[i];
for (c=old_c.val[i];c<=c_max;c++)
{
	colort.x[i]=(float)c;
	// Test is consistent
//printf("\n   c %i",c);
//printf(" %i",c);
		for (j=0;j<dplus.dplus[i].size;j++)
		{
			k=dplus.dplus[i].val[j]; // Neighbour
//printf("\n     k %i",k);
			if (k>=i) continue; // Not already colored
//printf("\n      i/c, k/colort.x[k], M: %i/%i <-> %i/%i   %i",i,c,k,colort.x[k], M.val[i][k]);		
			if (fabs(c-colort.x[k])<M.val[i][k]) // if color c is not admissible
			{
//printf(" => not OK");				
				goto next_c; // Not OK
			}	
		}
		
		// Test is not too many colors
		c_diff=diff_color(colort);
//printf("\n               c_diff %i",c_diff);
		if (c_diff<=cmax) goto OK;
//printf("   => not OK");
			

next_c:;	
}

goto previous_i;

	OK:	


	i=i+1;
	if (i==M.size) goto success;
		old_c.val[i-1]=c;
		goto try_i;


previous_i:

colort.x[i]=(float)NA;

c_min=(int) param.H.min[i];
old_c.val[i]=c_min;

minus_i:
i=i-1;

if (i<first) goto impossible;

if (color.x[i]>NA) goto minus_i;

	old_c.val[i]=old_c.val[i]+1;
	if (old_c.val[i]>c_max) goto previous_i;	
		goto try_i;

success:

colort.adm=1;
return colort;

impossible:

colort.adm=0;
//printf("\n Sorry, I can't. You should increase the number of colors to use. At least %i",cmax+1);

return colort;
}

// ----------------------------------------------------------------------------- COLOR_3
struct position color_3(struct matrix M,struct dplus dplus,struct position color,struct param param)
{
/*
Try to improve color, only by modifying non colored nodes 
Non colored node = highly negative value NA  (global variable)

		select the non colored node i which has the largest number of colored neighbours with different colors
			in case of a tie, select the one with the largest number of colored neighbours
				in case of a tie, select at random
		option 0: assign to i the consistent color with the most occurences		
		option 1: assign the smallest possible color
*/

int					all_checked;
int					best_color;
int					best_node;
int					c,c1,c2;
struct vector_int	candidate1,candidate2;
int					c_max;

int					c_min;

struct vector_int	checked; //[color] checked
struct position		colort;
struct color_list	hood_color={0};
int					i;
int					j;
int					k;
int					l;

int					inode;
int					largest;
int					largest2;

int					max_color;
int					most;

struct vector_int	n_color;
struct vector_int	not_color;

int					OK;
int					option;


int					rank_color;
struct vector_int	used_times[2]; // [color] [number of times it is used] 

//printf("\n color_3 \n");
//display_position(color);

option=0;

max_color=(int)param.H.min[0]; // Max color ever assigned;
colort=color;

if (option==0) // Initialize used_times
{
	used_times[0].size=0;
	for (i=0;i<color.size;i++)
	{
		c=(int)color.x[i];
		if (c<=NA) continue;
			if (used_times[0].size==0) goto new_color;
				for (j=0;j<	used_times[0].size;j++)
				{
					c1=used_times[0].val[j]; // Check color
					if (c1==c)
					{
						used_times[1].val[j]=used_times[1].val[j]+1;// Already used
						goto next_node;
					}
				}
			new_color:
			used_times[0].val[used_times[0].size]=c; // New color
			used_times[1].val[used_times[0].size]=1; // Count for the first time
			used_times[0].size=used_times[0].size+1; // One more color		
	next_node:;
	}
	if (used_times[0].size==0) // If no node is already colored, assign  a random color to a random node 
	{
		i=alea(0,color.size-1); // random node
		c_min= (int) param.H.min[0];
		c_max= (int)  param.H.max[0];
		c=alea(c_min,c_max);
		used_times[0].val[0]=c;
		used_times[1].val[0]=1;
		rank_color=0;
		used_times[0].size=1;
		colort.x[i]=(float)c;
		if (param.printlevel>1)
			printf("\nWARNING. color_3: complete recoloring");
	}
}


hood_color.size=dplus.dmax;

// Compute the two criteria for the first time
largest=0;

for (inode=0;inode<M.size;inode++) // For each possible node i ...
{
	 if (colort.x[inode]>NA) continue;
	
		
	not_color.val[inode]=0;// Number of non colored neighbours
	for (i=0;i<dplus.dplus[inode].size;i++)
	{
		j=dplus.dplus[inode].val[i]; // Neighbour
		if (colort.x[j]>NA) continue;
			not_color.val[inode]=not_color.val[inode]+1;
	}
	
	hood_color.size=0;
	for (i=0;i<dplus.dplus[inode].size;i++) // Check the colors used in the hood.
	{	
		j=dplus.dplus[inode].val[i];
		if (colort.x[j]<=NA) continue;
			c=(int) colort.x[j]; // Color of the neighbour
			for (k=0;k<hood_color.size;k++)
			{
				c1=hood_color.val[k];	
				if (c1==c) goto next_i; // Already counted
			}
			hood_color.val[hood_color.size]=c; // New color
			hood_color.size=hood_color.size+1;
	next_i:;
	}



	// Count how many _different_ colors in the neighbourhood
	n_color.val[inode]=hood_color.size;
	
	// Update the largest number of different colors in the hood		
	if (n_color.val[inode]>largest)
	{
		largest=n_color.val[inode];
	}
}


for (inode=0;inode<M.size;inode++)
{
	candidate1.size=0;
	largest2=0;

	for (i=0;i<M.size;i++) // First criterion
	{
		if (colort.x[i]>NA) continue; // Already colored
		if (n_color.val[i]<largest) continue;
			candidate1.val[candidate1.size]=i;
			candidate1.size=candidate1.size+1;
			if (not_color.val[i]>largest2) largest2=not_color.val[i];
	}

	if (candidate1.size==0) goto end;

	if (candidate1.size==1)
	{
		best_node=candidate1.val[0];
		goto assign_color;
	}

	candidate2.size=0;

	for (i=0;i<candidate1.size;i++)
	{
		j=candidate1.val[i];
		if (not_color.val[j]<largest2) continue;
			candidate2.val[candidate2.size]=j;
			candidate2.size=candidate2.size+1;
	}
/*
	if (candidate2.size==0)
	{
		best_node=candidate1.val[alea(0,candidate1.size-1)];
		goto assign_color;	
	}
*/

	
	best_node=candidate2.val[alea(0,candidate2.size-1)];

assign_color:

//printf("\ncolor_3. best node %i",best_node);

c_min=(int) param.H.min[best_node];
c_max=(int) param.H.max[best_node];


if (option==0)
{
	checked.size=0; // No color checked
		c=c_min;
}
else	
{
	all_checked=1;
	c=c_min-1;
}

next_color:

//printf("\n color_3. c %i",c);

if (all_checked>0)
{
	c=c+1;
	if (c>c_max) goto warning;
	goto check;
}

//if (option==0) // ... choose the most already used consistent color;
{
		most=-1;
		OK=0;
		for (i=0;i<used_times[0].size;i++) // For each already used color ...
		{
			c1=used_times[0].val[i]; //  (color already used)
			for (j=0;j<checked.size;j++) // ... check if already checked
			{
				c2=checked.val[j];
				if (c2!=c1) continue;
					 // Already checked
					goto next_choose;
			}

			if (used_times[1].val[i]<=most) continue; // Less used
				c=c1;
				most=used_times[1].val[i];
				OK=1;
				rank_color=i;
		next_choose:;
		}

		if (OK==0) // All already used colors have been checked
		{
			all_checked=1;
			goto next_color;
		}
}

check:

//printf("\n color_3.  best_color %i ",c);

if (option==0)
{
	checked.val[checked.size]=c;// Color c is (will be) checked
	checked.size=checked.size+1;
}
	{
	// ... look if it is consistent

	for (j=0;j<dplus.dplus[best_node].size;j++) // For each possible neighbour...
		{
		k=dplus.dplus[best_node].val[j]; 
		if (color.x[k]<=NA) goto OK;// ...not colored => obviously consistent
		if (fabs(c-colort.x[k])>=M.val[best_node][k]) goto OK; // ... consistent
			goto next_color;// not consistent	
		OK:;
						
		} // next neighbour
		goto assign;

	}
	
warning:
best_color=max_color;

//printf("\n WARNING. color_3. Can't find any consistent color for node %i. Set to %i",best_node,best_color);



assign:
// Assign the color

best_color=c;

colort.x[best_node]=(float)best_color;
//printf("   best color %i",best_color);

if (best_color>max_color) max_color=best_color;


//_____________________ 
// Modify the criteria (remember the matrix is symmetric)

		for (i=0;i<dplus.dplus[best_node].size;i++) // For each best_node's neighbour ...
		{
			j=dplus.dplus[best_node].val[i]; // (neighbour)
			if (colort.x[j]>NA) continue; //  already modified

			not_color.val[j]=not_color.val[j]-1; // decrease the number of non modified j's neighbours

			for (k=0;k<dplus.dplus[j].size;k++) 
			{
				l=dplus.dplus[j].val[k];
				if (colort.x[l]<=NA) continue;
				if (colort.x[l]==best_color && l!=best_node) goto next_i3; // Color best_color already used in the neighbour 
			}

			// best_color not already used in the neighbourhood of j

			n_color.val[j]=n_color.val[j]+1;
		next_i3:;
		}
//printf("\n ici 3");
		largest=0;
		for (i=0;i<M.size;i++)
		{
			if (colort.x[i]>NA) continue;
			if (n_color.val[i]>largest)
			{
				largest=n_color.val[i];
			}
		}
//printf("\n ici 4 rank_color %i",rank_color);
		if (option==0) // Update the number of times the color is used
		{
			used_times[0].val[rank_color]=used_times[0].val[rank_color]+1;
		}

//printf("\n ici 5");
}		

end:

return colort;
}


//================================================================== COLOR_6
struct position color_6(struct matrix M,struct dplus dplus,struct position color0,int trace)
{
/* Mechanical analogy (protein folding)
Try to find an acceptable coloring "near" to color0
while stop criterion not satisfied
	for each node compute the balance of the forces along its edges
	if >0 add 1 to its color
	if <0 add -1 to its color
end while
*/
float				c1,c2;
int					coin;
float				constr;
struct position 	colort;
float				d;
float				d1,d2;
float				delta[Max_DD];
float				diff;
int					dim;
float				E0,E1,E2,Emin;
float				f0,f1;
float				f1_min,f1_max;
int					i;
int					j;
float				lambda;
int					node;
float				step;
int					too_consist;
int					uncons,uncons_max;
float				z;


if (trace>1)
{
	printf("\n Color_6");
	display_position(color0);
}

dim=M.size;


step=(float) 1.0/(dplus.dmax+1);// Warning. If you write 1/(...) some compilers give step=0 !!
lambda=1; // deadening
f0=1; // coeff for force due to unsatisfied constraint
z=(float)dplus.dtot; // Warning. As dtot*dim may be > 2^31-1, convert into float

//z=dplus0.dmax;


z=z*dim;
f1_min=(float) 2.0/(z+2);// For too consistent pairs
f1_max=(float) 4.0/(z+4);
f1=alea_float(f1_min,f1_max);

Emin=(float) 0.99999999*f0*step; // Smaller than f0*step


// WARNING. Valid only if all constraints are equal to 1

	d=0;
	for (i=0;i<dim;i++)
		{
		d=d+dplus.dplus[i].size*(dplus.dplus[i].size-1)/2;
		}
	Emin=Emin+f1*d;

/*
One unsatisfied constraint must give more energy than
all constraints too satisfied 
*/


uncons_max=0;

colort=color0;

E2=energy_color(colort,M,dplus,f0,f1);
E1=E2;
E0=E1;
if (trace>2) printf("\n Energy %.2f",E2);

loop:

uncons=0;
for (node=0;node<dim;node++) delta[node]=0; // Initialize the balance


// Forces between adjacent nodes

too_consist=0;

for (node=0;node<dim;node++) // For each node ...
	{
	d1=0;
	d2=0;
	c1=colort.x[node];
	for (i=0;i<dplus.dplus[node].size;i++) // For each neighbour ...
		{
		j=dplus.dplus[node].val[i];
		if (j<=node) continue; // Symmetrical matrix
		constr=(float)M.val[node][j];

		
//if (constr<=0) continue; // No constraint

		c2=colort.x[j];
		
		diff=(float) fabs(c1-c2)-constr;  // ... check the consistency
//printf("\n (%i/%.2f) (%i/%.2f)",node,c1,j,c2);		
		if (diff==0) continue; // Perfect
/*		
		if (diff>0) // Consistent, but too much. The spring is dilated
		{
			if (c1>c2+constr) // c1 should decrease or c2 increase => (-1,0) or (0,1)
			{
				coin=alea(0,1);
				d1=coin-1;
				d2=coin;
			}
			if (c1+constr<c2)  //c1 should increase or c2 decrease => (1,0) or (0,-1)
			{
				coin=alea(0,1);
				d1=coin;
				d2=coin-1;
			}
//printf("\ntoo consistent. %i +%.2f,  %i +%.2f",node,d1,j,d2);
			too_consist=1;
			d1=f1*d1;
			d2=f1*d2;
		}
*/			
		if (diff<0) // Unconsistent. The spring is compressed
		{
			uncons=uncons+1;
	//printf("\n uncons %i",uncons);
			// abs(c1-c2) must increase. 
			
			if (c1==c2) // Either (0,-1) or (1,0) or (-1, 0) or (0,-1)
			{
				coin=alea(1,4);
				if (coin==1) {d1=0;d2=1;}
				if (coin==2) {d1=1;d2=0;}
				if (coin==3) {d1=-1;d2=0;}