Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.0
graph-color.cpp
Go to the documentation of this file.
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
57public:
58 const int n_v;
59 const int* e;
60 const int* c;
61 GraphColorSpec(const int n_v0, const int* e0, const int* c0)
62 : n_v(n_v0), e(e0), c(c0) {}
63};
64
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};
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
189const GraphColorSpec g1(200, g1_e, g1_c);
190
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};
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
302const GraphColorSpec g2(200, g2_e, g2_c);
304
312private:
313 const GraphColorSpec& g;
315 IntVarArray v;
317 IntVar m;
318public:
320 enum {
323 };
325 enum {
331 };
333 enum {
336 };
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:
369 INT_VAL_MIN());
370 break;
373 break;
374 case BRANCH_AFC_SIZE:
375 branch(*this, v, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
376 break;
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:
393 INT_VAL_MIN(), syms);
394 break;
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;
403 branch(*this, v, INT_VAR_ACTION_SIZE_MAX(opt.decay()),
404 INT_VAL_MIN(), syms);
405 break;
406 }
407 }
408 }
410 virtual IntVar cost(void) const {
411 return m;
412 }
415 v.update(*this, s.v);
416 m.update(*this, s.m);
417 }
419 virtual Space*
420 copy(void) {
421 return new GraphColor(*this);
422 }
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
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);
467 return 0;
468}
469
470// STATISTICS: example-any
471
int n
Number of negative literals for node type.
Parametric base-class for scripts.
Definition driver.hh:729
static void run(const Options &opt, Script *s=NULL)
Definition script.hpp:290
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition array.hpp:76
Passing integer variables.
Definition int.hh:656
Integer variable array.
Definition int.hh:763
Integer variables.
Definition int.hh:371
Options for scripts with additional size parameter
Definition driver.hh:675
Computation spaces.
Definition core.hpp:1742
Collection of symmetries.
Definition int.hh:5292
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition var.hpp:116
Graph specification
const int * e
Edges.
const int * c
Cliques.
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.
Definition test.cpp:120
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.
Definition branch.cpp:39
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVar x1)
Post propagator for .
Definition rel.cpp:68
@ IRT_EQ
Equality ( )
Definition int.hh:926
@ IRT_NQ
Disequality ( )
Definition int.hh:927
@ IRT_GQ
Greater or equal ( )
Definition int.hh:930
@ IRT_LQ
Less or equal ( )
Definition int.hh:928
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
Gecode toplevel namespace
SymmetryHandle ValueSymmetry(const IntArgs &v)
Values in v are interchangeable.
Definition ldsb.cpp:81
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.
Definition var.hpp:236
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree.
Definition var.hpp:121
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition tiebreak.hpp:80
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator for for all .
Definition distinct.cpp:46
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.
Definition var.hpp:256
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition val.hpp:55
IntVarBranch INT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl=nullptr)
Select variable with largest degree divided by domain size.
Definition var.hpp:221
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl=nullptr)
Select variable with smallest domain size.
Definition var.hpp:206
Post propagator for SetVar x
Definition set.hh:767