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

/* Define status indicators for vertices:
   ACTIVE means this vertex is not yet colored.
   IN_IND_SET means this vertex is included in the next independent set.
   NOT_ININD_SET means this vertex is not in the next independent set.
   DELETED means that this vertex is already colored. */
#define ACTIVE 1
#define IN_IND_SET 2
#define NOT_IN_IND_SET 3
#define DELETED 4

/* A shortcut */
typedef unsigned int uint;

/* A node in the adjacency list */
typedef struct _node {
   uint nbr;            /* Neighbor index in the array of vertex headers */
   struct _node *next;  /* Next pointer in the linked list */
} node;

/* A vertex header */
typedef struct {
   char name[16]; /* Name of a vertex: integer for G, a pair of integers for L(G) */
   uint degree;   /* Degree of the vertex */
   uint tmpdeg;   /* A temporary variable used in the computation of independent sets */
   uint status;   /* One of the above four #define's statuses */
   uint color;    /* The color the vertex receives. 0 means not yet colored. */
   node *alist;   /* Pointer to the adjacency list */
} vertex;

typedef vertex *graph;  /* A graph is an array of vertex headers */

/* Generate a random graph with n nodes and with each edge being present
   with probability p */
graph genRandomGraph ( uint n, double p )
{
   int u, v;
   graph G;
   node *ptr;

   /* Initialize memory */
   G = (vertex *)malloc(n * sizeof(vertex));
   for (u=0; u<n; ++u) {
      sprintf(G[u].name, "%u", u);
      G[u].degree = 0;
      G[u].tmpdeg = 0;
      G[u].status = ACTIVE;
      G[u].color = 0;
      G[u].alist = NULL;
   }

   /* Randomly generate edges */
   for (u = n-1; u >= 1; --u) {
      for (v = u-1; v >= 0; --v) {
         if ((double)rand() / (double)RAND_MAX <= p) {
            /* Insert v in the adjacency list of u */
            ptr = G[u].alist;
            G[u].alist = (node *)malloc(sizeof(node));
            G[u].alist -> nbr = v;
            G[u].alist -> next = ptr;
            ++G[u].degree;

            /* Insert u in the adjacency list of v */
            ptr = G[v].alist;
            G[v].alist = (node *)malloc(sizeof(node));
            G[v].alist -> nbr = u;
            G[v].alist -> next = ptr;
            ++G[v].degree;
         }
      }
   }

   return G;
}

/* Print the vertices of a graph. For each vertex, the neighbors are shown.
   The colors of vertices and neighbors are shown within square brackets. */
void prnGraph ( graph G, uint n )
{
   uint u;
   node *ptr;

   for (u=0; u<n; ++u) {
      printf("%9s [%u] :", G[u].name, G[u].color);
      ptr = G[u].alist;
      while (ptr != NULL) {
         printf(" %s [%u]", G[ptr -> nbr].name, G[ptr -> nbr].color);
         ptr = ptr ->next;
      }
      printf("\n");
   }
}

/* Generate a maximal independent set in the active (uncolored) part of G */
void getIndependentSet ( graph G, uint n )
{
   uint mindeg, u, v, w, m;
   node *ptr, *q;

   m = 0;
   for (u=0; u<n; ++u) 
      if (G[u].status == ACTIVE)     /* This vertex is uncolored */
         G[u].tmpdeg = G[u].degree;  /* Store its degree in a temporary variable */
      else
         ++m;                        /* m denotes the number of vertices considered */

   /* Repeat so long as there are active vertices which are not yet considered
      for inclusion or exclusion in the independent set being computed. */
   while (m < n) {
      /* First find an active vertex w of the smallest remaining degree */
      mindeg = w = n;
      for (u=0; u<n; ++u) {
         if ((G[u].status == ACTIVE) && (G[u].tmpdeg < mindeg)) {
            mindeg = G[u].tmpdeg;
            w = u;
         }
      }

      /* Include w in the independent set */
      ++m;
      G[w].status = IN_IND_SET;
      ptr = G[w].alist;

      /* Exclude all the active neighbors v of w from the independent set*/
      while (ptr != NULL) {
         v = ptr -> nbr;
         if (G[v].status == ACTIVE) {
            ++m;
            G[v].status = NOT_IN_IND_SET;

            /* Decrease the degrees of all neighbors of v */
            q = G[v].alist;
            while (q != NULL) {
               w = q -> nbr;
               if (G[w].status == ACTIVE) --G[w].tmpdeg;
               q = q -> next;
            }
         }

         ptr = ptr -> next;
      }
   }
}

/* Greedy vertex coloring of G with n vertices. This function returns the
   number of colors used. */
uint color ( graph G, uint n )
{
   uint u, v, m, c;
   node *ptr;

   /* m stands for the number of vertices that are already colored.
      c stands for the last color used. */
   m = c = 0;

   /* Repeat until all vertices are colored */
   while (m < n) {
      /* First generate a maximal independent set */
      getIndependentSet(G,n);

      /* Going to use a new color */
      ++c;

      for (u = 0; u < n; ++u) {
         /* All vertices in the independent set are colored with the new color */
         if (G[u].status == IN_IND_SET) {
            ++m;                    /* Another node colored */
            G[u].color = c;         /* The assignment of the new color */
            G[u].status = DELETED;  /* Done with this node */

            /* Look at all the unprocessed neighbors of u. Because u is
               now deleted from the graph, the degrees of each of these
               neighbors decreases by 1. */
            ptr = G[u].alist;
            while (ptr != NULL) {
               v = ptr -> nbr;
               if ((G[v].status == ACTIVE) || (G[v].status == NOT_IN_IND_SET))
                  --G[v].degree;
               ptr = ptr -> next;
            }
         } else if (G[u].status == NOT_IN_IND_SET) {
            /* This node could not be colored in this iteration. Make it
               active again. */
            G[u].status = ACTIVE;
         }
      }
   }
   return c;
}

/* Given a graph G with n vertices, this function returns the line graph
   L(G) of G. The number of edges in L(G) is passed via m. */
graph lineGraph ( graph G, uint n, uint *m )
{
   uint u, v, u1, v1;
   int e, f;
   node *ptr;
   graph H;

   /* Recompute the degrees of the vertices of G. These were destroyed
      by the coloring function. Also accumulate in e the sum of the degrees
      of the vertices. */
   e = 0;
   for (u = 0; u < n; ++u) {
      G[u].degree = 0;
      ptr = G[u].alist;
      while (ptr != NULL) { ++G[u].degree; ptr = ptr -> next; }
      e += G[u].degree;
   }

   *m = ((uint)e >> 1);  /* Degree-sum formula */

   e = 0; /* e is going to be used for another purpose. */

   /* Allocate memory for the line graph */
   H = (vertex *)malloc((*m) * sizeof(vertex));

   /* Initialize the vertex headers */
   for (u = 0; u < n; ++u) {
      ptr = G[u].alist;
      while (ptr != NULL) {
         v = ptr -> nbr;
         if (v > u) {        /* A new edge is discovered */
            sprintf(H[e].name, "(%u,%u)", u, v);
            H[e].degree = 0;
            H[e].tmpdeg = 0;
            H[e].status = ACTIVE;
            H[e].color = 0;
            H[e].alist = NULL;
            ++e;
         }
         ptr = ptr -> next;
      }
   }

   /* Find the neighbors of the vertices of L(G) */
   for (e = *m-1; e > 0; --e) {
      sscanf(H[e].name, "(%u,%u)", &u, &v);
      for (f = e-1; f >= 0; --f) {
         sscanf(H[f].name, "(%u,%u)", &u1, &v1);

         /* If the e-th and f-th edges share an endpoint */
         if ((u == u1) || (u == v1) || (v == u1) || (v == v1)) {
            /* Add f to the adjacency list of e */
            ptr = H[e].alist;
            H[e].alist = (node *)malloc(sizeof(node));
            H[e].alist -> nbr = f;
            H[e].alist -> next = ptr;
            ++H[e].degree;

            /* Add e to the adjacency list of f */
            ptr = H[f].alist;
            H[f].alist = (node *)malloc(sizeof(node));
            H[f].alist -> nbr = e;
            H[f].alist -> next = ptr;
            ++H[f].degree;
         }
      }
   }

   return H;
}

/* Free dynamic memory allocated to a graph */
void freeGraph ( graph G, uint n )
{
   uint u;
   node *ptr, *q;

   for (u = 0; u < n; ++u) {
      ptr = G[u].alist;
      while (ptr != NULL) {
         q = ptr -> next;
         free(ptr); /* Node by node freeing is needed */
         ptr = q;
      }
   }
   free(G);         /* Finally free the vertex header array */
}

int main ( int argc, char *argv[] )
{
   uint n, nc, m;
   double p;
   graph G, H;

   srand((uint)time(NULL));

   if (argc >= 3) {
      n = atoi(argv[1]);
      p = atof(argv[2]);
   } else {
      printf("n = "); scanf("%u", &n);
      printf("p = "); scanf("%lf", &p);
   }

   G = genRandomGraph(n,p);
   printf("\n+++ The graph before vertex coloring\n");
   prnGraph(G,n);

   nc = color(G,n);
   printf("\nVertex coloring done\nNumber of colors used = %u\n", nc);
   printf("\n+++ The graph after vertex coloring\n");
   prnGraph(G,n);

   H = lineGraph(G,n,&m);
   printf("\n+++ The line graph before coloring\n");
   prnGraph(H,m);

   nc = color(H,m);
   printf("\nEdge coloring done\nNumber of colors used = %u\n", nc);
   printf("\n+++ The graph after edge coloring\n");
   prnGraph(H,m);

   freeGraph(G,n);
   freeGraph(H,m);

   exit(0);
}