/*--------------------- 

Findoptimal, Version 1.1

Program for finding optimal representative in LC orbit
(in terms of number of edges and chromatic index) and 
give LC-sequence(s) producing the input graph from the 
optimal graph(s).

Uses nauty (http://cs.anu.edu.au/~bdm/nauty/) and 
very_nauty (http://keithbriggs.info/very_nauty.html).

Compiles with the following command. (Replace $(NAUDIR) 
and $(VERYNAUTYDIR) with the actual locations of nauty 
and very_nauty.)

gcc -o findoptimal -I$(NAUDIR) -I$(VERYNAUTYDIR) -DMAXN=WORDSIZE -O4 findoptimal.c $(NAUDIR)/nauty.o $(NAUDIR)/nautil.o $(NAUDIR)/naugraph.o $(NAUDIR)/gtools.o $(NAUDIR)/naututil.o $(NAUDIR)/rng.o $(NAUDIR)/gutil1.o $(NAUDIR)/gutil2.o $(VERYNAUTYDIR)vn_graph.o -lm

-- L. E. Danielsen

Version 1.0, 28 Sep. 2010:
 - First version
Version 1.1, 13 Jan. 2011:
 - Program now outputs much shorter LC sequences

---------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "vn_graph.h"
#include "gtools.h"
#include "naututil.h"
#include "gutils.h"

#define MAXVERTICES 20 // Works for graphs with up to n=20 vertices
#define BYTES 24 // (n choose 2)/8 bytes needed to store graph with up to n vertices

typedef struct treenode
{
  char value[BYTES];
  struct treenode *left;
  struct treenode *right;
} node;

typedef struct queuenode
{
  graph g[MAXN];
  char lcstring[512];
  struct queuenode *next;
} qnode;

node *root = NULL;
int nx = 0;
unsigned char gvalue[BYTES];
graph gx[MAXN];
graph gxcanon[MAXN];
graph gxedge[MAXN];
graph gxchrom[MAXN];
char lcedge[512];
char lcchrom[512];
int orbitsize;
int minedge;
int minedgechrom;
int minchrom;
int minchromedge;
char *s;
const set onemask = 0x1L << (WORDSIZE-1);


void getValue(const graph *g) {
  int i, j;
  set row;
  int byte = 0;
  int bytecount = 0;

  memset(gvalue, 0, BYTES);

  for(i=1; i<nx; i++) {
    row = (g[i-1] << i);

    for(j=0; j<(nx-i); j++) {
      bytecount++;
      if(ISELEMENT(&row,j))
        gvalue[byte] |= 0x01;
      if(bytecount == 8) {
        byte++;
        bytecount = 0;
      }
      else
        gvalue[byte] <<= 1;
    }
  }

  gvalue[byte] <<= (7-bytecount);
}


void freeTree(node **root) {
  if(*root != NULL) {
    freeTree(&((*root)->left));
    freeTree(&((*root)->right));
    free(*root);
  }
}


int addNode(node **root) {
  node *curNode, *prevNode, *newNode;
  int different;

  different = 3;
  curNode = *root;
  while (curNode != NULL) {
    different = 0;

    if(memcmp(gvalue, curNode->value, BYTES) < 0) {
      different = 1;
      prevNode = curNode;
      curNode = curNode->left;
    }
    else if(memcmp(gvalue, curNode->value, BYTES) > 0) {
      different = 2;
      prevNode = curNode;
      curNode = curNode->right;
    }
    else {
      return 0;
    }
  }

  newNode = malloc(sizeof(node));
  memcpy(newNode->value, gvalue, BYTES);
  newNode->left = NULL;
  newNode->right = NULL;

  switch (different) {
  case 1:
    curNode = newNode;
    prevNode->left = curNode;
    return(1);
    break;
  case 2:
    curNode = newNode;
    prevNode->right = curNode;
    return(1);
    break;
  case 3:
    *root = newNode;
    return(1);
    break;
  }
}


void makecanon(graph *g, graph *gcan) {
  statsblk nauty_stats;
  int lab[MAXN],ptn[MAXN],orbits[MAXN];
  static DEFAULTOPTIONS(options);
  setword workspace[50];
  options.getcanon = TRUE;

  nauty(g,lab,ptn,NULL,orbits,&options,&nauty_stats,workspace,50,1,nx,gcan);
}


void lc(const int v) {
  unsigned char w;
  const set rowv = gx[v];
  set *roww;
  set mask = onemask;

  for(w=0; w<nx; w++) {
    roww = &(gx[w]);
    if(rowv & mask) {
      (*roww) ^= rowv;
      (*roww) ^= mask;
    }
    mask >>= 1;
  }
}


int edges(graph *gx) {
  int i,j;
  int count = 0;
  set *row;

  for(i=0; i<nx-1; i++) {
    row = GRAPHROW(gx,i,1);
    for(j=i+1; j<nx; j++) {
      if(ISELEMENT(row, j))
	count++;
    }
  }
  
  return count;
}

void processgraph(char *lcstring) {
  graph_t g;
  int c, e, i;

  e = edges(gx);
  s = ntog6(gx,1,nx);
  g = geng_stringtograph(s);
  c = graph_edge_chromatic_number(g, 0);

  if( (e < minedge) || ( (e == minedge) && (c < minedgechrom) ) ) {
    minedge = e;
    minedgechrom = c;
    for(i=0; i<nx; i++)
      gxedge[i] = gx[i];
    strcpy(lcedge, lcstring);
  }

  if( (c < minchrom) || ( (c == minchrom) && (e < minchromedge) ) ) {
    minchrom = c;
    minchromedge = e;
    for(i=0; i<nx; i++)
      gxchrom[i] = gx[i]; 
    strcpy(lcchrom, lcstring);
  }
}


void orbit() {
  int v, i;
  qnode *qfirst = NULL;
  qnode *qlast = NULL;
  qnode *qnew;
  char *oldstring;
  char newstring[512];

  minedge = 1<<30;
  minedgechrom = 1<<30;
  minchrom = 1<<30;
  minchromedge = 1<<30;

  makecanon(gx,gxcanon);
  getValue(gxcanon);
  addNode(&root);
  processgraph("");
  orbitsize = 1;

  qnew = malloc(sizeof(qnode));
  for(i=0; i<nx; i++)
    qnew->g[i] = gx[i];
  sprintf(qnew->lcstring, "");
  qnew->next = NULL;
  qfirst = qnew;
  qlast = qnew;
 
  while(qfirst != NULL) {
    for(i=0; i<nx; i++)
      gx[i] = qfirst->g[i];
    oldstring = qfirst->lcstring;

    for(v=0; v<nx; v++) {
      lc(v);

      makecanon(gx,gxcanon);
      getValue(gxcanon);
      if(addNode(&root)) {
	sprintf(newstring, "%d,", v);
	strcat(newstring, oldstring);

	processgraph(newstring);
	orbitsize++;

	qnew = malloc(sizeof(qnode));
	for(i=0; i<nx; i++)
	  qnew->g[i] = gx[i];
	strcpy(qnew->lcstring, newstring);
	qnew->next = NULL;
	qlast->next = qnew;
	qlast = qnew;
      }

      lc(v);
    }
    qfirst = qfirst->next;
  }
}


void printedges(graph *g) {
  int first = 1;
  int i, j;
  set *row;
    
  for(i=0; i<(nx-1); i++) {
    row = GRAPHROW(g,i,1);
    for(j=i+1; j<nx; j++) {
      if(ISELEMENT(row, j)) {
	if(first) {
	  printf("%d-%d", i, j);
	  first = 0;
	}
	else
	  printf(",%d-%d", i, j);
      }
    }
  }
  printf("\n");
}


void edgestog6(char* line, graph* g) {
  int i;
  char *term, *endptr;
  set *row;
  int u, v;

  for(i=0; i<MAXN; i++)
    g[i] = 0;

  term = strtok(line, ",- ");

  if(!term) {
    printf("No input!\n");
    exit(-1);
  }

  while(term) {
    u = strtol(term, &endptr, 10);

    if(*endptr != '\0') {
      printf("Error in input!\n");
      exit(-1);
    }

    if(u >= MAXVERTICES) {
      printf("Error: Max number of vertices is %d!\n", MAXVERTICES);
      exit(-1);
    }

    if(u >= nx)
      nx = u+1;

    term = strtok(0, ",- ");

    if(!term) {
      printf("Error in input!\n");
      exit(-1);
    }

    v = strtol(term, &endptr, 10);

    if(*endptr != '\0') {
      printf("Error in input!\n");
      exit(-1);
    }

    if(v >= MAXVERTICES) {
      printf("Error: Max number of vertices is %d!\n", MAXVERTICES);
      exit(-1);
    }

    if(v >= nx)
      nx = v+1;

    if(u == v) {
      printf("Error: No edges from a vertex to itself allowed!\n");
      exit(-1);
    }

    row = GRAPHROW(g, u, 1);
    ADDELEMENT(row, v);
    row = GRAPHROW(g, v, 1);
    ADDELEMENT(row, u);

    term = strtok(0, ",- ");
  }
}


int graphequals(graph* g1, graph* g2) {
  int i;
  int equals = 1;

  for(i=0; i<nx; i++) {
    if(g1[i] != g2[i]) {
      equals = 0;
      break;
    }
  }

  return equals;
}


int main(int argc, char** argv) {
  char line[2048];
  time_t t0, t1;
  graph gxoriginal[MAXN];
  int i;

  printf("*****************************************************\n");
  printf("Input the edges of your graph.\n (Example: 0-1,0-2,1-2)\n (Label your vertices 0,1,...,n-1. Maxmimum number of vertices is %d.)\n", MAXVERTICES);
  printf(":>");

  fgets(line, 2048, stdin);
  line[strlen(line)-1] = '\0';
  edgestog6(line, gx);

  for(i=0; i<nx; i++)
    gxoriginal[i] = gx[i];

  printf("*****************************************************\n");
  printf("Generating LC orbit of %d-vertex graph...\n", nx);
  t0 = time(NULL);
  orbit();
  t1 = time(NULL);

  printf("*****************************************************\n");
  printf("LC orbit of size %d generated in %f minutes\n\n", orbitsize, (double) (t1 - t0)/60);

  if( (minchrom == minedgechrom) && (minedge == minchromedge) ) {
    printf("Graph with minimum number of edges (%d) and minimum chromatic index (%d):\n", minedge, minedgechrom);
    printedges(gxedge);
    if(graphequals(gxoriginal, gxedge))
      printf("(This is your original graph.)\n\n");
    else {
      printf("LC sequence that takes this graph to your graph:\n");
      lcedge[strlen(lcedge)-1] = 0;
      printf("%s\n\n", lcedge);
    }
  }
  else {
    printf("Graph with minimum number of edges (%d) (chromatic index is %d):\n", minedge, minedgechrom);
    printedges(gxedge);
    if(graphequals(gxoriginal, gxedge))
      printf("(This is your original graph.)\n\n");
    else {
      printf("LC sequence that takes this graph to your graph:\n");
      printf("%s\n\n", lcedge);
    }

    printf("Graph with minimum chromatic index (%d) (number of edges is %d):\n", minchrom, minchromedge);
    printedges(gxchrom);
    if(graphequals(gxoriginal, gxchrom))
      printf("(This is your original graph.)\n\n");
    else {
      printf("LC sequence that takes this graph to your graph:\n");
      lcchrom[strlen(lcchrom)-1] = 0;
      printf("%s\n\n", lcchrom);
    }
  }

  printf("*****************************************************\n");

  freeTree(&root);
}