this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.org>
5 *
6 * Contributing authors:
7 * Stefano Gualandi <stefano.gualandi@gmail.com>
8 *
9 * Copyright:
10 * Christian Schulte, 2004
11 * Stefano Gualandi, 2013
12 *
13 * This file is part of Gecode, the generic constraint
14 * development environment:
15 * http://www.gecode.org
16 *
17 * Permission is hereby granted, free of charge, to any person obtaining
18 * a copy of this software and associated documentation files (the
19 * "Software"), to deal in the Software without restriction, including
20 * without limitation the rights to use, copy, modify, merge, publish,
21 * distribute, sublicense, and/or sell copies of the Software, and to
22 * permit persons to whom the Software is furnished to do so, subject to
23 * the following conditions:
24 *
25 * The above copyright notice and this permission notice shall be
26 * included in all copies or substantial portions of the Software.
27 *
28 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35 *
36 */
37
38#include <gecode/driver.hh>
39#include <gecode/int.hh>
40
41using namespace Gecode;
42
43/**
44 * \name %Graph specification for graph coloring
45 *
46 * The edges are described by an array of integers with even number
47 * of elements, terminated by the elements -1,-1.
48 * The cliques are described by an array of integers, where the first
49 * integer gives the size of the clique, the following elements are
50 * nodes for each clique. The cliques are terminated by -1 for clique size
51 *
52 * \relates GraphColor
53 */
54//@{
55/// %Graph specification
56class GraphColorSpec {
57public:
58 const int n_v; ///< Number of nodes
59 const int* e; ///< Edges
60 const int* c; ///< Cliques
61 GraphColorSpec(const int n_v0, const int* e0, const int* c0)
62 : n_v(n_v0), e(e0), c(c0) {}
63};
64
65/// First example graph: edges
66const int g1_e[] = {
67 160,184, 192,199, 0,129, 20,80, 8,29, 93,171,
68 101,165, 124,193, 2,100, 66,173, 151,191, 164,187,
69 3,130, 118,176, 121,184, 25,106, 159,193, 121,123,
70 5,62, 97,101, 6,143, 123,163, 19,125, 17,108,
71 122,168, 181,184, 25,41, 62,70, 29,103, 48,67,
72 46,160, 79,170, 143,152, 38,184, 2,40, 191,195,
73 7,196, 62,199, 76,141, 82,166, 36,80, 51,189,
74 13,97, 3,192, 90,180, 47,176, 13,172, 92,121,
75 50,64, 65,113, 108,123, 26,106, 34,153, 90,123,
76 34,39, 116,178, 22,179, 50,61, 84,105, 84,93,
77 19,108, 29,59, 63,185, 119,129, 50,177, 80,194,
78 13,36, 46,56, 38,144, 82,193, 72,93, 49,95,
79 42,155, 117,140, 109,189, 19,35, 31,125, 118,191,
80 163,169, 40,167, 91,127, 3,121, 124,149, 40,174,
81 30,175, 19,132, 18,165, 34,93, 37,63, 10,55,
82 88,95, 76,122, 7,91, 25,141, 29,173, 139,173,
83 8,130, 110,158, 81,174, 113,114, 95,182, 136,149,
84 5,199, 56,106, 36,120, 133,187, 111,172, 19,34,
85 96,197, 32,108, 27,63, 50,188, 20,116, 50,118,
86 10,50, 24,172, 86,138, 35,50, 141,153, 98,132,
87 70,143, 1,97, 8,160, 37,170, 4,73, 1,94,
88 88,146, 59,61, 104,156, 62,172, 117,139, 66,189,
89 33,134, 122,169, 95,163, 95,152, 83,140, 110,189,
90 147,159, 22,147, 59,173, 30,41, 33,183, 181,187,
91 88,105, 93,151, 6,130, 24,30, 84,130, 72,120,
92 118,159, 147,189, 122,149, 24,175, 39,169, 164,186,
93 93,187, 13,156, 119,176, 73,91, 174,178, 71,198,
94 10,134, 30,101, 79,93, 180,187, 1,50, 51,59,
95 18,169, 73,153, 1,198, 137,154, 61,106, 80,113,
96 48,142, 100,111, 97,133, 82,97, 136,170, 53,134,
97 65,177, 7,80, 73,137, 6,70, 115,166, 72,196,
98 40,109, 91,101, 2,177, 120,185, 55,65, 72,166,
99 104,165, 173,187, 54,71, 3,61, 52,56, 120,149,
100 64,72, 42,43, 75,185, 62,68, 108,147, 30,111,
101 25,58, 39,93, 75,117, 61,194, 140,153, 80,121,
102 93,102, 9,177, 7,163, 17,70, 5,168, 63,178,
103 74,160, 148,158, 9,84, 30,76, 63,80, 68,99,
104 20,152, 7,182, 7,22, 71,134, 32,100, 107,164,
105 23,62, 5,98, 130,192, 65,144, 139,161, 24,124,
106 31,47, 29,140, 61,153, 53,109, 20,26, 143,160,
107 47,195, 171,172, 185,193, 128,173, 38,96, 14,171,
108 176,199, 111,139, 21,54, 80,171, 116,185, 184,199,
109 37,88, 62,133, 3,150, 48,109, 46,176, 24,178,
110 59,172, 180,198, 64,109, 110,111, 101,146, 66,164,
111 5,117, 144,179, 71,126, 166,169, 107,151, 46,85,
112 106,139, 27,153, 97,148, 68,185, 17,179, 10,142,
113 168,169, 4,46, 113,152, 52,176, 6,38, 22,48,
114 20,120, 2,84, 71,85, 91,116, 0,189, 116,197,
115 142,147, 33,165, 86,198, 146,149, 152,187, 44,62,
116 48,175, 56,150, 63,161, 71,164, 17,171, 19,66, -1,-1};
117/// First example graph: cliques
118const int g1_c[] = {
119 30, 6,11,14,25,40,42,48,53,61,76,80,87,89,92,108,115,120,131,132,137,145,159,162,163,164,168,172,173,176,182,
120 30, 3,15,16,31,34,35,37,38,49,58,67,78,86,91,100,110,114,123,129,132,133,140,143,154,167,168,174,175,193,197,
121 25, 3,10,33,38,43,45,48,51,65,66,82,88,90,93,94,103,107,128,131,141,152,155,168,185,199,
122 25, 0,4,7,26,28,33,36,58,61,72,79,81,90,99,105,114,115,124,135,152,159,161,173,181,192,
123 25, 12,15,28,39,43,44,45,66,83,84,85,99,102,108,112,115,120,126,131,152,157,163,171,182,183,
124 25, 13,14,15,38,55,66,76,78,87,91,95,99,109,110,125,130,134,137,148,153,159,169,181,185,195,
125 25, 3,4,31,35,41,42,57,60,65,66,72,74,84,86,90,91,94,96,110,139,140,141,165,179,199,
126 25, 0,4,5,9,28,31,42,49,54,63,65,72,74,75,76,82,91,99,107,109,140,147,154,169,182,
127 25, 4,5,10,17,41,43,48,58,65,85,92,97,107,112,114,129,131,146,150,153,158,169,176,184,191,
128 25, 4,8,15,16,20,21,37,55,68,84,87,104,109,112,117,119,122,123,126,133,142,164,167,180,195,
129 25, 5,6,10,11,28,30,43,46,53,60,66,79,82,105,114,116,119,124,127,147,157,171,184,195,196,
130 20, 15,16,30,35,36,56,66,78,81,84,99,126,128,129,138,151,152,153,166,190,
131 20, 5,21,23,29,39,40,49,69,88,114,122,127,128,142,148,155,161,171,188,190,
132 20, 0,3,15,23,31,41,57,60,69,76,89,107,109,128,153,155,161,169,174,183,
133 20, 9,33,43,61,64,69,85,98,100,101,114,120,138,144,172,182,184,187,188,198,
134 20, 4,6,8,10,23,27,45,57,66,68,71,93,110,122,139,146,150,155,156,188,
135 20, 4,14,18,22,63,77,78,83,94,98,104,114,150,166,172,177,183,186,196,199,
136 20, 22,35,46,47,63,64,70,78,87,99,102,112,116,119,125,131,152,165,174,186,
137 20, 1,3,13,15,19,26,46,51,65,73,76,110,114,149,152,163,166,170,178,186,
138 20, 9,29,33,40,50,54,102,105,111,112,119,120,124,128,136,138,144,175,190,199,
139 20, 39,75,79,102,106,112,123,125,138,145,154,155,159,162,165,168,175,181,189,196,
140 20, 0,11,12,23,42,63,68,71,79,83,89,98,113,117,121,141,156,176,177,193,
141 20, 10,17,31,56,77,89,102,115,116,117,118,120,136,157,163,168,172,182,193,196,
142 20, 9,34,35,43,44,57,60,64,79,87,88,94,103,133,156,157,166,171,174,189,
143 20, 13,21,22,31,41,45,66,67,79,86,112,116,119,146,160,171,175,181,192,195,
144 20, 11,24,26,45,57,91,99,102,122,123,135,141,144,146,154,156,167,191,194,199,
145 15, 17,44,53,61,82,90,95,103,107,122,124,145,169,186,190,
146 15, 2,14,26,37,58,61,75,95,103,109,115,116,141,154,199,
147 15, 5,13,21,28,61,64,65,73,105,115,119,132,148,154,185,
148 15, 10,20,38,45,61,75,109,111,115,143,150,157,163,179,186,
149 15, 9,45,48,49,51,52,57,64,70,128,158,163,182,183,192,
150 15, 47,55,57,64,79,80,105,131,152,163,172,180,186,190,197,
151 15, 16,36,69,84,99,113,118,121,126,137,160,162,165,177,196,
152 15, 16,44,50,53,54,65,69,80,96,112,125,139,150,153,193,
153 15, 6,54,72,76,86,95,96,144,145,148,151,164,168,180,183,
154 15, 10,18,19,37,65,85,90,104,112,128,147,158,164,192,198,
155 15, 20,21,36,50,53,74,90,96,99,124,129,140,163,171,183,
156 15, 13,20,27,53,65,77,86,98,110,125,133,139,147,188,196,
157 15, 23,41,43,49,58,74,77,86,111,126,150,168,173,185,189,
158 15, 11,35,62,89,125,132,134,141,149,163,166,167,171,194,196,
159 15, 14,28,30,52,114,115,122,125,132,135,172,177,179,181,195,
160 15, 0,8,9,20,23,53,77,93,121,136,141,147,150,191,199,
161 15, 3,21,47,49,91,102,106,113,124,136,140,143,177,178,194,
162 15, 44,46,52,53,68,82,89,90,120,128,144,147,175,178,192,
163 15, 8,16,19,21,67,72,79,82,86,90,115,116,149,152,199,
164 15, 12,30,78,80,97,120,122,123,143,146,151,165,173,177,178,
165 15, 9,19,39,46,91,109,128,130,131,146,148,150,178,185,198,
166 10, 29,44,69,74,96,115,122,126,189,199,
167 10, 22,42,52,53,97,113,146,151,160,195,
168 10, 19,20,32,77,81,133,134,138,147,177,
169 10, 0,4,56,59,107,109,144,149,158,167,
170 10, 6,69,99,104,110,114,118,134,152,172,
171 5, 25,76,126,140,143,
172 5, 4,54,67,116,142,
173 5, 47,52,124,151,192,
174 5, 32,55,61,64,73,
175 5, 11,65,128,134,190,
176 5, 45,48,63,131,139,
177 5, 34,55,82,108,151,
178 5, 24,34,54,112,156,
179 5, 12,47,72,148,163,
180 5, 74,126,145,162,170,
181 5, 73,78,104,175,192,
182 5, 19,83,127,130,166,
183 5, 20,90,98,137,165,
184 5, 22,24,29,49,132,
185 5, 82,92,116,134,184,
186 -1};
187
188/// First example graph
189const GraphColorSpec g1(200, g1_e, g1_c);
190
191/// Second example graph: edges
192const int g2_e[] = {
193 63,97, 67,85, 18,180, 2,143, 55,156, 28,105,
194 37,196, 26,33, 88,199, 175,179, 45,46, 62,70,
195 53,58, 49,177, 91,178, 52,129, 147,165, 83,95,
196 68,172, 66,150, 7,112, 71,92, 97,150, 114,116,
197 56,86, 154,188, 95,97, 159,199, 68,119, 11,81,
198 79,116, 64,74, 88,89, 99,114, 70,73, 87,162,
199 24,119, 9,25, 174,188, 11,80, 47,198, 86,145,
200 7,70, 37,170, 138,180, 66,199, 98,153, 70,142,
201 84,196, 78,185, 7,131, 54,76, 69,82, 53,166,
202 25,178, 3,36, 128,197, 59,96, 122,137, 54,124,
203 157,162, 3,146, 72,198, 2,94, 137,158, 64,131,
204 2,79, 18,119, 22,38, 92,136, 7,108, 179,194,
205 68,166, 10,84, 28,192, 103,104, 28,75, 8,43,
206 153,164, 59,119, 88,177, 36,70, 59,154, 57,75,
207 109,174, 155,184, 16,74, 99,148, 77,121, 54,177,
208 38,172, 138,174, 7,16, 28,146, 18,192, 4,154,
209 17,31, 56,57, 174,177, 81,122, 101,175, 21,155,
210 48,96, 124,154, 129,130, 58,169, 19,57, 115,165,
211 40,117, 34,181, 28,32, 32,176, 19,119, 20,93,
212 137,172, 55,135, 92,95, 34,51, 5,81, 63,118,
213 72,94, 157,181, 15,68, 41,90, 35,73, 159,183,
214 115,128, 28,183, 34,45, 149,177, 74,137, 51,110,
215 25,170, 43,123, 53,109, 4,26, 68,80, 53,171,
216 48,159, 0,28, 67,176, 87,163, 75,165, 137,162,
217 150,199, 57,153, 32,93, 25,92, 13,88, 115,167,
218 16,192, 113,157, 90,125, 104,188, 148,171, 96,101,
219 22,68, 25,62, 89,161, 24,158, 66,190, 31,34,
220 106,133, 51,102, 146,163, 31,154, 56,129, 66,157,
221 38,93, 73,166, 117,174, 93,161, 3,95, 86,181,
222 131,139, 5,182, 30,66, 0,11, 88,107, 54,101,
223 36,66, 25,176, 8,38, 31,177, 78,195, 122,179,
224 42,60, 83,112, 149,161, 184,188, 65,126, 74,198,
225 38,80, 135,172, 43,156, 148,151, 135,195, 111,184,
226 10,14, 97,152, -1,-1};
227/// Second example graph: cliques
228const int g2_c[] = {
229 30, 10,11,17,20,24,29,33,40,45,50,51,76,77,85,88,101,114,120,122,127,129,136,144,147,148,157,169,180,184,193,
230 30, 0,2,14,21,38,40,44,51,72,82,91,99,106,109,119,123,126,136,141,154,157,161,163,165,166,171,175,182,183,196,
231 30, 2,17,20,30,35,36,37,39,46,56,61,72,75,77,80,84,85,96,97,100,107,112,123,156,160,163,175,181,182,195,
232 25, 11,19,36,41,44,59,60,73,74,89,93,94,108,109,113,130,132,153,163,167,182,186,193,196,199,
233 25, 2,11,25,30,31,41,49,51,52,53,85,86,93,101,105,108,111,130,135,144,150,183,185,191,194,
234 25, 1,6,9,11,12,13,19,21,33,49,51,77,124,128,130,131,140,146,147,161,171,180,181,185,198,
235 25, 3,5,31,39,42,57,59,61,90,93,98,102,106,121,129,132,140,160,165,166,168,185,187,193,194,
236 25, 9,12,16,23,33,41,44,61,68,73,85,93,96,113,118,122,125,127,129,133,139,146,181,186,199,
237 25, 6,23,35,42,45,57,65,67,70,77,80,96,100,105,114,119,129,145,146,152,157,160,166,190,195,
238 25, 8,18,19,27,36,40,49,52,60,65,75,84,85,96,97,107,109,110,120,122,132,154,155,172,189,
239 25, 1,25,27,37,39,45,56,61,69,70,80,87,89,102,111,115,120,126,134,146,156,169,173,175,192,
240 20, 8,14,20,21,32,39,50,55,88,91,102,120,126,142,159,165,171,175,184,186,
241 20, 10,15,35,43,50,52,60,77,80,81,85,87,106,120,145,151,155,159,176,196,
242 20, 10,17,20,33,46,55,60,68,95,96,103,112,117,118,120,123,127,141,147,179,
243 20, 9,34,41,52,56,72,73,100,102,116,124,131,138,155,157,158,172,173,182,183,
244 20, 0,14,16,27,29,44,70,95,101,104,115,127,140,158,161,168,170,173,181,189,
245 20, 6,14,17,18,23,27,50,51,83,84,93,107,108,116,122,136,154,159,172,185,
246 20, 11,16,17,21,32,38,45,49,55,56,84,88,102,123,126,133,173,189,195,198,
247 20, 0,14,21,29,30,40,63,67,93,98,116,122,131,140,150,152,174,178,183,190,
248 20, 8,14,28,36,44,65,72,79,84,111,114,124,130,134,140,158,182,185,193,197,
249 20, 9,10,12,17,28,42,46,50,57,62,90,117,132,149,168,176,178,182,187,188,
250 20, 2,4,22,27,31,32,65,74,108,117,132,142,153,159,160,178,180,187,192,195,
251 20, 2,4,7,21,56,64,67,100,103,130,135,140,147,151,156,161,167,191,193,196,
252 20, 6,18,24,30,50,51,67,82,84,88,93,95,106,113,138,146,168,187,190,198,
253 20, 28,37,44,98,99,107,112,119,129,132,135,151,156,167,168,179,182,190,198,199,
254 15, 4,37,61,64,67,77,93,103,105,118,136,159,169,177,193,
255 15, 17,44,53,61,82,90,95,103,107,122,124,145,169,186,190,
256 15, 21,54,80,100,110,120,126,127,132,142,149,150,162,181,186,
257 15, 3,7,21,22,40,41,82,94,96,98,126,140,143,147,152,
258 15, 4,14,58,66,80,100,107,111,126,133,140,141,148,155,167,
259 15, 31,38,44,48,59,74,75,77,100,105,139,168,171,182,187,
260 15, 0,5,55,62,66,67,74,84,92,128,160,163,188,189,195,
261 15, 0,36,55,73,80,96,121,133,167,173,190,191,193,195,198,
262 15, 21,33,41,43,52,62,69,77,88,110,114,118,139,142,187,
263 15, 12,14,23,29,44,58,67,74,124,149,150,156,167,171,183,
264 15, 22,33,36,48,60,63,90,92,107,108,137,140,144,165,193,
265 15, 11,24,40,45,49,59,72,123,125,132,151,161,167,179,184,
266 15, 4,19,20,48,61,76,98,106,136,147,155,177,183,191,192,
267 15, 17,22,28,35,55,74,86,90,98,106,121,138,168,190,195,
268 15, 24,30,35,44,55,63,80,120,128,130,148,160,163,166,192,
269 15, 20,30,59,64,69,94,104,106,139,140,144,147,156,161,199,
270 15, 13,30,38,49,54,61,86,95,103,105,131,148,156,162,180,
271 15, 2,25,34,41,46,63,69,81,91,113,139,159,186,188,190,
272 15, 1,6,14,35,47,50,66,81,90,136,137,152,156,168,195,
273 15, 34,37,47,52,94,100,104,105,107,131,147,171,186,191,192,
274 15, 9,14,29,37,109,125,137,142,145,147,151,159,167,178,192,
275 15, 13,45,60,62,78,99,104,118,142,143,156,179,189,191,197,
276 15, 3,15,23,33,66,71,82,89,99,110,113,135,143,158,171,
277 15, 27,39,101,102,118,133,134,138,141,144,145,148,165,169,189,
278 15, 12,18,20,36,50,51,53,76,86,120,141,176,178,186,198,
279 10, 6,8,17,77,109,112,115,124,129,193,
280 10, 21,31,51,58,86,112,117,126,127,143,
281 10, 10,74,87,108,123,134,157,180,186,190,
282 10, 13,14,15,44,67,118,133,142,146,193,
283 10, 40,44,46,66,73,128,141,161,174,192,
284 5, 25,117,163,165,192,
285 5, 40,46,105,121,134,
286 5, 3,12,56,90,126,
287 5, 13,95,98,120,188,
288 5, 3,98,111,128,194,
289 5, 4,21,51,65,73,
290 5, 36,106,124,132,197,
291 5, 5,35,57,91,144,
292 5, 0,19,122,177,190,
293 5, 85,98,111,113,134,
294 5, 49,85,107,139,149,
295 5, 54,88,102,111,172,
296 5, 41,74,115,170,184,
297 5, 33,70,123,151,159,
298 5, 50,82,117,123,163,
299 -1};
300
301/// Second example graph
302const GraphColorSpec g2(200, g2_e, g2_c);
303//@}
304
305/**
306 * \brief %Example: Clique-based graph coloring
307 *
308 * \ingroup Example
309 *
310 */
311class GraphColor : public IntMinimizeScript {
312private:
313 const GraphColorSpec& g;
314 /// Color of nodes
315 IntVarArray v;
316 /// Number of colors
317 IntVar m;
318public:
319 /// Model variants
320 enum {
321 MODEL_NONE, ///< No lower bound
322 MODEL_CLIQUE ///< Use maximal clique size as lower bound
323 };
324 /// Branching to use for model
325 enum {
326 BRANCH_DEGREE, ///< Choose variable with largest degree
327 BRANCH_SIZE, ///< Choose variablee with smallest size
328 BRANCH_DEGREE_SIZE, ///< Choose variable with largest degree/size
329 BRANCH_AFC_SIZE, ///< Choose variable with largest afc/size
330 BRANCH_ACTION_SIZE ///< Choose variable with smallest size/action
331 };
332 /// Symmetry variants
333 enum {
334 SYMMETRY_NONE, ///< Simple symmetry
335 SYMMETRY_LDSB ///< Use LDSB for value symmetry breaking
336 };
337 /// The actual model
338 GraphColor(const SizeOptions& opt)
339 : IntMinimizeScript(opt),
340 g(opt.size() == 1 ? g2 : g1),
341 v(*this,g.n_v,0,g.n_v-1),
342 m(*this,0,g.n_v-1) {
343 rel(*this, v, IRT_LQ, m);
344 for (int i = 0; g.e[i] != -1; i += 2)
345 rel(*this, v[g.e[i]], IRT_NQ, v[g.e[i+1]]);
346
347 const int* c = g.c;
348 for (int i = *c++; i--; c++)
349 rel(*this, v[*c], IRT_EQ, i);
350 while (*c != -1) {
351 int n = *c;
352 IntVarArgs x(n); c++;
353 for (int i = n; i--; c++)
354 x[i] = v[*c];
355 distinct(*this, x, opt.ipl());
356 if (opt.model() == MODEL_CLIQUE)
357 rel(*this, m, IRT_GQ, n-1);
358 }
359 // Branching on the number of colors
360 branch(*this, m, INT_VAL_MIN());
361 if (opt.symmetry() == SYMMETRY_NONE) {
362 // Branching without symmetry breaking
363 switch (opt.branching()) {
364 case BRANCH_SIZE:
365 branch(*this, v, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
366 break;
367 case BRANCH_DEGREE:
368 branch(*this, v, tiebreak(INT_VAR_DEGREE_MAX(),INT_VAR_SIZE_MIN()),
369 INT_VAL_MIN());
370 break;
371 case BRANCH_DEGREE_SIZE:
372 branch(*this, v, INT_VAR_DEGREE_SIZE_MAX(), INT_VAL_MIN());
373 break;
374 case BRANCH_AFC_SIZE:
375 branch(*this, v, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
376 break;
377 case BRANCH_ACTION_SIZE:
378 branch(*this, v, INT_VAR_ACTION_SIZE_MAX(opt.decay()), INT_VAL_MIN());
379 break;
380 }
381 } else { // opt.symmetry() == SYMMETRY_LDSB
382 // Branching while considering value symmetry breaking
383 // (every permutation of color values gives equivalent solutions)
384 Symmetries syms;
385 syms << ValueSymmetry(IntArgs::create(g.n_v,0));
386 switch (opt.branching()) {
387 case BRANCH_SIZE:
388 branch(*this, v, INT_VAR_SIZE_MIN(), INT_VAL_MIN(), syms);
389 break;
390 case BRANCH_DEGREE:
391 branch(*this, v, tiebreak(INT_VAR_DEGREE_MAX(),
392 INT_VAR_SIZE_MIN()),
393 INT_VAL_MIN(), syms);
394 break;
395 case BRANCH_DEGREE_SIZE:
396 branch(*this, v, INT_VAR_DEGREE_SIZE_MAX(), INT_VAL_MIN(), syms);
397 break;
398 case BRANCH_AFC_SIZE:
399 branch(*this, v, INT_VAR_AFC_SIZE_MAX(opt.decay()),
400 INT_VAL_MIN(), syms);
401 break;
402 case BRANCH_ACTION_SIZE:
403 branch(*this, v, INT_VAR_ACTION_SIZE_MAX(opt.decay()),
404 INT_VAL_MIN(), syms);
405 break;
406 }
407 }
408 }
409 /// Cost function
410 virtual IntVar cost(void) const {
411 return m;
412 }
413 /// Constructor for cloning \a s
414 GraphColor(GraphColor& s) : IntMinimizeScript(s), g(s.g) {
415 v.update(*this, s.v);
416 m.update(*this, s.m);
417 }
418 /// Copying during cloning
419 virtual Space*
420 copy(void) {
421 return new GraphColor(*this);
422 }
423 /// Print the solution
424 virtual void
425 print(std::ostream& os) const {
426 os << "\tm = " << m << std::endl
427 << "\tv[] = {";
428 for (int i = 0; i < v.size(); i++) {
429 os << v[i] << ", ";
430 if ((i+1) % 15 == 0)
431 os << std::endl << "\t ";
432 }
433 os << "};" << std::endl;
434 }
435};
436
437
438/** \brief Main-function
439 * \relates GraphColor
440 */
441int
442main(int argc, char* argv[]) {
443 SizeOptions opt("GraphColor");
444 opt.ipl(IPL_DOM);
445 opt.solutions(0);
446
447 opt.model(GraphColor::MODEL_NONE);
448 opt.model(GraphColor::MODEL_NONE, "none",
449 "no lower bound");
450 opt.model(GraphColor::MODEL_CLIQUE, "clique",
451 "use maximal clique size as lower bound");
452
453 opt.branching(GraphColor::BRANCH_DEGREE);
454 opt.branching(GraphColor::BRANCH_DEGREE, "degree");
455 opt.branching(GraphColor::BRANCH_SIZE, "size");
456 opt.branching(GraphColor::BRANCH_DEGREE_SIZE, "degree-size");
457 opt.branching(GraphColor::BRANCH_AFC_SIZE, "afc-size");
458 opt.branching(GraphColor::BRANCH_ACTION_SIZE, "action-size");
459
460 opt.symmetry(GraphColor::SYMMETRY_NONE);
461 opt.symmetry(GraphColor::SYMMETRY_NONE, "none");
462 opt.symmetry(GraphColor::SYMMETRY_LDSB, "ldsb",
463 "use value symmetry breaking");
464
465 opt.parse(argc,argv);
466 Script::run<GraphColor,BAB,SizeOptions>(opt);
467 return 0;
468}
469
470// STATISTICS: example-any
471