sig.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TRUE 1
#define FALSE 0
#define MAXNODES	100
#define MAXCOLORS 100		
#define MAXEDGES 100*(100-1)	

/* SIG Simplified Iterated Greedy graph coloring algorithm C.C. McGeoch 2011
	 Usage: sig <filename 

	 filename:	 input file containing algorithm parameters. See
					getinput.c for details. 
*/ 


//#define REPORTSTATS	0
//#define REPORTCOLORS	0
//#define DEBUG	0
#define ASSERT(cond, msg) if (! (cond)) {printf("msg \n"); exit(1);} ;

int numnodes=0;		/* number of nodes in the graph */
int numcolors=0;	 /* initialized to equal numnodes, then decreases	*/ 
int numedges=0;		/* total edges */

/*-------------------------------------------------------------*/
/* Graph and coloring representation													 */
/* The graph is an adjacency list in two arrays								*/ 
/*-------------------------------------------------------------*/ 

/* vertices named/indexed 1..n; colors named/indexed 1..n */ 
int edgex[MAXNODES+1];			/* vertex v: index to neighbor array */ 
int ecount[MAXNODES+1];		 /* vertex v: number of neighbors */ 
int neighbor[MAXEDGES+1];	 /* list of adjacent nodes */ 
int colorof[MAXNODES+1];		 /* vertex v: current color */ 

int curcolors;							 /* number distinct colors in coloring*/ 
int curcolorscore;					 /* sum of current colors in coloring + (curcolors*numnodes) */ 
int colorcount[MAXNODES+1];	/* color c: number of vertices this color */ 

int bestcoloring[MAXNODES+1]; /* save best coloring: i is col(v_i) */ 
int bestcolors; 
int bestcolorscore = MAXNODES+1;						

int vperm[MAXNODES+1];			 /* vertex permutation: pos i is name of v_i */ 
int cperm[MAXNODES+1];			 /* color permutation:	pos i is name of c_i */ 

/*Hand defined to allow for compilation*/
/*Defined by command line*/
FILE *fp = NULL;
int initpolicy = 1;

/*Hard coded for testing*/
int maxiter = 200;
int trials = 1;
int revert = 20;
int target = 1;
float ccutoffs[6]; /* ccutoffs is a 1 by 6 normalized probability vector */
float vcutoffs[4]; 				/* vcutoffs is a 1 by 4 normalized probability vector */
int initcolors;
int initcolorscore;
/*-------------------------------------------------------*/
/* algorithm statistics																	*/ 

int checkcount = 0; 

/*-----------------------------------------------------------*/
/* Utility functions																				 */

/*print usage----------------------------------------------------*/
void usage() {
	printf("sig graph_file initpolicy [options]\n");
	printf("--maxiter <int>			Max number of iterations, default 1000\n");
	printf("--trials <int>			Max trials, default 100\n");
	printf("--revert <int>			Max number of trials before revert, default 100\n");
	printf("--target <int>			Expected number of colors, default 100\n");
	printf("--vweight <int> <int> <int> <int>\n");
	printf("--cweight <int> <int> <int> <int> <int> <int>\n");
	printf("-h, --help			Print this message\n");
}

void parseinput(int argc, char** argv) {
	fp = fopen(argv[1], "r");
	if (NULL == fp){
		printf("Error opening file\n");
		exit(1);
	}
	initpolicy = atoi(argv[2]);

	for(int x = 0; x < 6; ++x) {
		ccutoffs[x] = 1.0/6.0;
	}

	for(int x = 0; x < 4; ++x) {
		vcutoffs[x] = 1.0/4.0;
	}

	/*parse flags*/
	for(int i = 3; i < argc; ++i) {
		if(!strncmp("--maxiter", argv[i], 9)) {
			++i;
			maxiter = atoi(argv[i]);
		} else if (!strncmp("--trials", argv[i], 8)) {
			++i;
			trials = atoi(argv[i]);
		} else if (!strncmp("--revert", argv[i], 8)) {
			++i;
			revert = atoi(argv[i]);
		} else if (!strncmp("--target", argv[i], 8)) {
			++i;
			target = atoi(argv[i]);
		} else if (!strncmp("-h", argv[i], 2) || !strncmp("--help", argv[i], 6)) {
			usage();
			exit(0);
		} else if (!strncmp("--cweight", argv[i], 9)) {
			++i;
			ccutoffs[0] = atof(argv[i]);
			++i;
			ccutoffs[1] = atof(argv[i]);
			++i;
			ccutoffs[2] = atof(argv[i]);
			++i;
			ccutoffs[3] = atof(argv[i]);
			++i;
			ccutoffs[4] = atof(argv[i]);
			++i;
			ccutoffs[5] = atof(argv[i]);
		} else if (!strncmp("--vweight", argv[i], 9)) {
			++i;
			vcutoffs[0] = atof(argv[i]);
			++i;
			vcutoffs[1] = atof(argv[i]);
			++i;
			vcutoffs[2] = atof(argv[i]);
			++i;
			vcutoffs[3] = atof(argv[i]);

		} else {
			printf("Unknown flag %s \n", argv[i]);
			exit(1);
		}
	}
}

/*---printcolors---------------------------------------------*/ 
void printcolors(int which) 
{
	int v; 

	if (which==0) {// print best 
		printf("best coloring:\t"); 
		for (v =1; v<= numnodes; v++) {
			printf("%d %d\t", v, bestcoloring[v]); 
			if (v % 10 == 0) printf("\n"); 
		}
		printf("\n best	%d	%d \n", bestcolors, bestcolorscore); 
	}
	else { // print current 
		printf("current coloring:\t"); 
		for (v =1; v<= numnodes; v++) {
			printf("%d %d\t", v, colorof[v]); 
			if (v % 10 == 0) printf("\n"); 
		}
		printf("\n curcolors,score	%d	%d \n", curcolors, curcolorscore); 
	}
}
/*---printgraph----------------------------------------------*/ 
void printgraph() 
{
	int src;
	int ex; 
	int i; 
 
	for (src = 1; src <= numnodes; src++) {
		ex = edgex[src];
		printf("\n v %d: ", src); 
		for (i=1; i <= ecount[src]; i++) {
			printf("%d \t", neighbor[ex++]);
		}
	}
	printf("\n"); 
}
/*--------------------------------------------------------------*/ 
/* getgraph: Read input file and build graph.									 */ 
/* Input Format:	
			First line is integer number of nodes. 
			Then (nodes are named 1..n):	
				 neighbors of v1, list ending with 0	
				 neighbors of v2, list ending with 0	
				 ... 
				 neighbors of vn, list ending with 0	
			Lines after n+1 inputs are ignored as comments.
*/
void getgraph()
{
	int i;	 
	int edgeindex = 1; 
	int edgecount; 
	int nodeval; 	

		fscanf(fp,"%d", &numnodes);	/* number of nodes in graph */
		numcolors = numnodes; 
		if (numnodes >MAXNODES) {
			printf("too many nodes: recompile and try again\n");
			exit(1); 
		}
 
		for (i=1; i <= numnodes; i++) { 
			edgex[i] = edgeindex;	
			fscanf(fp, "%d", &nodeval); 
			edgecount=0; 

			while (nodeval != 0) {	
	numedges++;				 /* total for accounting */
				edgecount++;				/* total neighbors this node */ 
				neighbor[edgeindex++] = nodeval; 
	fscanf(fp, "%d", &nodeval);				

			} // for each neighbor 
			ecount[i] = edgecount; 
		} // for each vertex 
} //getgraph 

/*--------------------------------------------------------------*/
/* Greedy coloring																							*/

/*--checkcolorok----------------------------------------------*/ 
int checkcolorok(int thenode, int thecolor)
{
	int ex = edgex[thenode];	/* index to neighbor list */ 
	int edges = ecount[thenode]; /* number of neighbors */ 
	int e=1;		 
	while (e++ <= edges){
	++checkcount;
		if (colorof [neighbor[ex++] ] == thecolor) return 0; /* false */ 
	}
	return	1; 
}
/*---colorit---------------------------------------------------*/ 
void colorit (int thenode, int thecolor) 
{
	colorof[thenode] = thecolor;
	colorcount[thecolor]++; 
}	 
/*---greedycolorgraph-----------------------------------------------------------*/ 
/* recolors the graph respecting vperm, cperm, and current colors							 */ 
void greedycolorgraph()
{
	int v , vertex; 
	int k, c; 

	for (k = 1; k <= numnodes; k++) colorcount[k] = 0; // initialize 
	curcolors=0; 
	curcolorscore=0; 

#ifdef DEBUG
	printf("\nbefore greedy color: ");
	printcolors(1); 
	printf("\n vperm is: \t");
	for (v = 1; v <= numnodes; v++) printf("%d \t", vperm[v]);
	printf("\n cperm is: \t");
	for (c = 1; c <= numcolors; c++) printf("%d \t", cperm[c]);
#endif 

	for (v = 1; v <= numnodes; v++) { // for each vertex 
		vertex = vperm[v];	// respecting vperm 

		for (k = 1; k <= numcolors; k++ ) { // for each color	
			int color = cperm[k] ;	 // respecting cperm 

			if (checkcolorok(vertex, color)) {	 // if ok 
				colorit(vertex, color);						// set colorof
				curcolorscore += color;						// sum of colors assigned in coloring	
				if (curcolors < k) curcolors=k;		// number of distinct colors assigned 
				break; 
			}//if 
		}//for k
	}//for v

	curcolorscore += curcolors*numnodes;	//finish curcolorscore	
	if (curcolors < numcolors) numcolors = curcolors;	// reduce size of color set 

#ifdef DEBUG
	printf("\nafter greedy color:	");
	printcolors(1);
	printf("curcolors %d curcolorscore %d	numcolors %d\n", curcolors, curcolorscore, numcolors);
#endif 

} // greedycolorgraph 

/*---saveAsBest---------------------------------------------------*/ 
void saveAsBest() {
	int v; 

	for (v=1; v<=numnodes; v++)	bestcoloring[v] = colorof[v];
	bestcolors=curcolors;	// should equal numcolors 
	bestcolorscore=curcolorscore; 
#ifdef DEBUG 
	printf("save best\n"); 
#endif 
} 
/*---revertToBest-------------------------------------------------*/ 
void revertToBest() {
	int v;
	for (v=1; v<= numnodes; v++) colorof[v] = bestcoloring[v];
	curcolors=bestcolors;
	curcolorscore = bestcolorscore;
#ifdef DEBUG
	printf("revert \n");
#endif 

}

/*--pickRandomColorRule------------------------------------------------*/
int pickRandomColorRule() {
	
	double	pr = drand48(); 
	int i;	
	for (i=0; i < 6; ++i) {
		if (pr <= 0) {
			break;
		}
		pr -= ccutoffs[i];
	}
	return i; 
}

/*--pickRandomVertexRule-----------------------------------------------*/ 
int pickRandomVertexRule() {
	double pr = drand48();
	int i;
	for (i=0; i < 4; ++i){
		if(pr <= 0) {
			break;
		}
		pr -= vcutoffs[i];
	}
	return i; 
} 

/*---vertexreorder--------------------------------------*/ 
void vertexreorder(int vr) { 
	 /* vertex re-order puts vertices in groups according to color, by rule: 
				0: 1..k	colors going up 
				1: k..1	colors going down 
				2: random color order
				3: by decreasing total degree in color set	
	 builds vperm[1..n] vperm[i] names the vertex to be considered ith in turn	
	*/ 
	int i;
	int colorhead[numnodes+1];	// start of each color list 
	int next[numnodes+1];			 // next vertex in color list 
	int order[numnodes+1];			// temp for ordering colors 
	int c, k, cc, r; 
	int vpermx=0;
	int vx; 
	int tmp; 
	int max; 
	int v; 

 // gather vertices according to color
	for (k=1; k <= numnodes; k++) { //numnodes = max colors 
		colorhead[k] = 0;	
		next[k] = 0;
	}
	for(v=1; v<= numnodes;v++) {
		c = colorof[v];
		next[v] = colorhead[c];
		colorhead[c] = v; 
	}

#ifdef DEBUG
	printf("vertex rule %d: ", vr);
	switch(vr) {
	case 0: printf("1..k\n"); break;
	case 1: printf("k..1\n"); break;
	case 2: printf("random\n"); break;
	case 3: printf("decreasing vcount in colorset\n"); break;
	}
#endif 

	//copy into vperm by color group and rule 
	vpermx = 1; // index into vperm 

	switch(vr) {
	case 0: // vertices by increasing colors (skipping unused colors)	 
		for (c = 1; c <= numnodes; c++) {
			vx = colorhead[c];
			while (vx != 0) { 
	vperm[vpermx++] = vx;
	vx = next[vx];
			}
		}// for 
		break; 
	case 1: // vertices by decreasing colors (skipping unused colors) 
		for (c = numnodes; c>= 1; c--) {
			vx = colorhead[c];
			while (vx != 0) {
	vperm[vpermx++] = vx;
	vx = next[vx];
			}
		}//for 
		break; 

	case 2:	//vertices by random color gropus 
		for (i = 1; i <= numnodes; i++) order[i] = i; // initialize order 
		for (i = numnodes;	i >= 2; i--){						 // random permute 
			r =	(int) (drand48() * i) +1	;						//1..i inclusive 
			tmp= order[i];
			order[i] = order[r];
			order[r]=tmp;
		}

		for (c = 1; c <= numnodes; c++) {//build vperm 
			cc = order[c]; 
			vx = colorhead[cc];
			while (vx != 0){
	vperm[vpermx++] = vx;
	vx = next[vx];
			}
		}//for 
		break;

	case 3: //vertices by decreasing vcount in colorset 
		for (c = 1; c <= numnodes; c++) order[c] = colorcount[c]; // copy it 
		while ( TRUE ) {	// at most maxnodes passes, usually fewer 
			max = -1; 
			for (c = 1; c <= numnodes; c++) if (max < order[c]) max = order[c]; 

			for (c = 1; c <= numnodes; c++) { // copy all groups with max colors 
	if (max == order[c] ) {
		vx	= colorhead[c]; 
		while (vx != 0) {
			vperm[vpermx++] = vx;
			vx=next[vx];
		}
		order[c] = -1 ;	//remove it from copy 
	}//if max 
			}// c passes 
			 if (max==0) break;	// last colorcount was 0, done			 
		}// while true 
		break;
	}//switch 

}//vertexreorder 

/*-----------------------------------------------------------------*/ 
/* colorreroder sets the colors in order to be considered				 */ 
void colorreorder (int cr) { 
	/*re-order colors in cperm[1..numcolors] by color rule	
		0: 1..k up 
		1: largest color set first 
		2: smallest color set first 
		3: random colors 
		4: down k..1 
		5: reverse current order 
result is array cperm[1..numcolors] (just the front): cperm[i] names the ith color 
	*/ 
	int i, c, cx; 
	int r; 
	int tmp; 
	int order[numnodes+1];		 
	int coloruse[numnodes+1] ;	// which colors are in the mix? 
	int newcperm[numnodes+1];	
	int newx=1;	
	int max; 
	int min; 

	for (c = 1; c <= numnodes; c++)	coloruse[c] = FALSE; 
	for (c = 1; c <= numcolors; c++) coloruse[ cperm[c] ] = TRUE; //use this color 

#ifdef DEBUG
	printf("color reorde rules	%d number colors is %d: ", cr, numcolors);
	switch(cr) {
	case 0: printf("1..k\n"); break; 
	case 1: printf("largest first\n"); break;
	case 2: printf("smallest first\n"); break;
	case 3: printf("random\n"); break;
	case 4: printf("k..1\n"); break; 
	case 5: printf("reverse current\n"); break; 
	}
	printf("use these colors: "); 
	for(c =1; c <= numcolors; c++) printf(" %d\t" , cperm[c]); 
	printf("\n"); 
#endif 

	switch (cr) {
	case 0: // 1..k up 
		cx = 1; 
		for (c = 1; c<= numnodes; c++)							 // for all colors in up order 
			if (coloruse[c] == TRUE) cperm[cx++] = c;	// if in use, put it next in cperm 
		break; 

	case 1:	// largest color set first among those in front of cperm 
		for (c = 1; c <= numcolors; c++) {
			order[ cperm[c] ] = colorcount[ cperm[c] ]; // copy 
		}
		newx=1; 
		
		while (TRUE) {
			max = -1; 
			for (c = 1; c <= numcolors; c++) {
	if (order[cperm[c] ] > max) max = order[cperm[c] ];
			}
			if (max<=0) break; // ignore unused colors 
			for (c = 1; c <= numcolors; c++) {
	if (order[cperm[c]] == max) { // copy all colors with max count 
			newcperm[newx++] = cperm[c]; 
			order[cperm[c] ] = -1;	// reset 
		}
			}
		}//while 
		for (c = 1; c <= numcolors; c++) cperm[c] = newcperm[c];	
		break;
		
	case 2: // smallest colorset first, not including 0 counts	
		for (c = 1; c <= numcolors; c++) {
				order[ cperm[c] ] = colorcount[ cperm[c] ]; // copy `
		} 
		newx=1; 
		while (TRUE) {
			min = numnodes+1 ; 
			for (c = 1; c <= numcolors; c++) 
	if (order[cperm[c] ] < min ) min = order[cperm[c] ];
			if (min==numnodes+1) break; // done finding colors to copy 
			for (c = 1; c <= numcolors; c++) {
	if (order[cperm[c]] == min) {
			newcperm[newx++] = cperm[c]; 
			order[cperm[c] ] = numnodes+2;	// reset to higher number
		}
			}
		}// while 
		for (c = 1; c <= numcolors; c++) cperm[c] = newcperm[c];	
		break;

	case 3: // random	order among front colors	
		for (i = numcolors;	i >= 2; i--){
			r =	(int) (drand48() * i) +1 ; //1..i inclusive 
			tmp= cperm[i];
			cperm[i] = cperm[r];
			cperm[r]=tmp;
		}
		break;

	case 4: // down k..1 among front of cperm 
	 cx = 1; 
	 for (c = numnodes; c>= 1; c--) {					// for all colors in down order 
		 if (coloruse[c] == 1) cperm[cx++] = c;	// if in use, put it next in cperm 
	 }
	 break; 

	case 5: // reverse current order : 
		cx = 1; 
		for (c = numcolors; c>= 1; c--) newcperm[cx++] = cperm[c]; 
		for (c = 1 ; c <= numcolors; c++) cperm[c] = newcperm[c]; 
		break; 
	}//switch 

	/* now cperm[1..numcolors] has the new color permutation	*/ 

} // reordercolor 

/*---initialcoloring()--------------------------------------------------*/ 
void initialcoloring() 
 {
 	int v,i,r, c, tmp; 
	for (i = 1; i<= numnodes; i++)	vperm[i] = i;	 //initialize vertex permutation
	for (i = 1; i<= numcolors; i++) cperm[i] = i;	 //initialize	color permutation 

	switch (initpolicy) {
		case 1:	// n distinct colors 
			for (v=1; v<=numnodes; v++) {
				colorof[v] = v;	
				colorcount[v]=1; 
				curcolorscore += v;
	 		}
			curcolors=numnodes; 
			curcolorscore += curcolors * numnodes;	
			numcolors=curcolors; 
			break; 
	
		case 2: // greedy with random vertex order, color order increasing	
			for (i = numnodes;	i >= 2; i--){
				r =	(int) (drand48() * i) +1 ; //1..i inclusive 
				tmp= vperm[i];
				vperm[i] = vperm[r];
				vperm[r]=tmp;
			}
			for (v=1; v<= numnodes; v++) {
				colorof[v] = 0;	//initialize vertices to not colored 
			}
			greedycolorgraph(); 
			break; 
		case 3: //greedy fixed vertex order
			greedycolorgraph();
			break;
	 }//switch	

	initcolors = curcolors;
	initcolorscore = curcolorscore;
}//initialcoloring 

/*-----------------------------------------------------------*/ 
/* SIG: simple iterated greedy coloring											*/

void sigcolor() {

	initialcoloring(); 
	saveAsBest(); 

#ifdef DEBUG 
	printf("after initialize\n"); 
	printcolors(0); //best
	printcolors(1); //current
#endif 

	int t = 0; // total iterations 
	int b = 0; // iterations since last save (new best) 
	int r = 0; // iterations since most recent (savebest, revert)	 

	int cr=0; 
	int vr=1; //rules 
	
	while ((b < maxiter) && (bestcolors > target)) {
		t++;	b++;	r++;	

	/* replaces pickRandomColorRule and pickRandomVertexRule */
		//vr = (vr+1) % 4; 
		//cr = (cr+1) % 6;	

		cr = pickRandomColorRule();
		vr = pickRandomVertexRule();

#ifdef DEBUG
		printf("\niteration %d color rule %d vertex rule %d\n", t, cr, vr); 
#endif 

		vertexreorder(vr);
		colorreorder(cr); 
		greedycolorgraph(); // recolor, respecting old colors

		if (curcolors < bestcolors) {// if this is a new min color count 
			saveAsBest();
			b = 0;	
			r = 0;										// new improvement 
		} 
		else if (curcolorscore < bestcolorscore) { // if this is a new min color score 
			saveAsBest();	
			b = 0; 
			r = 0; // new improvement	
		}
		if (r > revert) {
			revertToBest();
			r=0;
		} 
	}//while 

}//sigcolor


/*--main---------------------------------------------------------*/ 
int	main(int argc, char* argv[])
{

	if (argc < 3){
		usage();
		return 1;
	} else {
		parseinput(argc, argv);
	}

//	transinput();	// command file/parameters from standard in 
	getgraph();		// input graph	(from file named in command file) 

#ifdef DEBUG	
		printf("the graph:\n"); 
		printgraph(); 
#endif 

		int i;	

		for (i = 0; i < trials; i++) { 
			checkcount=0;
			bestcolors=0;
			bestcolorscore=0; 
			
			// what else to initialize: maxcolor=0; colorcount=0; checkcou
		
			sigcolor() ; 

#ifdef REPORTSTATS 
			printf("i n	m	it	compares maxcolor	colorcount	\n");
			printf("%d	%d %d	%d	%d			%d			 %d					\n", 
			 i, numnodes, numedges, trials, 
			 checkcount, bestcolors, bestcolorscore);
#endif 

#ifdef REPORTCOLORS
//			printcolors(0);
//			printcolors(1);
#endif 
			printf("%d,%d,%d,%d\n", bestcolorscore, bestcolors, initcolorscore, initcolors);
		}//for trials 

		return(0); 
} /* end main */