Generated on Sun Aug 9 2020 05:34:08 for Gecode by doxygen 1.8.18
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 
41 using namespace Gecode;
42 
55 class GraphColorSpec {
57 public:
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 
66 const 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};
118 const 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 
189 const GraphColorSpec g1(200, g1_e, g1_c);
190 
192 const 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};
228 const 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 
302 const GraphColorSpec g2(200, g2_e, g2_c);
304 
312 private:
313  const GraphColorSpec& g;
315  IntVarArray v;
317  IntVar m;
318 public:
320  enum {
322  MODEL_CLIQUE
323  };
325  enum {
330  BRANCH_ACTION_SIZE
331  };
333  enum {
335  SYMMETRY_LDSB
336  };
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;
371  case BRANCH_DEGREE_SIZE:
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:
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  }
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 
441 int
442 main(int argc, char* argv[]) {
443  SizeOptions opt("GraphColor");
444  opt.ipl(IPL_DOM);
445  opt.solutions(0);
446 
449  "no lower bound");
451  "use maximal clique size as lower bound");
452 
459 
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 
GraphColor(const SizeOptions &opt)
The actual model.
@ BRANCH_DEGREE
Choose variable with largest degree.
Post propagator for SetVar x
Definition: set.hh:767
const int * e
Edges.
Definition: graph-color.cpp:59
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition: array.hpp:76
virtual void print(std::ostream &os) const
Print the solution.
@ IRT_GQ
Greater or equal ( )
Definition: int.hh:930
Passing integer variables.
Definition: int.hh:656
unsigned int size(I &i)
Size of all ranges of range iterator i.
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Definition: tiebreak.hpp:80
@ MODEL_NONE
No lower bound.
void ipl(IntPropLevel i)
Set default integer propagation level.
Definition: options.hpp:216
Computation spaces.
Definition: core.hpp:1742
void branch(Home home, const FloatVarArgs &x, FloatVarBranch vars, FloatValBranch vals, FloatBranchFilter bf, FloatVarValPrint vvp)
Branch over x with variable selection vars and value selection vals.
Definition: branch.cpp:39
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:55
Integer variable array.
Definition: int.hh:763
const int * c
Cliques.
Definition: graph-color.cpp:60
@ BRANCH_ACTION_SIZE
Choose variable with smallest size/action.
virtual IntVar cost(void) const
Cost function.
Collection of symmetries.
Definition: int.hh:5292
Gecode toplevel namespace
GraphColor(GraphColor &s)
Constructor for cloning s.
virtual Space * copy(void)
Copying during cloning.
Options opt
The options.
Definition: test.cpp:97
@ MODEL_CLIQUE
Use maximal clique size as lower bound.
Parametric base-class for scripts.
Definition: driver.hh:729
void branching(int v)
Set default branching value.
Definition: options.hpp:225
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:979
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:548
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:121
Integer variables.
Definition: int.hh:371
@ BRANCH_SIZE
Choose variablee with smallest size.
IntVarBranch INT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl)
Select variable with largest degree divided by domain size.
Definition: var.hpp:221
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:206
const int v[7]
Definition: distinct.cpp:259
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:43
@ SYMMETRY_LDSB
Use LDSB for value symmetry breaking.
Graph specification
Definition: graph-color.cpp:56
int main(int argc, char *argv[])
Main-function.
Example: Clique-based graph coloring
SymmetryHandle ValueSymmetry(const IntArgs &vs)
Values in v are interchangeable.
Definition: ldsb.cpp:81
@ SYMMETRY_NONE
Simple symmetry.
GraphColorSpec(const int n_v0, const int *e0, const int *c0)
Definition: graph-color.cpp:61
@ BRANCH_DEGREE_SIZE
Choose variable with largest degree/size.
void symmetry(int v)
Set default symmetry value.
Definition: options.hpp:190
void update(Space &home, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:116
@ IRT_EQ
Equality ( )
Definition: int.hh:926
void distinct(Home home, const IntVarArgs &x, IntPropLevel ipl)
Post propagator for for all .
Definition: distinct.cpp:46
IntVarBranch INT_VAR_ACTION_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest action divided by domain size with decay factor d.
Definition: var.hpp:256
void solutions(unsigned int n)
Set default number of solutions to search for.
Definition: options.hpp:283
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.
Definition: var.hpp:236
const int n_v
Number of nodes.
Definition: graph-color.cpp:58
@ IRT_NQ
Disequality ( )
Definition: int.hh:927
Gecode::FloatVal c(-8, 8)
void model(int v)
Set default model value.
Definition: options.hpp:177
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
const GraphColorSpec g1(200, g1_e, g1_c)
First example graph.
Gecode::IntArgs i({1, 2, 3, 4})
@ BRANCH_AFC_SIZE
Choose variable with largest afc/size.
@ IRT_LQ
Less or equal ( )
Definition: int.hh:928
Options for scripts with additional size parameter
Definition: driver.hh:675
const GraphColorSpec g2(200, g2_e, g2_c)
Second example graph.