00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040
00041 using namespace Gecode;
00042
00055
00056 class GraphColorSpec {
00057 public:
00058 const int n_v;
00059 const int* e;
00060 const int* c;
00061 GraphColorSpec(const int n_v0, const int* e0, const int* c0)
00062 : n_v(n_v0), e(e0), c(c0) {}
00063 };
00064
00066 const int g1_e[] = {
00067 160,184, 192,199, 0,129, 20,80, 8,29, 93,171,
00068 101,165, 124,193, 2,100, 66,173, 151,191, 164,187,
00069 3,130, 118,176, 121,184, 25,106, 159,193, 121,123,
00070 5,62, 97,101, 6,143, 123,163, 19,125, 17,108,
00071 122,168, 181,184, 25,41, 62,70, 29,103, 48,67,
00072 46,160, 79,170, 143,152, 38,184, 2,40, 191,195,
00073 7,196, 62,199, 76,141, 82,166, 36,80, 51,189,
00074 13,97, 3,192, 90,180, 47,176, 13,172, 92,121,
00075 50,64, 65,113, 108,123, 26,106, 34,153, 90,123,
00076 34,39, 116,178, 22,179, 50,61, 84,105, 84,93,
00077 19,108, 29,59, 63,185, 119,129, 50,177, 80,194,
00078 13,36, 46,56, 38,144, 82,193, 72,93, 49,95,
00079 42,155, 117,140, 109,189, 19,35, 31,125, 118,191,
00080 163,169, 40,167, 91,127, 3,121, 124,149, 40,174,
00081 30,175, 19,132, 18,165, 34,93, 37,63, 10,55,
00082 88,95, 76,122, 7,91, 25,141, 29,173, 139,173,
00083 8,130, 110,158, 81,174, 113,114, 95,182, 136,149,
00084 5,199, 56,106, 36,120, 133,187, 111,172, 19,34,
00085 96,197, 32,108, 27,63, 50,188, 20,116, 50,118,
00086 10,50, 24,172, 86,138, 35,50, 141,153, 98,132,
00087 70,143, 1,97, 8,160, 37,170, 4,73, 1,94,
00088 88,146, 59,61, 104,156, 62,172, 117,139, 66,189,
00089 33,134, 122,169, 95,163, 95,152, 83,140, 110,189,
00090 147,159, 22,147, 59,173, 30,41, 33,183, 181,187,
00091 88,105, 93,151, 6,130, 24,30, 84,130, 72,120,
00092 118,159, 147,189, 122,149, 24,175, 39,169, 164,186,
00093 93,187, 13,156, 119,176, 73,91, 174,178, 71,198,
00094 10,134, 30,101, 79,93, 180,187, 1,50, 51,59,
00095 18,169, 73,153, 1,198, 137,154, 61,106, 80,113,
00096 48,142, 100,111, 97,133, 82,97, 136,170, 53,134,
00097 65,177, 7,80, 73,137, 6,70, 115,166, 72,196,
00098 40,109, 91,101, 2,177, 120,185, 55,65, 72,166,
00099 104,165, 173,187, 54,71, 3,61, 52,56, 120,149,
00100 64,72, 42,43, 75,185, 62,68, 108,147, 30,111,
00101 25,58, 39,93, 75,117, 61,194, 140,153, 80,121,
00102 93,102, 9,177, 7,163, 17,70, 5,168, 63,178,
00103 74,160, 148,158, 9,84, 30,76, 63,80, 68,99,
00104 20,152, 7,182, 7,22, 71,134, 32,100, 107,164,
00105 23,62, 5,98, 130,192, 65,144, 139,161, 24,124,
00106 31,47, 29,140, 61,153, 53,109, 20,26, 143,160,
00107 47,195, 171,172, 185,193, 128,173, 38,96, 14,171,
00108 176,199, 111,139, 21,54, 80,171, 116,185, 184,199,
00109 37,88, 62,133, 3,150, 48,109, 46,176, 24,178,
00110 59,172, 180,198, 64,109, 110,111, 101,146, 66,164,
00111 5,117, 144,179, 71,126, 166,169, 107,151, 46,85,
00112 106,139, 27,153, 97,148, 68,185, 17,179, 10,142,
00113 168,169, 4,46, 113,152, 52,176, 6,38, 22,48,
00114 20,120, 2,84, 71,85, 91,116, 0,189, 116,197,
00115 142,147, 33,165, 86,198, 146,149, 152,187, 44,62,
00116 48,175, 56,150, 63,161, 71,164, 17,171, 19,66, -1,-1};
00118 const int g1_c[] = {
00119 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,
00120 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,
00121 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,
00122 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,
00123 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,
00124 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,
00125 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,
00126 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,
00127 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,
00128 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,
00129 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,
00130 20, 15,16,30,35,36,56,66,78,81,84,99,126,128,129,138,151,152,153,166,190,
00131 20, 5,21,23,29,39,40,49,69,88,114,122,127,128,142,148,155,161,171,188,190,
00132 20, 0,3,15,23,31,41,57,60,69,76,89,107,109,128,153,155,161,169,174,183,
00133 20, 9,33,43,61,64,69,85,98,100,101,114,120,138,144,172,182,184,187,188,198,
00134 20, 4,6,8,10,23,27,45,57,66,68,71,93,110,122,139,146,150,155,156,188,
00135 20, 4,14,18,22,63,77,78,83,94,98,104,114,150,166,172,177,183,186,196,199,
00136 20, 22,35,46,47,63,64,70,78,87,99,102,112,116,119,125,131,152,165,174,186,
00137 20, 1,3,13,15,19,26,46,51,65,73,76,110,114,149,152,163,166,170,178,186,
00138 20, 9,29,33,40,50,54,102,105,111,112,119,120,124,128,136,138,144,175,190,199,
00139 20, 39,75,79,102,106,112,123,125,138,145,154,155,159,162,165,168,175,181,189,196,
00140 20, 0,11,12,23,42,63,68,71,79,83,89,98,113,117,121,141,156,176,177,193,
00141 20, 10,17,31,56,77,89,102,115,116,117,118,120,136,157,163,168,172,182,193,196,
00142 20, 9,34,35,43,44,57,60,64,79,87,88,94,103,133,156,157,166,171,174,189,
00143 20, 13,21,22,31,41,45,66,67,79,86,112,116,119,146,160,171,175,181,192,195,
00144 20, 11,24,26,45,57,91,99,102,122,123,135,141,144,146,154,156,167,191,194,199,
00145 15, 17,44,53,61,82,90,95,103,107,122,124,145,169,186,190,
00146 15, 2,14,26,37,58,61,75,95,103,109,115,116,141,154,199,
00147 15, 5,13,21,28,61,64,65,73,105,115,119,132,148,154,185,
00148 15, 10,20,38,45,61,75,109,111,115,143,150,157,163,179,186,
00149 15, 9,45,48,49,51,52,57,64,70,128,158,163,182,183,192,
00150 15, 47,55,57,64,79,80,105,131,152,163,172,180,186,190,197,
00151 15, 16,36,69,84,99,113,118,121,126,137,160,162,165,177,196,
00152 15, 16,44,50,53,54,65,69,80,96,112,125,139,150,153,193,
00153 15, 6,54,72,76,86,95,96,144,145,148,151,164,168,180,183,
00154 15, 10,18,19,37,65,85,90,104,112,128,147,158,164,192,198,
00155 15, 20,21,36,50,53,74,90,96,99,124,129,140,163,171,183,
00156 15, 13,20,27,53,65,77,86,98,110,125,133,139,147,188,196,
00157 15, 23,41,43,49,58,74,77,86,111,126,150,168,173,185,189,
00158 15, 11,35,62,89,125,132,134,141,149,163,166,167,171,194,196,
00159 15, 14,28,30,52,114,115,122,125,132,135,172,177,179,181,195,
00160 15, 0,8,9,20,23,53,77,93,121,136,141,147,150,191,199,
00161 15, 3,21,47,49,91,102,106,113,124,136,140,143,177,178,194,
00162 15, 44,46,52,53,68,82,89,90,120,128,144,147,175,178,192,
00163 15, 8,16,19,21,67,72,79,82,86,90,115,116,149,152,199,
00164 15, 12,30,78,80,97,120,122,123,143,146,151,165,173,177,178,
00165 15, 9,19,39,46,91,109,128,130,131,146,148,150,178,185,198,
00166 10, 29,44,69,74,96,115,122,126,189,199,
00167 10, 22,42,52,53,97,113,146,151,160,195,
00168 10, 19,20,32,77,81,133,134,138,147,177,
00169 10, 0,4,56,59,107,109,144,149,158,167,
00170 10, 6,69,99,104,110,114,118,134,152,172,
00171 5, 25,76,126,140,143,
00172 5, 4,54,67,116,142,
00173 5, 47,52,124,151,192,
00174 5, 32,55,61,64,73,
00175 5, 11,65,128,134,190,
00176 5, 45,48,63,131,139,
00177 5, 34,55,82,108,151,
00178 5, 24,34,54,112,156,
00179 5, 12,47,72,148,163,
00180 5, 74,126,145,162,170,
00181 5, 73,78,104,175,192,
00182 5, 19,83,127,130,166,
00183 5, 20,90,98,137,165,
00184 5, 22,24,29,49,132,
00185 5, 82,92,116,134,184,
00186 -1};
00187
00189 const GraphColorSpec g1(200, g1_e, g1_c);
00190
00192 const int g2_e[] = {
00193 63,97, 67,85, 18,180, 2,143, 55,156, 28,105,
00194 37,196, 26,33, 88,199, 175,179, 45,46, 62,70,
00195 53,58, 49,177, 91,178, 52,129, 147,165, 83,95,
00196 68,172, 66,150, 7,112, 71,92, 97,150, 114,116,
00197 56,86, 154,188, 95,97, 159,199, 68,119, 11,81,
00198 79,116, 64,74, 88,89, 99,114, 70,73, 87,162,
00199 24,119, 9,25, 174,188, 11,80, 47,198, 86,145,
00200 7,70, 37,170, 138,180, 66,199, 98,153, 70,142,
00201 84,196, 78,185, 7,131, 54,76, 69,82, 53,166,
00202 25,178, 3,36, 128,197, 59,96, 122,137, 54,124,
00203 157,162, 3,146, 72,198, 2,94, 137,158, 64,131,
00204 2,79, 18,119, 22,38, 92,136, 7,108, 179,194,
00205 68,166, 10,84, 28,192, 103,104, 28,75, 8,43,
00206 153,164, 59,119, 88,177, 36,70, 59,154, 57,75,
00207 109,174, 155,184, 16,74, 99,148, 77,121, 54,177,
00208 38,172, 138,174, 7,16, 28,146, 18,192, 4,154,
00209 17,31, 56,57, 174,177, 81,122, 101,175, 21,155,
00210 48,96, 124,154, 129,130, 58,169, 19,57, 115,165,
00211 40,117, 34,181, 28,32, 32,176, 19,119, 20,93,
00212 137,172, 55,135, 92,95, 34,51, 5,81, 63,118,
00213 72,94, 157,181, 15,68, 41,90, 35,73, 159,183,
00214 115,128, 28,183, 34,45, 149,177, 74,137, 51,110,
00215 25,170, 43,123, 53,109, 4,26, 68,80, 53,171,
00216 48,159, 0,28, 67,176, 87,163, 75,165, 137,162,
00217 150,199, 57,153, 32,93, 25,92, 13,88, 115,167,
00218 16,192, 113,157, 90,125, 104,188, 148,171, 96,101,
00219 22,68, 25,62, 89,161, 24,158, 66,190, 31,34,
00220 106,133, 51,102, 146,163, 31,154, 56,129, 66,157,
00221 38,93, 73,166, 117,174, 93,161, 3,95, 86,181,
00222 131,139, 5,182, 30,66, 0,11, 88,107, 54,101,
00223 36,66, 25,176, 8,38, 31,177, 78,195, 122,179,
00224 42,60, 83,112, 149,161, 184,188, 65,126, 74,198,
00225 38,80, 135,172, 43,156, 148,151, 135,195, 111,184,
00226 10,14, 97,152, -1,-1};
00228 const int g2_c[] = {
00229 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,
00230 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,
00231 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,
00232 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,
00233 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,
00234 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,
00235 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,
00236 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,
00237 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,
00238 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,
00239 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,
00240 20, 8,14,20,21,32,39,50,55,88,91,102,120,126,142,159,165,171,175,184,186,
00241 20, 10,15,35,43,50,52,60,77,80,81,85,87,106,120,145,151,155,159,176,196,
00242 20, 10,17,20,33,46,55,60,68,95,96,103,112,117,118,120,123,127,141,147,179,
00243 20, 9,34,41,52,56,72,73,100,102,116,124,131,138,155,157,158,172,173,182,183,
00244 20, 0,14,16,27,29,44,70,95,101,104,115,127,140,158,161,168,170,173,181,189,
00245 20, 6,14,17,18,23,27,50,51,83,84,93,107,108,116,122,136,154,159,172,185,
00246 20, 11,16,17,21,32,38,45,49,55,56,84,88,102,123,126,133,173,189,195,198,
00247 20, 0,14,21,29,30,40,63,67,93,98,116,122,131,140,150,152,174,178,183,190,
00248 20, 8,14,28,36,44,65,72,79,84,111,114,124,130,134,140,158,182,185,193,197,
00249 20, 9,10,12,17,28,42,46,50,57,62,90,117,132,149,168,176,178,182,187,188,
00250 20, 2,4,22,27,31,32,65,74,108,117,132,142,153,159,160,178,180,187,192,195,
00251 20, 2,4,7,21,56,64,67,100,103,130,135,140,147,151,156,161,167,191,193,196,
00252 20, 6,18,24,30,50,51,67,82,84,88,93,95,106,113,138,146,168,187,190,198,
00253 20, 28,37,44,98,99,107,112,119,129,132,135,151,156,167,168,179,182,190,198,199,
00254 15, 4,37,61,64,67,77,93,103,105,118,136,159,169,177,193,
00255 15, 17,44,53,61,82,90,95,103,107,122,124,145,169,186,190,
00256 15, 21,54,80,100,110,120,126,127,132,142,149,150,162,181,186,
00257 15, 3,7,21,22,40,41,82,94,96,98,126,140,143,147,152,
00258 15, 4,14,58,66,80,100,107,111,126,133,140,141,148,155,167,
00259 15, 31,38,44,48,59,74,75,77,100,105,139,168,171,182,187,
00260 15, 0,5,55,62,66,67,74,84,92,128,160,163,188,189,195,
00261 15, 0,36,55,73,80,96,121,133,167,173,190,191,193,195,198,
00262 15, 21,33,41,43,52,62,69,77,88,110,114,118,139,142,187,
00263 15, 12,14,23,29,44,58,67,74,124,149,150,156,167,171,183,
00264 15, 22,33,36,48,60,63,90,92,107,108,137,140,144,165,193,
00265 15, 11,24,40,45,49,59,72,123,125,132,151,161,167,179,184,
00266 15, 4,19,20,48,61,76,98,106,136,147,155,177,183,191,192,
00267 15, 17,22,28,35,55,74,86,90,98,106,121,138,168,190,195,
00268 15, 24,30,35,44,55,63,80,120,128,130,148,160,163,166,192,
00269 15, 20,30,59,64,69,94,104,106,139,140,144,147,156,161,199,
00270 15, 13,30,38,49,54,61,86,95,103,105,131,148,156,162,180,
00271 15, 2,25,34,41,46,63,69,81,91,113,139,159,186,188,190,
00272 15, 1,6,14,35,47,50,66,81,90,136,137,152,156,168,195,
00273 15, 34,37,47,52,94,100,104,105,107,131,147,171,186,191,192,
00274 15, 9,14,29,37,109,125,137,142,145,147,151,159,167,178,192,
00275 15, 13,45,60,62,78,99,104,118,142,143,156,179,189,191,197,
00276 15, 3,15,23,33,66,71,82,89,99,110,113,135,143,158,171,
00277 15, 27,39,101,102,118,133,134,138,141,144,145,148,165,169,189,
00278 15, 12,18,20,36,50,51,53,76,86,120,141,176,178,186,198,
00279 10, 6,8,17,77,109,112,115,124,129,193,
00280 10, 21,31,51,58,86,112,117,126,127,143,
00281 10, 10,74,87,108,123,134,157,180,186,190,
00282 10, 13,14,15,44,67,118,133,142,146,193,
00283 10, 40,44,46,66,73,128,141,161,174,192,
00284 5, 25,117,163,165,192,
00285 5, 40,46,105,121,134,
00286 5, 3,12,56,90,126,
00287 5, 13,95,98,120,188,
00288 5, 3,98,111,128,194,
00289 5, 4,21,51,65,73,
00290 5, 36,106,124,132,197,
00291 5, 5,35,57,91,144,
00292 5, 0,19,122,177,190,
00293 5, 85,98,111,113,134,
00294 5, 49,85,107,139,149,
00295 5, 54,88,102,111,172,
00296 5, 41,74,115,170,184,
00297 5, 33,70,123,151,159,
00298 5, 50,82,117,123,163,
00299 -1};
00300
00302 const GraphColorSpec g2(200, g2_e, g2_c);
00304
00311 class GraphColor : public MinimizeScript {
00312 private:
00313 const GraphColorSpec& g;
00315 IntVarArray v;
00317 IntVar m;
00318 public:
00320 enum {
00321 MODEL_NONE,
00322 MODEL_CLIQUE
00323 };
00325 enum {
00326 BRANCH_DEGREE,
00327 BRANCH_SIZE,
00328 BRANCH_SIZE_DEGREE,
00329 BRANCH_SIZE_AFC,
00330 };
00332 GraphColor(const SizeOptions& opt)
00333 : g(opt.size() == 1 ? g2 : g1),
00334 v(*this,g.n_v,0,g.n_v),
00335 m(*this,0,g.n_v) {
00336 rel(*this, v, IRT_LQ, m);
00337 for (int i = 0; g.e[i] != -1; i += 2)
00338 rel(*this, v[g.e[i]], IRT_NQ, v[g.e[i+1]]);
00339
00340 const int* c = g.c;
00341 for (int i = *c++; i--; c++)
00342 rel(*this, v[*c], IRT_EQ, i);
00343 while (*c != -1) {
00344 int n = *c;
00345 IntVarArgs x(n); c++;
00346 for (int i = n; i--; c++)
00347 x[i] = v[*c];
00348 distinct(*this, x, opt.icl());
00349 if (opt.model() == MODEL_CLIQUE)
00350 rel(*this, m, IRT_GQ, n-1);
00351 }
00352 branch(*this, m, INT_VAL_MIN);
00353 switch (opt.branching()) {
00354 case BRANCH_SIZE:
00355 branch(*this, v, INT_VAR_SIZE_MIN, INT_VAL_MIN);
00356 break;
00357 case BRANCH_DEGREE:
00358 branch(*this, v, tiebreak(INT_VAR_DEGREE_MAX,INT_VAR_SIZE_MIN),
00359 INT_VAL_MIN);
00360 break;
00361 case BRANCH_SIZE_DEGREE:
00362 branch(*this, v, INT_VAR_SIZE_DEGREE_MIN, INT_VAL_MIN);
00363 break;
00364 case BRANCH_SIZE_AFC:
00365 branch(*this, v, INT_VAR_SIZE_AFC_MIN, INT_VAL_MIN);
00366 break;
00367 default:
00368 break;
00369 }
00370 }
00372 virtual IntVar cost(void) const {
00373 return m;
00374 }
00376 GraphColor(bool share, GraphColor& s) : MinimizeScript(share,s), g(s.g) {
00377 v.update(*this, share, s.v);
00378 m.update(*this, share, s.m);
00379 }
00381 virtual Space*
00382 copy(bool share) {
00383 return new GraphColor(share,*this);
00384 }
00386 virtual void
00387 print(std::ostream& os) const {
00388 os << "\tm = " << m << std::endl
00389 << "\tv[] = {";
00390 for (int i = 0; i < v.size(); i++) {
00391 os << v[i] << ", ";
00392 if ((i+1) % 15 == 0)
00393 os << std::endl << "\t ";
00394 }
00395 os << "};" << std::endl;
00396 }
00397 };
00398
00399
00403 int
00404 main(int argc, char* argv[]) {
00405 SizeOptions opt("GraphColor");
00406 opt.icl(ICL_DOM);
00407 opt.iterations(20);
00408 opt.solutions(0);
00409 opt.model(GraphColor::MODEL_NONE);
00410 opt.model(GraphColor::MODEL_NONE, "none",
00411 "no lower bound");
00412 opt.model(GraphColor::MODEL_CLIQUE, "clique",
00413 "use maximal clique size as lower bound");
00414 opt.branching(GraphColor::BRANCH_DEGREE);
00415 opt.branching(GraphColor::BRANCH_DEGREE, "degree");
00416 opt.branching(GraphColor::BRANCH_SIZE, "size");
00417 opt.branching(GraphColor::BRANCH_SIZE_DEGREE, "sizedegree");
00418 opt.branching(GraphColor::BRANCH_SIZE_AFC, "sizeafc");
00419 opt.parse(argc,argv);
00420 Script::run<GraphColor,BAB,SizeOptions>(opt);
00421 return 0;
00422 }
00423
00424
00425