Generated on Sat May 25 2013 18:00:32 for Gecode by doxygen 1.8.3.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  * Copyright:
7  * Christian Schulte, 2004
8  *
9  * Last modified:
10  * $Date: 2013-02-19 13:26:08 +0100 (Tue, 19 Feb 2013) $ by $Author: schulte $
11  * $Revision: 13313 $
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 
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 
311 class GraphColor : public MinimizeScript {
312 private:
313  const GraphColorSpec& g;
315  IntVarArray v;
317  IntVar m;
318 public:
320  enum {
322  MODEL_CLIQUE
323  };
325  enum {
330  };
333  : g(opt.size() == 1 ? g2 : g1),
334  v(*this,g.n_v,0,g.n_v),
335  m(*this,0,g.n_v) {
336  rel(*this, v, IRT_LQ, m);
337  for (int i = 0; g.e[i] != -1; i += 2)
338  rel(*this, v[g.e[i]], IRT_NQ, v[g.e[i+1]]);
339 
340  const int* c = g.c;
341  for (int i = *c++; i--; c++)
342  rel(*this, v[*c], IRT_EQ, i);
343  while (*c != -1) {
344  int n = *c;
345  IntVarArgs x(n); c++;
346  for (int i = n; i--; c++)
347  x[i] = v[*c];
348  distinct(*this, x, opt.icl());
349  if (opt.model() == MODEL_CLIQUE)
350  rel(*this, m, IRT_GQ, n-1);
351  }
352  branch(*this, m, INT_VAL_MIN());
353  switch (opt.branching()) {
354  case BRANCH_SIZE:
355  branch(*this, v, INT_VAR_SIZE_MIN(), INT_VAL_MIN());
356  break;
357  case BRANCH_DEGREE:
359  INT_VAL_MIN());
360  break;
361  case BRANCH_SIZE_DEGREE:
363  break;
364  case BRANCH_SIZE_AFC:
365  branch(*this, v, INT_VAR_AFC_SIZE_MAX(opt.decay()), INT_VAL_MIN());
366  break;
367  default:
368  break;
369  }
370  }
372  virtual IntVar cost(void) const {
373  return m;
374  }
376  GraphColor(bool share, GraphColor& s) : MinimizeScript(share,s), g(s.g) {
377  v.update(*this, share, s.v);
378  m.update(*this, share, s.m);
379  }
381  virtual Space*
382  copy(bool share) {
383  return new GraphColor(share,*this);
384  }
386  virtual void
387  print(std::ostream& os) const {
388  os << "\tm = " << m << std::endl
389  << "\tv[] = {";
390  for (int i = 0; i < v.size(); i++) {
391  os << v[i] << ", ";
392  if ((i+1) % 15 == 0)
393  os << std::endl << "\t ";
394  }
395  os << "};" << std::endl;
396  }
397 };
398 
399 
403 int
404 main(int argc, char* argv[]) {
405  SizeOptions opt("GraphColor");
406  opt.icl(ICL_DOM);
407  opt.iterations(20);
408  opt.solutions(0);
410  opt.model(GraphColor::MODEL_NONE, "none",
411  "no lower bound");
412  opt.model(GraphColor::MODEL_CLIQUE, "clique",
413  "use maximal clique size as lower bound");
415  opt.branching(GraphColor::BRANCH_DEGREE, "degree");
416  opt.branching(GraphColor::BRANCH_SIZE, "size");
417  opt.branching(GraphColor::BRANCH_SIZE_DEGREE, "sizedegree");
418  opt.branching(GraphColor::BRANCH_SIZE_AFC, "sizeafc");
419  opt.parse(argc,argv);
420  Script::run<GraphColor,BAB,SizeOptions>(opt);
421  return 0;
422 }
423 
424 // STATISTICS: example-any
425