// lb-sim
// (c) A.C. Kaporis, L.K. Kirousis, and E.C. Stavropoulos, 2006 
// 
// Purpose: 
//
// Computes the maximum cut of a random generated graph G in G(n,m)
// n=2^k is the number of nodes of G
// m=d*n/2 is the number of edges of G
//
// Syntax: 
//
// lb-sim [k] [d] [output file name]
//		k is the exponent of a power of 2
//		d is the average degree of G
//		The output is directed to output file name (also to the standand output)  
//
// Output format: 
//
// number of nodes, average degree, and the maximum cut of graph G  
//
// Reference paper: 
//
// A.C. Kaporis, L.K. Kirousis, and E.C. Stavropoulos,
// Approximating almost all instances of Max-Cut within a ratio above the H{\aa}stad threshold. 
// In Proc of ESA 2006, LNCS 4168, pp. 432--443, 2006
//


#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <time.h>


#define UNCOLORED -1
#define RED 0
#define BLUE 1
#define MAXVARS 100

typedef struct _Tneigh
{ 
	int who;
	struct _Tneigh *next;
} Tneigh;

typedef struct
{
	Tneigh *neigh;
	int degree;
} Tnode;

typedef struct
{
	int neighcolored[2];
	int mycolor;
} Tnodecolor;

Tnode *nodes;
Tnodecolor *nodecolors;

int k, numofnodes, numofedges;
double c, d; 
FILE *fp;
int decimation_cut=0; 


void *alloc (size_t n)
{
	void *ret;
	
	ret = malloc(n);
	if (ret == 0) 
	{
		printf ("out of memory! Exiting...\n");
		exit(0);
	}
	return (ret);
}

int randomnumber (int size)
{
	return (rand() % size);
}

void initgraph ()
{
	int i;

	nodes = (Tnode *) alloc (numofnodes*sizeof (Tnode));
	nodecolors = (Tnodecolor *) alloc (numofnodes*sizeof(Tnodecolor));

	for (i=0;i<numofnodes;++i)
	{
		nodes[i].degree = 0;
		nodes[i].neigh = 0;
	}

}

void freegraph ()
{
	int i;
	Tneigh *p, *pnext;

	for (i=0;i<numofnodes;++i)
	{
		p=nodes[i].neigh;
		while (p)
		{
			pnext = p->next;
			free (p);
			p=pnext;
		}
	}

	free (nodes);
	free (nodecolors);
}

void randomgraph ()
{
	int i, distinct, endpoint1, endpoint2;
	Tneigh *p, *prev;

	for (i=0;i<numofedges;++i)
	{
		endpoint1 = randomnumber (numofnodes);
		distinct = 0;
		while (!distinct)
		{
			endpoint2 = randomnumber (numofnodes);
			if (endpoint2 != endpoint1)
				distinct = 1;
		}
		if (nodes[endpoint1].degree == 0)
		{
			nodes[endpoint1].neigh = (Tneigh *) alloc (sizeof(Tneigh));
			nodes[endpoint1].neigh->who = endpoint2;
			nodes[endpoint1].neigh->next = 0;
		}
		else 
		{
			p = nodes[endpoint1].neigh;
			while (p)
			{
				prev = p;
				p = p->next;
			}
			p = (Tneigh *) alloc (sizeof(Tneigh));
			prev->next = p;
			p->who = endpoint2;
			p->next = 0;
		}
		nodes[endpoint1].degree++;

		if (nodes[endpoint2].degree == 0)
		{
			nodes[endpoint2].neigh = (Tneigh *) alloc (sizeof(Tneigh));
			nodes[endpoint2].neigh->who = endpoint1;
			nodes[endpoint2].neigh->next = 0;
		}
		else 
		{
			p = nodes[endpoint2].neigh;
			while (p)
			{
				prev = p;
				p = p->next;
			}
			p = (Tneigh *) alloc (sizeof(Tneigh));
			prev->next = p;
			p->who = endpoint1;
			p->next = 0;
		}
		nodes[endpoint2].degree++;
	}

	for (i=0;i<numofnodes;++i)
	{
		nodecolors[i].mycolor = UNCOLORED;
		nodecolors[i].neighcolored[RED] = 0;
		nodecolors[i].neighcolored[BLUE] = 0;
	}
}

int countcut ()
{
	int i,cut;

	cut =0;
	for (i=0;i<numofnodes;++i)
		if (nodecolors[i].mycolor == BLUE)
			cut += nodecolors[i].neighcolored[RED];
	return (cut);
			
}


 //delete edge (endpoint1, endpoint2) where deg(endpoint1)=0
 void delete_edge(int endpoint1, int endpoint2)
 {
	Tneigh *p, *pnext;
	int found=0;
	
	if (nodes[endpoint1].degree == 1)
		nodes[endpoint1].neigh = 0;
	nodes[endpoint1].degree--;

	if (nodes[endpoint2].degree == 1)
		nodes[endpoint2].neigh = 0;
	else{
		if (nodes[endpoint2].neigh->who == endpoint1)
			nodes[endpoint2].neigh = nodes[endpoint2].neigh->next;
		else
		{
			p=nodes[endpoint2].neigh;
			while(!found){
				pnext = p->next;
				if (pnext->who == endpoint1){ 
						found=1;
						p->next = pnext->next;
				}
				else 
					p=p->next;
			}
		}
	}
	nodes[endpoint2].degree--;
}//delete_edge


void decimation()
{
	Tneigh *p;
	int i,j; 

	int endpoint1, endpoint2;
	for (j=0; j<numofnodes; j++)
		for (i=0;i<numofnodes;++i){
			if (nodes[i].degree == 1) {
				endpoint1 = i;
				p=nodes[i].neigh;
				endpoint2 = p->who;
				delete_edge(endpoint1, endpoint2);
				decimation_cut++;
			}
		} 	
} 


//////////////////////////////////////////////////////////////////////////////
///////////////////////// Coloring Algorithm /////////////////////////////////
//////////////////////////////////////////////////////////////////////////////
void color_ESA2006 ()
{
	int i,j,n;
	int discrepancy;
	int max_discrepancy = -1;
	int uncolored_degree;
	int min_uncolored_degree = numofedges;
	int numofcolorednodes = 0;

	Tneigh *p;

	for (i=0;i<numofnodes;++i)
	{
		nodecolors[i].mycolor = UNCOLORED;
		nodecolors[i].neighcolored[RED] = 0;
		nodecolors[i].neighcolored[BLUE] = 0;
	}

	while (numofcolorednodes < numofnodes) 
	{

		//color all nodes with uncolored_degree=0
		for (j=0;j<numofnodes;++j) 
		{
			if (nodecolors[j].mycolor == UNCOLORED )  
			{
				uncolored_degree = nodes[j].degree - nodecolors[j].neighcolored[BLUE] - nodecolors[j].neighcolored[RED]; 
				if (uncolored_degree == 0) //color it now
				{ 
					n = j;
					numofcolorednodes++;
					//printf("%d \t color node %d with uncolored_degree %d \n", numofcolorednodes, n, uncolored_degree);
					if (nodecolors[n].neighcolored[RED] > nodecolors[n].neighcolored[BLUE])
					{
						nodecolors[n].mycolor = BLUE;
						p=nodes[n].neigh;
						while (p)
						{	
							nodecolors[p->who].neighcolored[BLUE]++;
							p=p->next;
						}
					}
					else if (nodecolors[n].neighcolored[RED] < nodecolors[n].neighcolored[BLUE])
					{
						nodecolors[n].mycolor = RED;
						p=nodes[n].neigh;
						while (p)
						{
							nodecolors[p->who].neighcolored[RED]++;
							p=p->next;
						}
					}
					else
					{
						nodecolors[n].mycolor = randomnumber (2);
						p=nodes[n].neigh;
						while (p)
						{
							nodecolors[p->who].neighcolored[nodecolors[n].mycolor]++;
							p=p->next;
						}
					}
				}
			}
		}


		// find an uncolored node with max discrepancy 
		max_discrepancy = -1;
		for (j=0;j<numofnodes;++j)
		{
			if (nodecolors[j].mycolor == UNCOLORED && nodes[j].degree > 1)
			{
				discrepancy = abs(nodecolors[j].neighcolored[BLUE]-nodecolors[j].neighcolored[RED]);
				if (discrepancy > max_discrepancy)
				{
					n = j;
					max_discrepancy = discrepancy;
				}
			}
		}

		//find an uncolored node with max_discrepancy having the minimun number of uncolored neighbors
		min_uncolored_degree = numofedges; 
		for (j=0;j<numofnodes;++j)
		{
			if (nodecolors[j].mycolor == UNCOLORED && nodes[j].degree > 1)
			{
				discrepancy = abs(nodecolors[j].neighcolored[BLUE]-nodecolors[j].neighcolored[RED]);
				if (discrepancy == max_discrepancy)
				{
					uncolored_degree = 	nodes[j].degree-nodecolors[j].neighcolored[RED]-nodecolors[j].neighcolored[BLUE];
					if (uncolored_degree < min_uncolored_degree)
					{
						min_uncolored_degree = uncolored_degree;
						n = j;
					}
				}

			}
		}

		//color node n 
		if (nodecolors[n].mycolor == UNCOLORED && nodes[n].degree > 1)
		{
			numofcolorednodes++; 
			if (nodecolors[n].neighcolored[RED] > nodecolors[n].neighcolored[BLUE])
			{
				nodecolors[n].mycolor = BLUE;
				p=nodes[n].neigh;
				while (p)
				{
					nodecolors[p->who].neighcolored[BLUE]++;
					p=p->next;
				}
			}
			else if (nodecolors[n].neighcolored[RED] < nodecolors[n].neighcolored[BLUE])
			{
				nodecolors[n].mycolor = RED;
				p=nodes[n].neigh;
				while (p)
				{
					nodecolors[p->who].neighcolored[RED]++;
					p=p->next;
				}
			}
			else
			{
				nodecolors[n].mycolor = randomnumber (2);
				p=nodes[n].neigh;
				while (p)
				{
					nodecolors[p->who].neighcolored[nodecolors[n].mycolor]++;
					p=p->next;
				}
			}
		}
	}
}




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

	if (argc != 4) {
       	printf("Syntax: lb-sim [exponent of a power of 2] [average degree] [output file name] \n"); 
		exit(1);
	}

	srand( (unsigned)time( NULL ) );
		
	k = atoi(argv[1]);
	numofnodes = (int) pow(2,k);

	d = atof(argv[2]);
	c = 0.5*d;
	
	numofedges = (int) (c*numofnodes); 
	
	fp = fopen(argv[3], "a");

	initgraph ();

	randomgraph ();

	decimation ();  

	color_ESA2006 ();

	printf ("n=%d \t d=%4.1f \t cut=%10.8f \n", 
			numofnodes, d, (double) (countcut()+ decimation_cut) / (double) numofedges);

	fprintf (fp, "n=%d \t d=%4.1f \t cut=%10.8f \n", 
			numofnodes, d, (double) (countcut()+ decimation_cut) / (double) numofedges);

	fclose(fp);

	freegraph();

	return 0;	
}//main