/*  SOLUTION CHECKER FOR OPTIMAL REGISTER COALESCING.
    Copyright (c) 2000  Andrew W. Appel and Lal George.

  The problem of optimal register coalescing is this:  Given an
  interference graph of N nodes, each of degree less than K,
  and a set of additional weighted pairs of the form (I,J,W),
  where I and J are nodes and W is a weight
  find a K-coloring of the graph that minimizes the sum of the weights
  of pairs (I,J) such that color[I] != color[J].
  
  Format of problem file is as follows.  Every capital letter stands for
  an integer literal.

  problem ::= N K edges
  edges ::= <empty>
          | interference-edge  edges
          | coalesce-edge  edges
  interference-edge ::= I J -1
  coalesce-edge ::= I J W

  Where  N >= 0,  K > 0, 
   and for each I,J,  0 <= I < N, 0 <= J < N,  and each W >= 0.

  For each node I such that I >= K, the degree of node I must be less than
  K.  That is, the first K nodes may have arbitrarily high degree,
  but the rest must have low degree: for a given I, if I >= K,
  the number of interference edges of the form   I Y -1  or   X I -1
  must be less than K.  There may be arbitrarily many coalesce edges
  that mention I.    (A K-coloring must trivially exist in a graph of 
  max degree K-1.)

  Format of solution file is as follows:

  solution ::= N K colors
  colors ::= <empty>
          |  C colors

  where the number of C values is N, and for each C,  0 <= C < K.

  In both the problem file and the solution file, a comment starts
  with the % character and ends with a newline, and is ignored.

  A solution is legal if for each interference (I,J,-1), 
  color[I]!=color[J].

  The cost of a solution is the sum of the weights W for 
  all coalesce-edges (I,J,W) such that color[I]!=color[J].

  The optimum solution is the minimum-cost legal solution.

  This "check" program evaluates the cost of a solution.
  Usage:  check <problem> <solution>

*/


#include <stdio.h>
#include <ctype.h>

int N;
int K;

int *color;
int *degree;

void err(char *s, char *e) {
  fprintf(stderr, "Error in format of %s file: %s\n.", s, e);
  exit(1);
}

void err2(char *s) {
  fprintf(stderr, "Erroneous solution: %s\n.", s);
  exit(1);
}

void comment(FILE *f) {
  int c;
  c = getc(f);
  for (;;) {
    if (isspace(c)) {c = getc(f);}
    else if (c=='%')
      while (c!=EOF && c!='\n') {c = getc(f);}
    else break;
  }
  if (c!=EOF) ungetc(c,f);
}
  

int scan(FILE *f, int *p) {
  int i,j;
  comment(f);
  return fscanf(f, "%d", p);
}

void read_solution(FILE *f) {
  int i;
  if (scan(f,&N) != 1)  err("solution","no numbers");
  if (N<0)  err("solution","negative N");
  if (scan(f,&K) != 1)  err("solution", "no K");
  color= (int*) malloc(N * sizeof(int));
  degree= (int*) malloc(N * sizeof(int));
  if (!color || !degree) err("solution","not enough memory, N too large");
  for (i=0;i<N;i++) {
    degree[i]=0;
    if (scan(f,&color[i]) != 1)  err("solution", "not enough nodes");
    if (color[i]<0 || color[i] >=K) err("solution", "illegal color");
    /* The following line was added in 2006 by Daniel Grund */
    if (i<K && color[i] != i) err2("Precolored node has wrong color"); 
    }
  if (scan(f,&i) ==1) err("solution","too many nodes");
}
          
incdegree(int i) {
  degree[i]++;
  if (i >= K && degree[i] >= K)
      fprintf(stderr, "Warning: node %d has high degree; graph may not be colorable.\n");
}

void check_solution(FILE *f) {
  int i,j,w, cost=0, z;
  if (scan(f,&i) != 1)  err("problem","no numbers");
  if (i!=N) err2("N in solution doesn't match N in problem");
  if (scan(f,&i) != 1)  err("problem","no K");
  if (i!=K) err2("K in solution doesn't match K in problem");
  for (;;) {
    z=scan(f,&i);
    if (z<1) break;
    z+=scan(f,&j);
    z+=scan(f,&w);
    if (z!=3) err("problem","incomplete triple");
    if (w<0) {
      incdegree(i);  incdegree(j);
      if (color[i]==color[j]) {
	fprintf(stderr,"Interference error, nodes %d and %d\n", i, j);
        exit(1);
      }
    }
    else if (color[i]!=color[j]) cost+=w;
  }
  printf("Cost = %d\n", cost);
}

main(int argc, char **argv) {
  FILE *problem, *solution;
  if (argc!=3) {
    fprintf(stderr,"Usage: check <problem> <solution>\n");
    exit(1);
  }
  problem = fopen(argv[1],"r");
  if (!problem) {
    fprintf(stderr,"Cannot open %s\n",argv[1]);
    exit(1);
  }
  solution = fopen(argv[2],"r");
  if (!solution) {
    fprintf(stderr,"Cannot open %s\n",argv[1]);
    exit(1);
  }
  read_solution(solution);
  check_solution(problem);
  return 0;
}