/* 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 ::= | 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 ::= | 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 */ #include #include 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=K) err("solution", "illegal color"); /* The following line was added in 2006 by Daniel Grund */ 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 \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; }