/* save this file as color.txt then run: ./glpsol --math -o solution.txt color.txt */

/* COLOR, Graph Coloring Problem */

/* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */

/* Given an undirected loopless graph G = (V, E), where V is a set of
   nodes, E <= V x V is a set of arcs, the Graph Coloring Problem is to
   find a mapping (coloring) F: V -> C, where C = {1, 2, ... } is a set
   of colors whose cardinality is as small as possible, such that
   F(i) != F(j) for every arc (i,j) in E, that is adjacent nodes must
   be assigned different colors. */

param n, integer, >= 2;
/* number of nodes */

set V := {1..n};
/* set of nodes */

set E, within V cross V;
/* set of arcs */

check{(i,j) in E}: i != j;
/* there must be no loops */

/* We need to estimate an upper bound of the number of colors |C|.
   The number of nodes |V| can be used, however, for sparse graphs such
   bound is not very good. To obtain a more suitable estimation we use
   an easy "greedy" heuristic. Let nodes 1, ..., i-1 are already
   assigned some colors. To assign a color to node i we see if there is
   an existing color not used for coloring nodes adjacent to node i. If
   so, we use this color, otherwise we introduce a new color. */

set EE := setof{(i,j) in E} (i,j) union setof{(i,j) in E} (j,i);
/* symmetrisized set of arcs */

param z{i in V, case in 0..1} :=
/* z[i,0] = color index assigned to node i
   z[i,1] = maximal color index used for nodes 1, 2, ..., i-1 which are
            adjacent to node i */
(  if case = 0 then
   (  /* compute z[i,0] */
      min{c in 1..z[i,1]}
      (  if not exists{j in V: j < i and (i,j) in EE} z[j,0] = c then
            c
         else
            z[i,1] + 1
      )
   )
   else
   (  /* compute z[i,1] */
      if not exists{j in V: j < i} (i,j) in EE then
         1
      else
         max{j in V: j < i and (i,j) in EE} z[j,0]
   )
);

check{(i,j) in E}: z[i,0] != z[j,0];
/* check that all adjacent nodes are assigned distinct colors */

param nc := max{i in V} z[i,0];
/* number of colors used by the heuristic; obviously, it is an upper
   bound of the optimal solution */

display nc;

var x{i in V, c in 1..nc}, binary;
/* x[i,c] = 1 means that node i is assigned color c */

var u{c in 1..nc}, binary;
/* u[c] = 1 means that color c is used, i.e. assigned to some node */

var color{i in 1..n}, integer;

s.t. map{i in V}: sum{c in 1..nc} x[i,c] = 1;
/* each node must be assigned exactly one color */

s.t. arc{(i,j) in E, c in 1..nc}: x[i,c] + x[j,c] <= u[c];
/* adjacent nodes cannot be assigned the same color */

minimize obj: sum{c in 1..nc} u[c];
/* objective is to minimize the number of colors used */

solve;

for{i in V,c in 1..nc:x[i,c]}printf"%d %d\n",i,c;

data;

param n := 19;

set E :=
 1 3
 1 8
 1 11
 1 12
 1 16
 1 19
 2 3
 2 4
 2 6
 2 8
 2 10
 2 11
 2 12
 2 15
 2 16
 3 11
 3 12
 3 14
 3 16
 4 5
 4 9
 4 12
 4 14
 4 15
 4 16
 5 12
 6 14
 6 19
 7 18
 7 19
 8 16
 8 18
 10 14
 10 19
 11 19
 12 13
 12 15
 12 17
 12 18
 13 19
 14 18
 14 19
 16 19
;

end;