/* R L F . C
 * Recursive Largest-First Algorithm
 * from F. Thomas Leighton, 19??
 *
 * written August 3, 1983
 * by Catherine Schevon
 * BTL, Murray Hill, NJ
 */

#include <stdio.h>
#include <sys/types.h>
#include <sys/times.h>

#define INT 32
#define CHARBITS 8
#define edge(x,y) (bitmap[y/CHARBITS][x] & (1<<(y%CHARBITS)))

#define NMAX 1024		/* maximum number of vertices handles */
#define MAX_NR_VERTICES		1024	/* = NMAX */
#define MAX_NR_VERTICESdiv8	128	/* = NMAX/8 */
#define BOOL	char
#define MAX_PREAMBLE 10000
#define SGI

struct lnklst {
	int vertex;
	struct lnklst *p;
} *vertptr, *lastp;
struct {
	int size;
	int edges;
	struct lnklst *list;
} colors[NMAX];
typedef struct lnklst tlist;


int Nr_vert, Nr_edges;
BOOL Bitmap[MAX_NR_VERTICES][MAX_NR_VERTICESdiv8];
static char Preamble[MAX_PREAMBLE];
char masks[ 8 ] = { 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80 };

unsigned char bitmap[NMAX/CHARBITS+1][NMAX+1];

double init_soln(),next_change(),change_soln(),final_soln;
void display(),cost(),readgraph();
static int K; 			/* number of colors used */
static int N;			/* number of vertices in graph */
static int curr_score;		/* score of current solution */
static int runscore;	/* best-so-far */
static int best1_k,best2_k,best1_e; /* best colorings obtained */
static int bad_edges;		/* number of edges inside color classes */
static int oldclass,newclass;
static int old_count,new_count; /*change in bad edges in old & new classes */
static int delta_score;
static int delta_edges;
static int best[NMAX+1];
static double x_coord[NMAX+1], y_coord[NMAX+1];
static int chrom_num;
int srand();
int width;


static unsigned mask[INT] =
   {
   1, 1<<31, 1<<30, 1<<29, 1<<28, 1<<27, 1<<26, 1<<25, 1<<24,
   1<<23, 1<<22, 1<<21, 1<<20, 1<<19, 1<<18, 1<<17, 1<<16,
   1<<15, 1<<14, 1<<13, 1<<12, 1<<11, 1<<10, 1<<9, 1<<8,
   1<<7, 1<<6, 1<<5, 1<<4, 1<<3, 1<<2, 1<<1
   };  /* CAUTION - assumes 32 bit machine */
static int mattype;
static double dens, maxdist, dens1, dens2;

/* colorscheme array */
/* if color of node >  0, that's its color.
   if color         = -1, it is uncolored and in set U1.
   if color         = -2,                 and in set U2.
 */

struct colors {
	int v;		/* actual vertex number */
	int color;
	int degree;
	int dU2;	/* number of edges to nodes in set U2 */
} cs[NMAX];
typedef struct colors colorscheme;

int size;	/* size of current independent set */
int u_count; 	/* number of vertices currently in U1 */
int v;		/* node selected from U1 for coloring */
int top;	/* pointer to last uncolored node in cs array */


main (argc,argv)
int argc;
char *argv[];
{
	register int i,j;
	int flag;
	int v1,v2,v3;
	FILE *inputfile;

	if (argc < 2) {
		printf("Usage: give filename for input graph");
		exit(1);
	}
	printf("\n(%s)\n",argv[1]);
	if ((inputfile = fopen(argv[1], "r")) == NULL) {
		printf("Input graph does not exist");
		exit(1);
	}
	readgraph(inputfile);

	/* calculate degrees of each vertex */
	for (i=1;i<=N;i++) {
		cs[i].degree = 0;
		for (j=0; j<(width); j++)
			cs[i].degree +=  bitcount (bitmap[i][j]);
		cs[i].color = -1;
		cs[i].v = i;
	}

	top = N;
	K=0;
	for (;;) {
		/* initialize set U1 to all uncolored nodes */
		u_count = 0;
		for (i=1;i<=top;i++) {
			cs[i].color = -1;
			u_count++;
			cs[i].dU2 = 0;
		}
		if (u_count == 0) break;

		K++;
		/* find independent set K */
		size = 0;
		while (u_count) {
			/* pick vertex */
			v = 1;
			while (cs[v].color != -1) v++;
			if (size == 0) {
				/* pick maximum degree vertex */
				flag = 0;
				for (i=1;i<=top;i++)
					if (cs[v].degree < cs[i].degree)
						v = i;
			}
			/* pick maximum degree to U2; break ties in favor 
			 * of minimum overall degree */
			else {
			   for (i=1;i<=top;i++)
				if (cs[i].color == -1) {
					if (cs[v].dU2 < cs[i].dU2)
						v = i;
					else if ((cs[v].dU2 == cs[i].dU2)&&
					    (cs[v].degree>cs[i].degree))
						v = i;
				}
			}
			cs[v].color = K;
			u_count--;
			size++;

			/* drop all neighbors of v from U1 to U2 */
			/* and increment dU2's of their neighbors */
			v1 = cs[v].v;
			for (i=1; i<=top; i++) {
				v2 = cs[i].v;
				if ((cs[i].color == -1) && edge(v1,v2)) {
					cs[i].color = -2;
					u_count--;
					cs[i].degree--;
					/* increment dU2 of i's neighbors */
					for (j=1;j<=top;j++) {
					    v3 = cs[j].v;
					    if ((cs[j].color == -1) &&
					       edge(v2,v3))
							cs[j].dU2++;
					}
				}
			}
			/* flip v to colored end of list */
			v1 = cs[top].v;
			cs[top].v = cs[v].v;
			cs[v].v = v1;
			cs[v].degree = cs[top].degree;
			cs[v].dU2 = cs[top].dU2;
			cs[v].color = cs[top].color;
			cs[top].color = K;
			top--;
		}
		printf ("set %d: size = %d\n",K,size);
		consistency_check_r();
	}

	printf ("%d colors used\n",K);

}

consistency_check_r ()
{
	/* checks that the vertices with color K are an independent set */
	register int i,j;
	int v1,v2;
	int count = 0;

	for (i=top+1;i<=N;i++) {
		if (cs[i].color != K) break;
		count++;
		v2 = cs[i].v;
		for (j=i+1;j<N;j++) {
			if (cs[j].color != K) break;
			v1 = cs[j].v;
			if (edge(v2,v1))
				printf ("edge in set %d\n",K);
		}
	}
	if (count != size)
		printf ("Actual size of set = %d\n",count);
}

bitcount (n)
unsigned n;
{
	int b;

	b = 0;
	while (n != 0) {
		n &= (n-1);
		b++;
	}
	return b;
}

BOOL get_edge( i, j )
int i,j;
{
	int byte, bit;
	char mask;
	int k;

	if (i<j) {
		k = i;
		i = j;
		j = k;
	}
	
	bit  = 7-(j & 0x00000007);
	byte = j >> 3;
	
	mask = masks[bit];
	return( (Bitmap[i][byte] & mask)==mask );
}

void readgraph(fp) 
FILE *fp;
{
   int i,j;
   int length = 0;
   unsigned temp;

	if (!fscanf(fp, "%d\n", &length))
	  { printf("ERROR: Corrupted preamble.\n"); exit(10); }

	if(length >= MAX_PREAMBLE)
	  { printf("ERROR: Too long preamble.\n"); exit(10); }
		   
	fread(Preamble, 1, length, fp);
	Preamble[length] = '\0';
	
	if (!get_params())
		  { printf("ERROR: Corrupted preamble.\n"); exit(10); }

	if (Nr_vert >NMAX) {
		printf("Too many vertices! Recompile with NMAX > %d\n",
			Nr_vert);
		exit(0);
	}

	for ( i = 0
		 ; i < Nr_vert && fread(Bitmap[i], 1, (int)((i + 8)/8), fp)
		 ; i++ );

	fclose(fp);

   N = Nr_vert;

   for (i = 0; i < N; i++)
       for (j = 0; j < N; j++)
	   if (get_edge(i, j))
	       bitmap[(j+1)/CHARBITS][i+1] |= (1 << ((j+1) % CHARBITS));

}

int get_params()
                      /* getting Nr_vert and Nr_edge from the preamble string,
			containing Dimacs format "p ??? num num" */
{
	char c, *tmp;
	char * pp = Preamble;
	int stop = 0;
	tmp = (char *)calloc(100, sizeof(char));
	
	Nr_vert = Nr_edges = 0;
	
	while (!stop && (c = *pp++) != '\0'){
		switch (c)
		  {
			case 'c':
			  while ((c = *pp++) != '\n' && c != '\0');
			  break;
			  
			case 'p':
			  sscanf(pp, "%s %d %d\n", tmp, &Nr_vert, &Nr_edges);
			  stop = 1;
			  break;
			  
			default:
			  break;
		  }
	}
	
	free(tmp);
	
	if (Nr_vert == 0 || Nr_edges == 0)
	  return 0;  /* error */
	else
	  return 1;
	
}