1 | /* COLOR, Graph Coloring Problem */ |
---|
2 | |
---|
3 | /* Written in GNU MathProg by Andrew Makhorin <mao@gnu.org> */ |
---|
4 | |
---|
5 | /* Given an undirected loopless graph G = (V, E), where V is a set of |
---|
6 | nodes, E <= V x V is a set of arcs, the Graph Coloring Problem is to |
---|
7 | find a mapping (coloring) F: V -> C, where C = {1, 2, ... } is a set |
---|
8 | of colors whose cardinality is as small as possible, such that |
---|
9 | F(i) != F(j) for every arc (i,j) in E, that is adjacent nodes must |
---|
10 | be assigned different colors. */ |
---|
11 | |
---|
12 | param n, integer, >= 2; |
---|
13 | /* number of nodes */ |
---|
14 | |
---|
15 | set V := {1..n}; |
---|
16 | /* set of nodes */ |
---|
17 | |
---|
18 | set E, within V cross V; |
---|
19 | /* set of arcs */ |
---|
20 | |
---|
21 | check{(i,j) in E}: i != j; |
---|
22 | /* there must be no loops */ |
---|
23 | |
---|
24 | /* We need to estimate an upper bound of the number of colors |C|. |
---|
25 | The number of nodes |V| can be used, however, for sparse graphs such |
---|
26 | bound is not very good. To obtain a more suitable estimation we use |
---|
27 | an easy "greedy" heuristic. Let nodes 1, ..., i-1 are already |
---|
28 | assigned some colors. To assign a color to node i we see if there is |
---|
29 | an existing color not used for coloring nodes adjacent to node i. If |
---|
30 | so, we use this color, otherwise we introduce a new color. */ |
---|
31 | |
---|
32 | set EE := setof{(i,j) in E} (i,j) union setof{(i,j) in E} (j,i); |
---|
33 | /* symmetrisized set of arcs */ |
---|
34 | |
---|
35 | param z{i in V, case in 0..1} := |
---|
36 | /* z[i,0] = color index assigned to node i |
---|
37 | z[i,1] = maximal color index used for nodes 1, 2, ..., i-1 which are |
---|
38 | adjacent to node i */ |
---|
39 | ( if case = 0 then |
---|
40 | ( /* compute z[i,0] */ |
---|
41 | min{c in 1..z[i,1]} |
---|
42 | ( if not exists{j in V: j < i and (i,j) in EE} z[j,0] = c then |
---|
43 | c |
---|
44 | else |
---|
45 | z[i,1] + 1 |
---|
46 | ) |
---|
47 | ) |
---|
48 | else |
---|
49 | ( /* compute z[i,1] */ |
---|
50 | if not exists{j in V: j < i} (i,j) in EE then |
---|
51 | 1 |
---|
52 | else |
---|
53 | max{j in V: j < i and (i,j) in EE} z[j,0] |
---|
54 | ) |
---|
55 | ); |
---|
56 | |
---|
57 | check{(i,j) in E}: z[i,0] != z[j,0]; |
---|
58 | /* check that all adjacent nodes are assigned distinct colors */ |
---|
59 | |
---|
60 | param nc := max{i in V} z[i,0]; |
---|
61 | /* number of colors used by the heuristic; obviously, it is an upper |
---|
62 | bound of the optimal solution */ |
---|
63 | |
---|
64 | display nc; |
---|
65 | |
---|
66 | var x{i in V, c in 1..nc}, binary; |
---|
67 | /* x[i,c] = 1 means that node i is assigned color c */ |
---|
68 | |
---|
69 | var u{c in 1..nc}, binary; |
---|
70 | /* u[c] = 1 means that color c is used, i.e. assigned to some node */ |
---|
71 | |
---|
72 | s.t. map{i in V}: sum{c in 1..nc} x[i,c] = 1; |
---|
73 | /* each node must be assigned exactly one color */ |
---|
74 | |
---|
75 | s.t. arc{(i,j) in E, c in 1..nc}: x[i,c] + x[j,c] <= u[c]; |
---|
76 | /* adjacent nodes cannot be assigned the same color */ |
---|
77 | |
---|
78 | minimize obj: sum{c in 1..nc} u[c]; |
---|
79 | /* objective is to minimize the number of colors used */ |
---|
80 | |
---|
81 | data; |
---|
82 | |
---|
83 | /* These data correspond to the instance myciel3.col from: |
---|
84 | http://mat.gsia.cmu.edu/COLOR/instances.html */ |
---|
85 | |
---|
86 | /* The optimal solution is 4 */ |
---|
87 | |
---|
88 | param n := 11; |
---|
89 | |
---|
90 | set E := |
---|
91 | 1 2 |
---|
92 | 1 4 |
---|
93 | 1 7 |
---|
94 | 1 9 |
---|
95 | 2 3 |
---|
96 | 2 6 |
---|
97 | 2 8 |
---|
98 | 3 5 |
---|
99 | 3 7 |
---|
100 | 3 10 |
---|
101 | 4 5 |
---|
102 | 4 6 |
---|
103 | 4 10 |
---|
104 | 5 8 |
---|
105 | 5 9 |
---|
106 | 6 11 |
---|
107 | 7 11 |
---|
108 | 8 11 |
---|
109 | 9 11 |
---|
110 | 10 11 |
---|
111 | ; |
---|
112 | |
---|
113 | end; |
---|