// lb-sim-batch
// © 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)
// from average degree dl to average degree du, with step dstep
// n=2^k is the number of nodes of G
// m=d*n/2 is the number of edges of G
//
// Syntax: 
//
// lb-sim-batch [k] [dl] [du] [step] [output file name]
//  k is the exponent of a power of 2, while 
//  dl is the lower value of average degree of G
//  du is the upper value of average degree of G
//  dstep is the value of increasing 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, cl, cu, cstep; 
double d, dl, du, dstep; 

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 != 6) {
        printf("Syntax: lb-sim [k] [dl] [du] [dstep] [output file name] \n"); 
  exit(1);
 }

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

 dl = atof(argv[2]);
 cl = 0.5*dl;

 du = atof(argv[3]);
 cu = 0.5*du;
 
 dstep = atof(argv[4]);
 cstep = 0.5*dstep;

 d = dl;
 c = 0.5*d;
 
 
 while (c < cu + cstep)
 {
  numofedges = (int) (c*numofnodes); 
 
  initgraph ();

  randomgraph ();

  decimation_cut=0; 
  decimation ();  

  color_ESA2006 ();

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

  fp = fopen(argv[5], "a");

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

  fclose(fp);

  freegraph();
  
  c = c + cstep;
 }
  
 return 0; 
}//main