41 using namespace Gecode;
62 : n_v(n_v0), e(e0),
c(c0) {}
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};
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,
173 5, 47,52,124,151,192,
175 5, 11,65,128,134,190,
180 5, 74,126,145,162,170,
181 5, 73,78,104,175,192,
182 5, 19,83,127,130,166,
185 5, 82,92,116,134,184,
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};
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,
290 5, 36,106,124,132,197,
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,
341 v(*this,g.n_v,0,g.n_v-1),
344 for (
int i = 0; g.
e[
i] != -1;
i += 2)
348 for (
int i = *
c++;
i--;
c++)
353 for (
int i =
n;
i--;
c++)
356 if (
opt.model() == MODEL_CLIQUE)
361 if (
opt.symmetry() == SYMMETRY_NONE) {
363 switch (
opt.branching()) {
371 case BRANCH_DEGREE_SIZE:
374 case BRANCH_AFC_SIZE:
377 case BRANCH_ACTION_SIZE:
386 switch (
opt.branching()) {
395 case BRANCH_DEGREE_SIZE:
398 case BRANCH_AFC_SIZE:
402 case BRANCH_ACTION_SIZE:
415 v.update(*
this, s.v);
426 os <<
"\tm = " << m << std::endl
428 for (
int i = 0;
i <
v.size();
i++) {
431 os << std::endl <<
"\t ";
433 os <<
"};" << std::endl;
451 "use maximal clique size as lower bound");
463 "use value symmetry breaking");
466 Script::run<GraphColor,BAB,SizeOptions>(
opt);
int n
Number of negative literals for node type.
Node * x
Pointer to corresponding Boolean expression node.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Parametric base-class for scripts.
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Passing integer variables.
void branching(int v)
Set default branching value.
void solutions(unsigned int n)
Set default number of solutions to search for.
void symmetry(int v)
Set default symmetry value.
void ipl(IntPropLevel i)
Set default integer propagation level.
void model(int v)
Set default model value.
Options for scripts with additional size parameter
Collection of symmetries.
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
GraphColorSpec(const int n_v0, const int *e0, const int *c0)
const int n_v
Number of nodes.
Example: Clique-based graph coloring
GraphColor(GraphColor &s)
Constructor for cloning s.
@ BRANCH_SIZE
Choose variablee with smallest size.
@ BRANCH_DEGREE_SIZE
Choose variable with largest degree/size.
@ BRANCH_DEGREE
Choose variable with largest degree.
@ BRANCH_AFC_SIZE
Choose variable with largest afc/size.
@ BRANCH_ACTION_SIZE
Choose variable with smallest size/action.
int main(int argc, char *argv[])
Main-function.
@ MODEL_NONE
No lower bound.
@ MODEL_CLIQUE
Use maximal clique size as lower bound.
virtual IntVar cost(void) const
Cost function.
@ SYMMETRY_NONE
Simple symmetry.
@ SYMMETRY_LDSB
Use LDSB for value symmetry breaking.
GraphColor(const SizeOptions &opt)
The actual model.
const GraphColorSpec g1(200, g1_e, g1_c)
First example graph.
const GraphColorSpec g2(200, g2_e, g2_c)
Second example graph.
virtual void print(std::ostream &os) const
Print the solution.
virtual Space * copy(void)
Copying during cloning.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
SymmetryHandle ValueSymmetry(const IntArgs &vs)
Values in v are interchangeable.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
@ IRT_GQ
Greater or equal ( )
@ IRT_LQ
Less or equal ( )
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
IntVarBranch INT_VAR_AFC_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
IntVarBranch INT_VAR_ACTION_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest action divided by domain size with decay factor d.
IntVarBranch INT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl)
Select variable with largest degree divided by domain size.
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode::FloatVal c(-8, 8)
Gecode::IntArgs i({1, 2, 3, 4})
LDSB< TieBreak > tiebreak("TieBreak")