/* 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;
}