Generated on Sat Feb 7 2015 02:01:11 for Gecode by doxygen 1.8.9.1
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  * Last modified:
14  * $Date: 2013-07-08 14:22:40 +0200 (Mon, 08 Jul 2013) $ by $Author: schulte $
15  * $Revision: 13820 $
16  *
17  * This file is part of Gecode, the generic constraint
18  * development environment:
19  * http://www.gecode.org
20  *
21  * Permission is hereby granted, free of charge, to any person obtaining
22  * a copy of this software and associated documentation files (the
23  * "Software"), to deal in the Software without restriction, including
24  * without limitation the rights to use, copy, modify, merge, publish,
25  * distribute, sublicense, and/or sell copies of the Software, and to
26  * permit persons to whom the Software is furnished to do so, subject to
27  * the following conditions:
28  *
29  * The above copyright notice and this permission notice shall be
30  * included in all copies or substantial portions of the Software.
31  *
32  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
33  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
34  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
35  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
36  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
37  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
38  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
39  *
40  */
41 
42 #include <gecode/driver.hh>
43 #include <gecode/int.hh>
44 
45 using namespace Gecode;
46 
59 class GraphColorSpec {
61 public:
62  const int n_v;
63  const int* e;
64  const int* c;
65  GraphColorSpec(const int n_v0, const int* e0, const int* c0)
66  : n_v(n_v0), e(e0), c(c0) {}
67 };
68 
70 const int g1_e[] = {
71  160,184, 192,199, 0,129, 20,80, 8,29, 93,171,
72  101,165, 124,193, 2,100, 66,173, 151,191, 164,187,
73  3,130, 118,176, 121,184, 25,106, 159,193, 121,123,
74  5,62, 97,101, 6,143, 123,163, 19,125, 17,108,
75  122,168, 181,184, 25,41, 62,70, 29,103, 48,67,
76  46,160, 79,170, 143,152, 38,184, 2,40, 191,195,
77  7,196, 62,199, 76,141, 82,166, 36,80, 51,189,
78  13,97, 3,192, 90,180, 47,176, 13,172, 92,121,
79  50,64, 65,113, 108,123, 26,106, 34,153, 90,123,
80  34,39, 116,178, 22,179, 50,61, 84,105, 84,93,
81  19,108, 29,59, 63,185, 119,129, 50,177, 80,194,
82  13,36, 46,56, 38,144, 82,193, 72,93, 49,95,
83  42,155, 117,140, 109,189, 19,35, 31,125, 118,191,
84  163,169, 40,167, 91,127, 3,121, 124,149, 40,174,
85  30,175, 19,132, 18,165, 34,93, 37,63, 10,55,
86  88,95, 76,122, 7,91, 25,141, 29,173, 139,173,
87  8,130, 110,158, 81,174, 113,114, 95,182, 136,149,
88  5,199, 56,106, 36,120, 133,187, 111,172, 19,34,
89  96,197, 32,108, 27,63, 50,188, 20,116, 50,118,
90  10,50, 24,172, 86,138, 35,50, 141,153, 98,132,
91  70,143, 1,97, 8,160, 37,170, 4,73, 1,94,
92  88,146, 59,61, 104,156, 62,172, 117,139, 66,189,
93  33,134, 122,169, 95,163, 95,152, 83,140, 110,189,
94  147,159, 22,147, 59,173, 30,41, 33,183, 181,187,
95  88,105, 93,151, 6,130, 24,30, 84,130, 72,120,
96  118,159, 147,189, 122,149, 24,175, 39,169, 164,186,
97  93,187, 13,156, 119,176, 73,91, 174,178, 71,198,
98  10,134, 30,101, 79,93, 180,187, 1,50, 51,59,
99  18,169, 73,153, 1,198, 137,154, 61,106, 80,113,
100  48,142, 100,111, 97,133, 82,97, 136,170, 53,134,
101  65,177, 7,80, 73,137, 6,70, 115,166, 72,196,
102  40,109, 91,101, 2,177, 120,185, 55,65, 72,166,
103  104,165, 173,187, 54,71, 3,61, 52,56, 120,149,
104  64,72, 42,43, 75,185, 62,68, 108,147, 30,111,
105  25,58, 39,93, 75,117, 61,194, 140,153, 80,121,
106  93,102, 9,177, 7,163, 17,70, 5,168, 63,178,
107  74,160, 148,158, 9,84, 30,76, 63,80, 68,99,
108  20,152, 7,182, 7,22, 71,134, 32,100, 107,164,
109  23,62, 5,98, 130,192, 65,144, 139,161, 24,124,
110  31,47, 29,140, 61,153, 53,109, 20,26, 143,160,
111  47,195, 171,172, 185,193, 128,173, 38,96, 14,171,
112  176,199, 111,139, 21,54, 80,171, 116,185, 184,199,
113  37,88, 62,133, 3,150, 48,109, 46,176, 24,178,
114  59,172, 180,198, 64,109, 110,111, 101,146, 66,164,
115  5,117, 144,179, 71,126, 166,169, 107,151, 46,85,
116  106,139, 27,153, 97,148, 68,185, 17,179, 10,142,
117  168,169, 4,46, 113,152, 52,176, 6,38, 22,48,
118  20,120, 2,84, 71,85, 91,116, 0,189, 116,197,
119  142,147, 33,165, 86,198, 146,149, 152,187, 44,62,
120  48,175, 56,150, 63,161, 71,164, 17,171, 19,66, -1,-1};
122 const int g1_c[] = {
123  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,
124  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,
125  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,
126  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,
127  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,
128  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,
129  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,
130  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,
131  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,
132  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,
133  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,
134  20, 15,16,30,35,36,56,66,78,81,84,99,126,128,129,138,151,152,153,166,190,
135  20, 5,21,23,29,39,40,49,69,88,114,122,127,128,142,148,155,161,171,188,190,
136  20, 0,3,15,23,31,41,57,60,69,76,89,107,109,128,153,155,161,169,174,183,
137  20, 9,33,43,61,64,69,85,98,100,101,114,120,138,144,172,182,184,187,188,198,
138  20, 4,6,8,10,23,27,45,57,66,68,71,93,110,122,139,146,150,155,156,188,
139  20, 4,14,18,22,63,77,78,83,94,98,104,114,150,166,172,177,183,186,196,199,
140  20, 22,35,46,47,63,64,70,78,87,99,102,112,116,119,125,131,152,165,174,186,
141  20, 1,3,13,15,19,26,46,51,65,73,76,110,114,149,152,163,166,170,178,186,
142  20, 9,29,33,40,50,54,102,105,111,112,119,120,124,128,136,138,144,175,190,199,
143  20, 39,75,79,102,106,112,123,125,138,145,154,155,159,162,165,168,175,181,189,196,
144  20, 0,11,12,23,42,63,68,71,79,83,89,98,113,117,121,141,156,176,177,193,
145  20, 10,17,31,56,77,89,102,115,116,117,118,120,136,157,163,168,172,182,193,196,
146  20, 9,34,35,43,44,57,60,64,79,87,88,94,103,133,156,157,166,171,174,189,
147  20, 13,21,22,31,41,45,66,67,79,86,112,116,119,146,160,171,175,181,192,195,
148  20, 11,24,26,45,57,91,99,102,122,123,135,141,144,146,154,156,167,191,194,199,
149  15, 17,44,53,61,82,90,95,103,107,122,124,145,169,186,190,
150  15, 2,14,26,37,58,61,75,95,103,109,115,116,141,154,199,
151  15, 5,13,21,28,61,64,65,73,105,115,119,132,148,154,185,
152  15, 10,20,38,45,61,75,109,111,115,143,150,157,163,179,186,
153  15, 9,45,48,49,51,52,57,64,70,128,158,163,182,183,192,
154  15, 47,55,57,64,79,80,105,131,152,163,172,180,186,190,197,
155  15, 16,36,69,84,99,113,118,121,126,137,160,162,165,177,196,
156  15, 16,44,50,53,54,65,69,80,96,112,125,139,150,153,193,
157  15, 6,54,72,76,86,95,96,144,145,148,151,164,168,180,183,
158  15, 10,18,19,37,65,85,90,104,112,128,147,158,164,192,198,
159  15, 20,21,36,50,53,74,90,96,99,124,129,140,163,171,183,
160  15, 13,20,27,53,65,77,86,98,110,125,133,139,147,188,196,
161  15, 23,41,43,49,58,74,77,86,111,126,150,168,173,185,189,
162  15, 11,35,62,89,125,132,134,141,149,163,166,167,171,194,196,
163  15, 14,28,30,52,114,115,122,125,132,135,172,177,179,181,195,
164  15, 0,8,9,20,23,53,77,93,121,136,141,147,150,191,199,
165  15, 3,21,47,49,91,102,106,113,124,136,140,143,177,178,194,
166  15, 44,46,52,53,68,82,89,90,120,128,144,147,175,178,192,
167  15, 8,16,19,21,67,72,79,82,86,90,115,116,149,152,199,
168  15, 12,30,78,80,97,120,122,123,143,146,151,165,173,177,178,
169  15, 9,19,39,46,91,109,128,130,131,146,148,150,178,185,198,
170  10, 29,44,69,74,96,115,122,126,189,199,
171  10, 22,42,52,53,97,113,146,151,160,195,
172  10, 19,20,32,77,81,133,134,138,147,177,
173  10, 0,4,56,59,107,109,144,149,158,167,
174  10, 6,69,99,104,110,114,118,134,152,172,
175  5, 25,76,126,140,143,
176  5, 4,54,67,116,142,
177  5, 47,52,124,151,192,
178  5, 32,55,61,64,73,
179  5, 11,65,128,134,190,
180  5, 45,48,63,131,139,
181  5, 34,55,82,108,151,
182  5, 24,34,54,112,156,
183  5, 12,47,72,148,163,
184  5, 74,126,145,162,170,
185  5, 73,78,104,175,192,
186  5, 19,83,127,130,166,
187  5, 20,90,98,137,165,
188  5, 22,24,29,49,132,
189  5, 82,92,116,134,184,
190  -1};
191 
193 const GraphColorSpec g1(200, g1_e, g1_c);
194 
196 const int g2_e[] = {
197  63,97, 67,85, 18,180, 2,143, 55,156, 28,105,
198  37,196, 26,33, 88,199, 175,179, 45,46, 62,70,
199  53,58, 49,177, 91,178, 52,129, 147,165, 83,95,
200  68,172, 66,150, 7,112, 71,92, 97,150, 114,116,
201  56,86, 154,188, 95,97, 159,199, 68,119, 11,81,
202  79,116, 64,74, 88,89, 99,114, 70,73, 87,162,
203  24,119, 9,25, 174,188, 11,80, 47,198, 86,145,
204  7,70, 37,170, 138,180, 66,199, 98,153, 70,142,
205  84,196, 78,185, 7,131, 54,76, 69,82, 53,166,
206  25,178, 3,36, 128,197, 59,96, 122,137, 54,124,
207  157,162, 3,146, 72,198, 2,94, 137,158, 64,131,
208  2,79, 18,119, 22,38, 92,136, 7,108, 179,194,
209  68,166, 10,84, 28,192, 103,104, 28,75, 8,43,
210  153,164, 59,119, 88,177, 36,70, 59,154, 57,75,
211  109,174, 155,184, 16,74, 99,148, 77,121, 54,177,
212  38,172, 138,174, 7,16, 28,146, 18,192, 4,154,
213  17,31, 56,57, 174,177, 81,122, 101,175, 21,155,
214  48,96, 124,154, 129,130, 58,169, 19,57, 115,165,
215  40,117, 34,181, 28,32, 32,176, 19,119, 20,93,
216  137,172, 55,135, 92,95, 34,51, 5,81, 63,118,
217  72,94, 157,181, 15,68, 41,90, 35,73, 159,183,
218  115,128, 28,183, 34,45, 149,177, 74,137, 51,110,
219  25,170, 43,123, 53,109, 4,26, 68,80, 53,171,
220  48,159, 0,28, 67,176, 87,163, 75,165, 137,162,
221  150,199, 57,153, 32,93, 25,92, 13,88, 115,167,
222  16,192, 113,157, 90,125, 104,188, 148,171, 96,101,
223  22,68, 25,62, 89,161, 24,158, 66,190, 31,34,
224  106,133, 51,102, 146,163, 31,154, 56,129, 66,157,
225  38,93, 73,166, 117,174, 93,161, 3,95, 86,181,
226  131,139, 5,182, 30,66, 0,11, 88,107, 54,101,
227  36,66, 25,176, 8,38, 31,177, 78,195, 122,179,
228  42,60, 83,112, 149,161, 184,188, 65,126, 74,198,
229  38,80, 135,172, 43,156, 148,151, 135,195, 111,184,
230  10,14, 97,152, -1,-1};
232 const int g2_c[] = {
233  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,
234  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,
235  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,
236  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,
237  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,
238  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,
239  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,
240  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,
241  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,
242  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,
243  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,
244  20, 8,14,20,21,32,39,50,55,88,91,102,120,126,142,159,165,171,175,184,186,
245  20, 10,15,35,43,50,52,60,77,80,81,85,87,106,120,145,151,155,159,176,196,
246  20, 10,17,20,33,46,55,60,68,95,96,103,112,117,118,120,123,127,141,147,179,
247  20, 9,34,41,52,56,72,73,100,102,116,124,131,138,155,157,158,172,173,182,183,
248  20, 0,14,16,27,29,44,70,95,101,104,115,127,140,158,161,168,170,173,181,189,
249  20, 6,14,17,18,23,27,50,51,83,84,93,107,108,116,122,136,154,159,172,185,
250  20, 11,16,17,21,32,38,45,49,55,56,84,88,102,123,126,133,173,189,195,198,
251  20, 0,14,21,29,30,40,63,67,93,98,116,122,131,140,150,152,174,178,183,190,
252  20, 8,14,28,36,44,65,72,79,84,111,114,124,130,134,140,158,182,185,193,197,
253  20, 9,10,12,17,28,42,46,50,57,62,90,117,132,149,168,176,178,182,187,188,
254  20, 2,4,22,27,31,32,65,74,108,117,132,142,153,159,160,178,180,187,192,195,
255  20, 2,4,7,21,56,64,67,100,103,130,135,140,147,151,156,161,167,191,193,196,
256  20, 6,18,24,30,50,51,67,82,84,88,93,95,106,113,138,146,168,187,190,198,
257  20, 28,37,44,98,99,107,112,119,129,132,135,151,156,167,168,179,182,190,198,199,
258  15, 4,37,61,64,67,77,93,103,105,118,136,159,169,177,193,
259  15, 17,44,53,61,82,90,95,103,107,122,124,145,169,186,190,
260  15, 21,54,80,100,110,120,126,127,132,142,149,150,162,181,186,
261  15, 3,7,21,22,40,41,82,94,96,98,126,140,143,147,152,
262  15, 4,14,58,66,80,100,107,111,126,133,140,141,148,155,167,
263  15, 31,38,44,48,59,74,75,77,100,105,139,168,171,182,187,
264  15, 0,5,55,62,66,67,74,84,92,128,160,163,188,189,195,
265  15, 0,36,55,73,80,96,121,133,167,173,190,191,193,195,198,
266  15, 21,33,41,43,52,62,69,77,88,110,114,118,139,142,187,
267  15, 12,14,23,29,44,58,67,74,124,149,150,156,167,171,183,
268  15, 22,33,36,48,60,63,90,92,107,108,137,140,144,165,193,
269  15, 11,24,40,45,49,59,72,123,125,132,151,161,167,179,184,
270  15, 4,19,20,48,61,76,98,106,136,147,155,177,183,191,192,
271  15, 17,22,28,35,55,74,86,90,98,106,121,138,168,190,195,
272  15, 24,30,35,44,55,63,80,120,128,130,148,160,163,166,192,
273  15, 20,30,59,64,69,94,104,106,139,140,144,147,156,161,199,
274  15, 13,30,38,49,54,61,86,95,103,105,131,148,156,162,180,
275  15, 2,25,34,41,46,63,69,81,91,113,139,159,186,188,190,
276  15, 1,6,14,35,47,50,66,81,90,136,137,152,156,168,195,
277  15, 34,37,47,52,94,100,104,105,107,131,147,171,186,191,192,
278  15, 9,14,29,37,109,125,137,142,145,147,151,159,167,178,192,
279  15, 13,45,60,62,78,99,104,118,142,143,156,179,189,191,197,
280  15, 3,15,23,33,66,71,82,89,99,110,113,135,143,158,171,
281  15, 27,39,101,102,118,133,134,138,141,144,145,148,165,169,189,
282  15, 12,18,20,36,50,51,53,76,86,120,141,176,178,186,198,
283  10, 6,8,17,77,109,112,115,124,129,193,
284  10, 21,31,51,58,86,112,117,126,127,143,
285  10, 10,74,87,108,123,134,157,180,186,190,
286  10, 13,14,15,44,67,118,133,142,146,193,
287  10, 40,44,46,66,73,128,141,161,174,192,
288  5, 25,117,163,165,192,
289  5, 40,46,105,121,134,
290  5, 3,12,56,90,126,
291  5, 13,95,98,120,188,
292  5, 3,98,111,128,194,
293  5, 4,21,51,65,73,
294  5, 36,106,124,132,197,
295  5, 5,35,57,91,144,
296  5, 0,19,122,177,190,
297  5, 85,98,111,113,134,
298  5, 49,85,107,139,149,
299  5, 54,88,102,111,172,
300  5, 41,74,115,170,184,
301  5, 33,70,123,151,159,
302  5, 50,82,117,123,163,
303  -1};
304 
306 const GraphColorSpec g2(200, g2_e, g2_c);
308 
316 private:
317  const GraphColorSpec& g;
319  IntVarArray v;
321  IntVar m;
322 public:
324  enum {
326  MODEL_CLIQUE
327  };
329  enum {
335  };
337  enum {
339  SYMMETRY_LDSB
340  };
343  : g(opt.size() == 1 ? g2 : g1),
344  v(*this,g.n_v,0,g.n_v-1),
345  m(*this,0,g.n_v-1) {
346  rel(*this, v, IRT_LQ, m);
347  for (int i = 0; g.e[i] != -1; i += 2)
348  rel(*this, v[g.e[i]], IRT_NQ, v[g.e[i+1]]);
349 
350  const int* c = g.c;
351  for (int i = *c++; i--; c++)
352  rel(*this, v[*c], IRT_EQ, i);
353  while (*c != -1) {
354  int n = *c;
355  IntVarArgs x(n); c++;
356  for (int i = n; i--; c++)
357  x[i] = v[*c];
358  distinct(*this, x, opt.icl());
359  if (opt.model() == MODEL_CLIQUE)
360  rel(*this, m, IRT_GQ, n-1);
361  }
363  branch(*this, m, INT_VAL_MIN());
364  if (opt.symmetry() == SYMMETRY_NONE) {
366  switch (opt.branching()) {
367  case BRANCH_SIZE:
368  branch(*this, v, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
369  break;
370  case BRANCH_DEGREE:
372  INT_VAL_MIN());
373  break;
374  case BRANCH_SIZE_DEGREE:
376  break;
377  case BRANCH_SIZE_AFC:
378  branch(*this, v, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
379  break;
380  case BRANCH_SIZE_ACTIVITY:
381  branch(*this, v, INT_VAR_ACTIVITY_SIZE_MAX(opt.decay()), INT_VAL_MIN());
382  break;
383  default:
384  break;
385  }
386  } else { // opt.symmetry() == SYMMETRY_LDSB
389  Symmetries syms;
390  syms << ValueSymmetry(IntArgs::create(g.n_v,0));
391  switch (opt.branching()) {
392  case BRANCH_SIZE:
393  branch(*this, v, INT_VAR_SIZE_MIN(), INT_VAL_MIN(), syms);
394  break;
395  case BRANCH_DEGREE:
397  INT_VAL_MIN(), syms);
398  break;
399  case BRANCH_SIZE_DEGREE:
400  branch(*this, v, INT_VAR_DEGREE_SIZE_MAX(), INT_VAL_MIN(), syms);
401  break;
402  case BRANCH_SIZE_AFC:
403  branch(*this, v, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN(), syms);
404  break;
405  case BRANCH_SIZE_ACTIVITY:
406  branch(*this, v, INT_VAR_ACTIVITY_SIZE_MAX(opt.decay()), INT_VAL_MIN(), syms);
407  break;
408  default:
409  break;
410  }
411  }
412  }
414  virtual IntVar cost(void) const {
415  return m;
416  }
418  GraphColor(bool share, GraphColor& s) : IntMinimizeScript(share,s), g(s.g) {
419  v.update(*this, share, s.v);
420  m.update(*this, share, s.m);
421  }
423  virtual Space*
424  copy(bool share) {
425  return new GraphColor(share,*this);
426  }
428  virtual void
429  print(std::ostream& os) const {
430  os << "\tm = " << m << std::endl
431  << "\tv[] = {";
432  for (int i = 0; i < v.size(); i++) {
433  os << v[i] << ", ";
434  if ((i+1) % 15 == 0)
435  os << std::endl << "\t ";
436  }
437  os << "};" << std::endl;
438  }
439 };
440 
441 
445 int
446 main(int argc, char* argv[]) {
447  SizeOptions opt("GraphColor");
448  opt.icl(ICL_DOM);
449  opt.iterations(20);
450  opt.solutions(0);
452  opt.model(GraphColor::MODEL_NONE, "none",
453  "no lower bound");
454  opt.model(GraphColor::MODEL_CLIQUE, "clique",
455  "use maximal clique size as lower bound");
457  opt.branching(GraphColor::BRANCH_DEGREE, "degree");
458  opt.branching(GraphColor::BRANCH_SIZE, "size");
459  opt.branching(GraphColor::BRANCH_SIZE_DEGREE, "sizedegree");
460  opt.branching(GraphColor::BRANCH_SIZE_AFC, "sizeafc");
464  opt.symmetry(GraphColor::SYMMETRY_LDSB,"ldsb","use value symmetry breaking");
465  opt.parse(argc,argv);
466  Script::run<GraphColor,BAB,SizeOptions>(opt);
467  return 0;
468 }
469 
470 // STATISTICS: example-any
471 
static IntArgs create(int n, int start, int inc=1)
Allocate array with n elements such that for all .
Definition: array.hpp:72
Options for scripts with additional size parameter
Definition: driver.hh:567
Choose variable with smallest size/afc.
Choose variable with smallest size/activity.
IntVarBranch INT_VAR_DEGREE_SIZE_MAX(BranchTbl tbl)
Select variable with largest degree divided by domain size.
Definition: var.hpp:227
void update(Space &home, bool share, VarImpVar< VarImp > &y)
Update this variable to be a clone of variable y.
Definition: var.hpp:128
Choose variable with smallest size/degree.
void parse(int &argc, char *argv[])
Parse options from arguments argv (number is argc)
Definition: options.cpp:435
Less or equal ( )
Definition: int.hh:906
Graph specification
Definition: graph-color.cpp:60
Example: Clique-based graph coloring
Collection of symmetries.
Definition: int.hh:4300
IntVarBranch INT_VAR_SIZE_MIN(BranchTbl tbl)
Select variable with smallest domain size.
Definition: var.hpp:212
Choose variable with largest degree.
const int * c
Cliques.
Definition: graph-color.cpp:64
Integer variable array.
Definition: int.hh:741
Use maximal clique size as lower bound.
Computation spaces.
Definition: core.hpp:1362
Greater or equal ( )
Definition: int.hh:908
Parametric base-class for scripts.
Definition: driver.hh:622
void iterations(unsigned int i)
Set default number of iterations.
Definition: options.hpp:385
void decay(double d)
Set default decay factor.
Definition: options.hpp:216
void update(Space &, bool share, VarArray< Var > &a)
Update array to be a clone of array a.
Definition: array.hpp:1072
Gecode::FloatVal c(-8, 8)
int main(int argc, char *argv[])
Main-function.
Use LDSB for value symmetry breaking.
Gecode::IntArgs i(4, 1, 2, 3, 4)
virtual Space * copy(bool share)
Copying during cloning.
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:904
IntVarBranch INT_VAR_DEGREE_MAX(BranchTbl tbl)
Select variable with largest degree.
Definition: var.hpp:147
Options opt
The options.
Definition: test.cpp:101
const int n_v
Number of nodes.
Definition: graph-color.cpp:62
IntValBranch INT_VAL_MIN(void)
Select smallest value.
Definition: val.hpp:68
unsigned int size(I &i)
Size of all ranges of range iterator i.
SymmetryHandle ValueSymmetry(const IntArgs &vs)
Values in v are interchangeable.
Definition: ldsb.cpp:85
IntVarBranch INT_VAR_ACTIVITY_SIZE_MAX(double d, BranchTbl tbl)
Select variable with largest activity divided by domain size with decay factor d. ...
Definition: var.hpp:262
GraphColor(bool share, GraphColor &s)
Constructor for cloning s.
void branching(int v)
Set default branching value.
Definition: options.hpp:203
No lower bound.
Passing integer variables.
Definition: int.hh:636
const int * e
Edges.
Definition: graph-color.cpp:63
const int v[7]
Definition: distinct.cpp:207
TieBreak< VarBranch > tiebreak(VarBranch a, VarBranch b)
Combine variable selection criteria a and b for tie-breaking.
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
GraphColorSpec(const int n_v0, const int *e0, const int *c0)
Definition: graph-color.cpp:65
virtual IntVar cost(void) const
Cost function.
Integer variables.
Definition: int.hh:350
void symmetry(int v)
Set default symmetry value.
Definition: options.hpp:168
GraphColor(const SizeOptions &opt)
The actual model.
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
Choose variable with smallest size.
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:242
void distinct(Home home, const IntVarArgs &x, IntConLevel icl)
Post propagator for for all .
Definition: distinct.cpp:47
void solutions(unsigned int n)
Set default number of solutions to search for.
Definition: options.hpp:243
void model(int v)
Set default model value.
Definition: options.hpp:155
Gecode toplevel namespace
Disequality ( )
Definition: int.hh:905
BrancherHandle 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:43
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
virtual void print(std::ostream &os) const
Print the solution.
void icl(IntConLevel i)
Set default integer consistency level.
Definition: options.hpp:194
Domain propagation or consistency.
Definition: int.hh:940