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 problem solution