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,
340 g(opt.size() == 1 ?
g2 :
g1),
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++)
363 switch (opt.branching()) {
386 switch (opt.branching()) {
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");
465 opt.
parse(argc,argv);
466 Script::run<GraphColor,BAB,SizeOptions>(opt);
int n
Number of negative literals for node type.
Node * x
Pointer to corresponding Boolean expression node.
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.
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 parse(int argc, char *argv[])
Parse commandline arguments.
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf=nullptr, FloatVarValPrint vvp=nullptr)
Branch over x with variable selection vars and value selection vals.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
@ IRT_GQ
Greater or equal ( )
@ IRT_LQ
Less or equal ( )
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Gecode toplevel namespace
SymmetryHandle ValueSymmetry(const IntArgs &v)
Values in v are interchangeable.
IntVarBranch INT_VAR_AFC_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest accumulated failure count divided by domain size with decay factor d.
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree.
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
IntVarBranch INT_VAR_ACTION_SIZE_MAX(double d=1.0, BranchTbl tbl=nullptr)
Select variable with largest action divided by domain size with decay factor d.
IntValBranch INT_VAL_MIN(void)
Select smallest value.
IntVarBranch INT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree divided by domain size.
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.