color_kit.c

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

/*
NOTE: NOT all these programs are simultaneously useful.
Some of them have more or less the same function.
They are here for test purpose
*/

// ----------------------------------------------------------------------------- ADMISSIBLE_COLOR
struct particle admissible_color(struct particle part,struct matrix M,int option,int cmax)
{
/*
For Coloring/Frequency assignment problem, try to adapt the position so that all constraints are respected, 
eventually by increasing the number of colors used

Note: edge list representation of the graph is a global variable (dplus)

*/

/*
For each  node successively (option=0)
or for each carefully chosen node (option >0)
	modify its color a few as possible so that all its constraints are satisfied
*/
/*
option2 =  0: assign to i the consistent color with the most occurences		
	
option2 =  2: assign the smallest possible color
*/
int					attempt;
int					best_color;
int					best_node;

struct particle		best_part;
struct vector_int	candidate1,candidate2;
int					c0,c;
int					c1,c2;
int					coeff_m;
struct color 		color;

int					color_min;
//struct color		colored_nodes;
int					confinement;

int					count;
float				d;
int					dmax;
struct color_list	hood_color;
int					inode;
int					i,j,j1,k,l,m;
int					largest,largest2;
int					loop;

int					max_attempt;
int					n_c,n_c1;
struct vector_int	n_color,not_color;

int					OK;
int					option2;
struct particle 	partt;
struct particle		partt2;
struct vector_int	used_times[2]; // [color] [number of times it is used] 


max_attempt=dplus.dmax;

//max_attempt=1;


color_min=diff_color(part.pos);

attempt=0;

begin:

count=0; // Just for test


option2=2;

if (option<3)
	confinement=option;
else
{
	confinement=1;
	loop=0;
}
//____________________________

try:

// Initialize the numbers of non modified neighbours

not_color.size=M.size;
for (inode=0;inode<M.size;inode++)
{
	not_color.val[inode]=dplus.dplus[inode].size;// Number of non modified neighbours
}


// Set color to NA (arbitrary value for "not modified")
color.size=M.size;
for (i=0;i<color.size;i++) 
	color.val[i]=NA;
	
partt=part;

used_times[0].size=0;

if (confinement==2)
{
	
	// Compute the two criteria for the first time
	largest=0;
	hood_color.size=0;
	for (inode=0;inode<M.size;inode++) // For each possible node i ...
	{	
		// Count how many _different_ (modified) colors in the neighbourhood
		n_color.val[inode]=0;

	}
}


//printf("\n inode loop. confinement %i\n",confinement);
for (inode=0;inode<M.size;inode++) // Choose the node to modify
{
	switch (confinement)
	{
		case 0:
		best_node=inode;
		break;

		//__________________
		case 1:
		//Select a non modified node i with the maximum of non modified neighbours

		dmax=-1;
		for (i=0;i<color.size;i++) // For each node ...
		{
			if (color.val[i]<=NA) // ... if not modified ...
			{
				if (not_color.val[i]>dmax) // ... check if it has the max of non modified neighbours
				{
					dmax=not_color.val[i];
					best_node=i;
				}
			}
		}


		// Decrease the number of non modified neighbours for each neighbour
		// (Note: works only for symmetric matrix)

		//printf("node %i dplus.dplus[node];size %i",node,dplus.dplus[node].size);
		for (i=0;i<dplus.dplus[best_node].size;i++)
		{
			not_color.val[dplus.dplus[best_node].val[i]]=not_color.val[dplus.dplus[best_node].val[i]]-1;
		}
		break;

		//___________________
		case 2:
		/*
		select the non modified node i which has the largest number of modified neighbours with different colors
			in case of a tie, select the one with the largest number of unmodified neighbours
				in case of a tie, select at random
		*/

		candidate1.size=0;
		largest2=0;
//printf("\n case 2");
		for (i=0;i<M.size;i++) // First criterion
		{
			if (color.val[i]>NA) continue; // Already modified
			if (n_color.val[i]<largest) continue; // Not enough modified neighbours
				candidate1.val[candidate1.size]=i;
				candidate1.size=candidate1.size+1;
				if (not_color.val[i]>largest2) largest2=not_color.val[i];
		}

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

		candidate2.size=0;

		for (i=0;i<candidate1.size;i++)
		{
			j=candidate1.val[i];

//printf("\n j, not_color.val[j] %i %i", j,not_color.val[j]);
			if (not_color.val[j]<largest2) continue;

				candidate2.val[candidate2.size]=j;
				candidate2.size=candidate2.size+1;
		}
//printf("\n candidate2.size %i",candidate2.size);

		if (candidate2.size==0)
		{
			printf("\n candidate1.size %i",candidate1.size);

			printf("\n largest2 %i",largest2);

			printf("\n ERROR admissible_color. candidate2.size=0");
			//best_node=candidate1.val[alea(0,candidate1.size-1)];

			infinite2:; goto infinite2;
			break;	
		}

		i=alea(0,candidate2.size-1);
		best_node=candidate2.val[i];
		
		//best_node=candidate2.val[0];
		break;
		
		//___________________
		default:
		best_node=inode;
		break;
	}

//printf(" %i",best_node);
	// Now, try to modify the color, "as few as possible"
	c0= (int)partt.pos.x[best_node];
	c=c0;

//printf("\n c %i",c);
	for (k=0;k<dplus.dplus[best_node].size;k++) // ... check the modified neighbours
	{
		j=dplus.dplus[best_node].val[k];
		if (color.val[j]<=NA) continue; // Not modified
		d=(float) fabs(c0-partt.pos.x[j])-M.val[best_node][j];
		if (d>=0) continue; // ... consistent
		
		// best_node has at least one unsatisfied constraint
		m=0;
		coeff_m=1;
		
		next_c:
		//coeff_m=-coeff_m;
		m=m+1;
		//for (m=1;m<M.size;m++) // Try another color
		{
			c=c0+coeff_m*m;
			OK=0;
//printf("\n c %i",c);
			//if (c>xmax)  goto minus_m;
			
			for (l=0;l<dplus.dplus[best_node].size;l++) // ... check the modified neighbours
			{
				j1=dplus.dplus[best_node].val[l];
				if (color.val[j1]<=NA) continue;

				d=(float) fabs(c-partt.pos.x[j1])-M.val[best_node][j1];
				if (d>=0) continue; // color c is ok for neighbour k
					 goto minus_m; // color c is not ok for neighbour k => try another color
//goto next_c;
			}
			// Color c is OK for all neighbours
//printf("\n node %i, color %.0f => %i", j,partt.pos.x[j],c);

//goto put_color;
			c1=c; 
			OK=1;
			
			minus_m:
			c=c0-coeff_m*m;
			//if (c<xmin) goto next_c;
			
			for (l=0;l<dplus.dplus[best_node].size;l++) // ... check the neighbours
			{
				j1=dplus.dplus[best_node].val[l];
				if (color.val[j1]<=NA) continue;

				d=(float) fabs(c-partt.pos.x[j1])-M.val[best_node][j1];
				if (d>=0) continue; // color c is ok for neighbour k
					 goto next_c; // color c is not ok for neighbour k => try another color
			}
			// Color c is OK for all neighbours
			if (OK==0) goto put_color;
	
			
			// Both c1 and c are possible. Find the most already used
			
			if (option2==0)
			{
				n_c=0;
				n_c1=0;
				for (l=0;l<used_times[0].size;l++)
				{
					c2=used_times[0].val[l];
					if (c2==c1) n_c1=used_times[1].val[l];
					if (c2==c) n_c=used_times[1].val[l];
				}
			
				if (n_c1>n_c) c=c1;
				if (n_c1==n_c)
				{		
					if (fabs(c1)<fabs(c)) c=c1;
					//c=MIN(c,c1);
					//if (alea_float(0,1)<0.5) c=c1;
				}
			}
			if (option2==2) if (fabs(c1)<fabs(c)) {c=c1;goto put_color;}
				
			
		//next_c:;
		}//m. Next color
		
	}//k.  Next neighbour

	put_color:

	partt.pos.x[best_node]= (float)c;
	best_color=c;

//printf(" %i/%i",best_node,best_color);	
//	
	color.val[best_node]=best_color;
	
	if (confinement==2) //  Modify the number of different colors in the neighbourhoods
	{
		// 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 (color.val[j]>NA) continue; //  already modified

			not_color.val[j]=not_color.val[j]-1; // decrease the number of non modified j's neighbours
			if (not_color.val[j]<0)
			{
				printf("\n ERROR. admissible_color. , not_color.val[j] %i %i. Max : %i",j, not_color.val[j], dplus.dplus[j].size);
				infinite:; goto infinite;
			}
			// Number of different colors used in the (modified) hood
			for (k=0;k<dplus.dplus[j].size;k++) 
			{
				l=dplus.dplus[j].val[k];
				if (color.val[l]<=NA) continue;
				if (color.val[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:;
		}
		
		largest=0; // Largest number of different colors in the hood for unmodified nodes

		for (i=0;i<M.size;i++)
		{
			if (color.val[i]>NA) continue;
			if (n_color.val[i]>largest)
			{
				largest=n_color.val[i];
			}
		}	
	}
	
	// Update how many times each color is used
		
		for (i=0;i<used_times[0].size;i++)
		{
			c=used_times[0].val[i];
			if (c==best_color)
			{
				used_times[1].val[i]=used_times[1].val[i]+1;
				goto end_used_times;
			}
		}
		// New color
			used_times[0].val[used_times[0].size]=best_color;
			used_times[1].val[used_times[0].size]=1;
			used_times[0].size=used_times[0].size+1;
		
		end_used_times:;

}// inode. Next node

if (option>2)
{
	if (loop==0)
	{
		partt2=partt;
		confinement=2;
		loop=loop+1;
		goto try;
	}
	else // Keep the best
	{
		c1=diff_color(partt.pos);
		c2=diff_color(partt2.pos);
		if (c2<c1) partt=partt2;
	}
}

/*
// Better to verify ...

color=convert_position_to_color(partt.pos);
i=check_color(color,M,dplus);
printf("\n Number of unsatisfied constraints: %i",i);

printf("\n Number of colors used: %i",i);
*/


//printf("\n admissible_color end");

best_part=partt;
attempt=attempt+1;

if (attempt<max_attempt)
{ 
	i=diff_color(best_part.pos);

	if (i<=cmax) return best_part;
	if (i<color_min)
	{
		color_min=i;	
	}

//printf("\n cmax %i",cmax);

	goto begin;
}


//printf("\n best_part.pos %f",best_part.pos.x[0]);
return best_part;
}


// ----------------------------------------------------------------------------- CHECK_COLOR
int	check_color(struct color color,struct matrix M, struct dplus dplus)
{ 
// Number of unsatisfied constraints
int i,j,k;
int uncons;

uncons=0;
for (i=0;i<M.size;i++)
{
	for (j=0;j<dplus.dplus[i].size;j++)
		{
		k=dplus.dplus[i].val[j];
		if (fabs(color.val[i]-color.val[k])<M.val[i][k]) uncons=uncons+1;
		}
}
return uncons;
}


// ----------------------------------------------------------------------------- COEFF_TIMES_VEL_COLOR
struct velocity coeff_times_vel_color(float coeff,struct velocity vel,struct matrix M)
{
/*
Option 0:  classical weighting

Option 1:
The graph has N nodes.
- choose a node at random
- from this node, build a connexe graph (as dense as possible) with coeff*N nodes (coeff<=1)
- keep just the velocity components corresponding to the nodes of this graph


*/
float coefft;
struct vector	g;
int				i,j;
int				n;
int				n1,n2;
int				option;
struct vector	used={0};
struct velocity velt; //{int size;float v[Max_vel];float ek;float v2[Max_vel];int combin;}

//printf("\n coeff_times_vel_color. coeff=%f, vel.size %i, vel.combin %i",coeff);
//display_velocity(vel);

option=0;

if (coeff==1)
{
	return vel;
}


velt.size=M.size;
velt.combin=0;


if (option==0)
{
	for (i=0;i<velt.size;i++)
	{
		velt.v[i]=coeff*vel.v[i];
	}
	return velt;
}

for (i=0;i<velt.size;i++) velt.v[i]=0;

if (coeff>1) coefft=(float) coeff-(float)floor(coeff); else coefft=coeff; // Just in case coeff>1

n=(int) coefft*M.size;
//printf("\n coefft, M.size,n: %f %i %i",coefft,M.size,n);
if (n==0) return velt;

i=alea(0,velt.size-1); // Choose the first node
g.x[0]=(float)i;
g.size=1;
used.x[i]=1;
//printf("\n first node %i",i);

if (n>1)
{
	for (j=0;j<g.size;j++) // For each node already used
	{
		n1=(int) g.x[j]; // n1 = node already used
		for (n2=0;n2<M.size;n2++) // Look for neighbours
		{
//printf("\n n1,n2 %i,%i",n1,n2);
		if (n1==n2) continue;
		if (used.x[n2]==1) continue; // Already used
		if (M.val[n1][n2]<=0) continue;  // No edge
//printf(": add %i",n2);
			g.x[g.size]=(float)n2;
			g.size=g.size+1;  // Note the trick: the upper bound of the loop is modified inside the loop
			if (g.size>=n) goto end;
				used.x[n2]=1;
		}
	
	}
}

end:

for (i=0;i<g.size;i++) 
{
	j=(int) g.x[i];
	velt.v[j]=vel.v[j];
}

//display_velocity(velt);
return velt;
}

// ----------------------------------------------------------------------------- COLOR_0
struct position		color_0(struct matrix M,struct dplus dplus,struct position color,struct param param)
{
// Backtrack

int					c;
int					c_diff;

int					cmax;

int					c_min,c_max;
struct position 	colort;
int					first;
int					i;
int					j;
int					k;
struct vector_int	old_c;

//printf("\n Color_0. ");
cmax=(int) param.max_fr;


colort=color;

for (i=0;i<M.size;i++)

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

	old_c.val[i]=c_min;

}