Generated on Thu Jul 6 07:06:40 2006 for Gecode by doxygen 1.4.7

graph-color.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-12-08 13:15:17 +0100 (Thu, 08 Dec 2005) $ by $Author: tack $
00010  *     $Revision: 2743 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "examples/support.hh"
00023 
00036 
00037 class GraphColorSpec {
00038 public:
00039   const int  n_v; 
00040   const int* e;   
00041   const int* c;   
00042 };
00043 
00045 static const int g1_e[] = {
00046   160,184,  192,199,  0,129,  20,80,  8,29,  93,171,
00047   101,165,  124,193,  2,100,  66,173,  151,191,  164,187,
00048   3,130,  118,176,  121,184,  25,106,  159,193,  121,123,
00049   5,62,  97,101,  6,143,  123,163,  19,125,  17,108,
00050   122,168,  181,184,  25,41,  62,70,  29,103,  48,67,
00051   46,160,  79,170,  143,152,  38,184,  2,40,  191,195,
00052   7,196,  62,199,  76,141,  82,166,  36,80,  51,189,
00053   13,97,  3,192,  90,180,  47,176,  13,172,  92,121,
00054   50,64,  65,113,  108,123,  26,106,  34,153,  90,123,
00055   34,39,  116,178,  22,179,  50,61,  84,105,  84,93,
00056   19,108,  29,59,  63,185,  119,129,  50,177,  80,194,
00057   13,36,  46,56,  38,144,  82,193,  72,93,  49,95,
00058   42,155,  117,140,  109,189,  19,35,  31,125,  118,191,
00059   163,169,  40,167,  91,127,  3,121,  124,149,  40,174,
00060   30,175,  19,132,  18,165,  34,93,  37,63,  10,55,
00061   88,95,  76,122,  7,91,  25,141,  29,173,  139,173,
00062   8,130,  110,158,  81,174,  113,114,  95,182,  136,149,
00063   5,199,  56,106,  36,120,  133,187,  111,172,  19,34,
00064   96,197,  32,108,  27,63,  50,188,  20,116,  50,118,
00065   10,50,  24,172,  86,138,  35,50,  141,153,  98,132,
00066   70,143,  1,97,  8,160,  37,170,  4,73,  1,94,
00067   88,146,  59,61,  104,156,  62,172,  117,139,  66,189,
00068   33,134,  122,169,  95,163,  95,152,  83,140,  110,189,
00069   147,159,  22,147,  59,173,  30,41,  33,183,  181,187,
00070   88,105,  93,151,  6,130,  24,30,  84,130,  72,120,
00071   118,159,  147,189,  122,149,  24,175,  39,169,  164,186,
00072   93,187,  13,156,  119,176,  73,91,  174,178,  71,198,
00073   10,134,  30,101,  79,93,  180,187,  1,50,  51,59,
00074   18,169,  73,153,  1,198,  137,154,  61,106,  80,113,
00075   48,142,  100,111,  97,133,  82,97,  136,170,  53,134,
00076   65,177,  7,80,  73,137,  6,70,  115,166,  72,196,
00077   40,109,  91,101,  2,177,  120,185,  55,65,  72,166,
00078   104,165,  173,187,  54,71,  3,61,  52,56,  120,149,
00079   64,72,  42,43,  75,185,  62,68,  108,147,  30,111,
00080   25,58,  39,93,  75,117,  61,194,  140,153,  80,121,
00081   93,102,  9,177,  7,163,  17,70,  5,168,  63,178,
00082   74,160,  148,158,  9,84,  30,76,  63,80,  68,99,
00083   20,152,  7,182,  7,22,  71,134,  32,100,  107,164,
00084   23,62,  5,98,  130,192,  65,144,  139,161,  24,124,
00085   31,47,  29,140,  61,153,  53,109,  20,26,  143,160,
00086   47,195,  171,172,  185,193,  128,173,  38,96,  14,171,
00087   176,199,  111,139,  21,54,  80,171,  116,185,  184,199,
00088   37,88,  62,133,  3,150,  48,109,  46,176,  24,178,
00089   59,172,  180,198,  64,109,  110,111,  101,146,  66,164,
00090   5,117,  144,179,  71,126,  166,169,  107,151,  46,85,
00091   106,139,  27,153,  97,148,  68,185,  17,179,  10,142,
00092   168,169,  4,46,  113,152,  52,176,  6,38,  22,48,
00093   20,120,  2,84,  71,85,  91,116,  0,189,  116,197,
00094   142,147,  33,165,  86,198,  146,149,  152,187,  44,62,
00095   48,175,  56,150,  63,161,  71,164,  17,171,  19,66,       -1,-1};
00097 static const int g1_c[] = {
00098   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,
00099   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,
00100   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,
00101   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,
00102   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,
00103   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,
00104   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,
00105   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,
00106   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,
00107   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,
00108   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,
00109   20,  15,16,30,35,36,56,66,78,81,84,99,126,128,129,138,151,152,153,166,190,
00110   20,  5,21,23,29,39,40,49,69,88,114,122,127,128,142,148,155,161,171,188,190,
00111   20,  0,3,15,23,31,41,57,60,69,76,89,107,109,128,153,155,161,169,174,183,
00112   20,  9,33,43,61,64,69,85,98,100,101,114,120,138,144,172,182,184,187,188,198,
00113   20,  4,6,8,10,23,27,45,57,66,68,71,93,110,122,139,146,150,155,156,188,
00114   20,  4,14,18,22,63,77,78,83,94,98,104,114,150,166,172,177,183,186,196,199,
00115   20,  22,35,46,47,63,64,70,78,87,99,102,112,116,119,125,131,152,165,174,186,
00116   20,  1,3,13,15,19,26,46,51,65,73,76,110,114,149,152,163,166,170,178,186,
00117   20,  9,29,33,40,50,54,102,105,111,112,119,120,124,128,136,138,144,175,190,199,
00118   20,  39,75,79,102,106,112,123,125,138,145,154,155,159,162,165,168,175,181,189,196,
00119   20,  0,11,12,23,42,63,68,71,79,83,89,98,113,117,121,141,156,176,177,193,
00120   20,  10,17,31,56,77,89,102,115,116,117,118,120,136,157,163,168,172,182,193,196,
00121   20,  9,34,35,43,44,57,60,64,79,87,88,94,103,133,156,157,166,171,174,189,
00122   20,  13,21,22,31,41,45,66,67,79,86,112,116,119,146,160,171,175,181,192,195,
00123   20,  11,24,26,45,57,91,99,102,122,123,135,141,144,146,154,156,167,191,194,199,
00124   15,  17,44,53,61,82,90,95,103,107,122,124,145,169,186,190,
00125   15,  2,14,26,37,58,61,75,95,103,109,115,116,141,154,199,
00126   15,  5,13,21,28,61,64,65,73,105,115,119,132,148,154,185,
00127   15,  10,20,38,45,61,75,109,111,115,143,150,157,163,179,186,
00128   15,  9,45,48,49,51,52,57,64,70,128,158,163,182,183,192,
00129   15,  47,55,57,64,79,80,105,131,152,163,172,180,186,190,197,
00130   15,  16,36,69,84,99,113,118,121,126,137,160,162,165,177,196,
00131   15,  16,44,50,53,54,65,69,80,96,112,125,139,150,153,193,
00132   15,  6,54,72,76,86,95,96,144,145,148,151,164,168,180,183,
00133   15,  10,18,19,37,65,85,90,104,112,128,147,158,164,192,198,
00134   15,  20,21,36,50,53,74,90,96,99,124,129,140,163,171,183,
00135   15,  13,20,27,53,65,77,86,98,110,125,133,139,147,188,196,
00136   15,  23,41,43,49,58,74,77,86,111,126,150,168,173,185,189,
00137   15,  11,35,62,89,125,132,134,141,149,163,166,167,171,194,196,
00138   15,  14,28,30,52,114,115,122,125,132,135,172,177,179,181,195,
00139   15,  0,8,9,20,23,53,77,93,121,136,141,147,150,191,199,
00140   15,  3,21,47,49,91,102,106,113,124,136,140,143,177,178,194,
00141   15,  44,46,52,53,68,82,89,90,120,128,144,147,175,178,192,
00142   15,  8,16,19,21,67,72,79,82,86,90,115,116,149,152,199,
00143   15,  12,30,78,80,97,120,122,123,143,146,151,165,173,177,178,
00144   15,  9,19,39,46,91,109,128,130,131,146,148,150,178,185,198,
00145   10,  29,44,69,74,96,115,122,126,189,199,
00146   10,  22,42,52,53,97,113,146,151,160,195,
00147   10,  19,20,32,77,81,133,134,138,147,177,
00148   10,  0,4,56,59,107,109,144,149,158,167,
00149   10,  6,69,99,104,110,114,118,134,152,172,
00150   5,  25,76,126,140,143,
00151   5,  4,54,67,116,142,
00152   5,  47,52,124,151,192,
00153   5,  32,55,61,64,73,
00154   5,  11,65,128,134,190,
00155   5,  45,48,63,131,139,
00156   5,  34,55,82,108,151,
00157   5,  24,34,54,112,156,
00158   5,  12,47,72,148,163,
00159   5,  74,126,145,162,170,
00160   5,  73,78,104,175,192,
00161   5,  19,83,127,130,166,
00162   5,  20,90,98,137,165,
00163   5,  22,24,29,49,132,
00164   5,  82,92,116,134,184,
00165   -1};
00166 
00168 static const GraphColorSpec g1 = {
00169   200, g1_e, g1_c
00170 };
00171 
00172 
00174 static const int g2_e[] = {
00175   63,97,  67,85,  18,180,  2,143,  55,156,  28,105,
00176   37,196,  26,33,  88,199,  175,179,  45,46,  62,70,
00177   53,58,  49,177,  91,178,  52,129,  147,165,  83,95,
00178   68,172,  66,150,  7,112,  71,92,  97,150,  114,116,
00179   56,86,  154,188,  95,97,  159,199,  68,119,  11,81,
00180   79,116,  64,74,  88,89,  99,114,  70,73,  87,162,
00181   24,119,  9,25,  174,188,  11,80,  47,198,  86,145,
00182   7,70,  37,170,  138,180,  66,199,  98,153,  70,142,
00183   84,196,  78,185,  7,131,  54,76,  69,82,  53,166,
00184   25,178,  3,36,  128,197,  59,96,  122,137,  54,124,
00185   157,162,  3,146,  72,198,  2,94,  137,158,  64,131,
00186   2,79,  18,119,  22,38,  92,136,  7,108,  179,194,
00187   68,166,  10,84,  28,192,  103,104,  28,75,  8,43,
00188   153,164,  59,119,  88,177,  36,70,  59,154,  57,75,
00189   109,174,  155,184,  16,74,  99,148,  77,121,  54,177,
00190   38,172,  138,174,  7,16,  28,146,  18,192,  4,154,
00191   17,31,  56,57,  174,177,  81,122,  101,175,  21,155,
00192   48,96,  124,154,  129,130,  58,169,  19,57,  115,165,
00193   40,117,  34,181,  28,32,  32,176,  19,119,  20,93,
00194   137,172,  55,135,  92,95,  34,51,  5,81,  63,118,
00195   72,94,  157,181,  15,68,  41,90,  35,73,  159,183,
00196   115,128,  28,183,  34,45,  149,177,  74,137,  51,110,
00197   25,170,  43,123,  53,109,  4,26,  68,80,  53,171,
00198   48,159,  0,28,  67,176,  87,163,  75,165,  137,162,
00199   150,199,  57,153,  32,93,  25,92,  13,88,  115,167,
00200   16,192,  113,157,  90,125,  104,188,  148,171,  96,101,
00201   22,68,  25,62,  89,161,  24,158,  66,190,  31,34,
00202   106,133,  51,102,  146,163,  31,154,  56,129,  66,157,
00203   38,93,  73,166,  117,174,  93,161,  3,95,  86,181,
00204   131,139,  5,182,  30,66,  0,11,  88,107,  54,101,
00205   36,66,  25,176,  8,38,  31,177,  78,195,  122,179,
00206   42,60,  83,112,  149,161,  184,188,  65,126,  74,198,
00207   38,80,  135,172,  43,156,  148,151,  135,195,  111,184,
00208   10,14,  97,152,       -1,-1};
00210 static const int g2_c[] = {
00211   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,
00212   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,
00213   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,
00214   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,
00215   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,
00216   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,
00217   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,
00218   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,
00219   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,
00220   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,
00221   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,
00222   20,  8,14,20,21,32,39,50,55,88,91,102,120,126,142,159,165,171,175,184,186,
00223   20,  10,15,35,43,50,52,60,77,80,81,85,87,106,120,145,151,155,159,176,196,
00224   20,  10,17,20,33,46,55,60,68,95,96,103,112,117,118,120,123,127,141,147,179,
00225   20,  9,34,41,52,56,72,73,100,102,116,124,131,138,155,157,158,172,173,182,183,
00226   20,  0,14,16,27,29,44,70,95,101,104,115,127,140,158,161,168,170,173,181,189,
00227   20,  6,14,17,18,23,27,50,51,83,84,93,107,108,116,122,136,154,159,172,185,
00228   20,  11,16,17,21,32,38,45,49,55,56,84,88,102,123,126,133,173,189,195,198,
00229   20,  0,14,21,29,30,40,63,67,93,98,116,122,131,140,150,152,174,178,183,190,
00230   20,  8,14,28,36,44,65,72,79,84,111,114,124,130,134,140,158,182,185,193,197,
00231   20,  9,10,12,17,28,42,46,50,57,62,90,117,132,149,168,176,178,182,187,188,
00232   20,  2,4,22,27,31,32,65,74,108,117,132,142,153,159,160,178,180,187,192,195,
00233   20,  2,4,7,21,56,64,67,100,103,130,135,140,147,151,156,161,167,191,193,196,
00234   20,  6,18,24,30,50,51,67,82,84,88,93,95,106,113,138,146,168,187,190,198,
00235   20,  28,37,44,98,99,107,112,119,129,132,135,151,156,167,168,179,182,190,198,199,
00236   15,  4,37,61,64,67,77,93,103,105,118,136,159,169,177,193,
00237   15,  17,44,53,61,82,90,95,103,107,122,124,145,169,186,190,
00238   15,  21,54,80,100,110,120,126,127,132,142,149,150,162,181,186,
00239   15,  3,7,21,22,40,41,82,94,96,98,126,140,143,147,152,
00240   15,  4,14,58,66,80,100,107,111,126,133,140,141,148,155,167,
00241   15,  31,38,44,48,59,74,75,77,100,105,139,168,171,182,187,
00242   15,  0,5,55,62,66,67,74,84,92,128,160,163,188,189,195,
00243   15,  0,36,55,73,80,96,121,133,167,173,190,191,193,195,198,
00244   15,  21,33,41,43,52,62,69,77,88,110,114,118,139,142,187,
00245   15,  12,14,23,29,44,58,67,74,124,149,150,156,167,171,183,
00246   15,  22,33,36,48,60,63,90,92,107,108,137,140,144,165,193,
00247   15,  11,24,40,45,49,59,72,123,125,132,151,161,167,179,184,
00248   15,  4,19,20,48,61,76,98,106,136,147,155,177,183,191,192,
00249   15,  17,22,28,35,55,74,86,90,98,106,121,138,168,190,195,
00250   15,  24,30,35,44,55,63,80,120,128,130,148,160,163,166,192,
00251   15,  20,30,59,64,69,94,104,106,139,140,144,147,156,161,199,
00252   15,  13,30,38,49,54,61,86,95,103,105,131,148,156,162,180,
00253   15,  2,25,34,41,46,63,69,81,91,113,139,159,186,188,190,
00254   15,  1,6,14,35,47,50,66,81,90,136,137,152,156,168,195,
00255   15,  34,37,47,52,94,100,104,105,107,131,147,171,186,191,192,
00256   15,  9,14,29,37,109,125,137,142,145,147,151,159,167,178,192,
00257   15,  13,45,60,62,78,99,104,118,142,143,156,179,189,191,197,
00258   15,  3,15,23,33,66,71,82,89,99,110,113,135,143,158,171,
00259   15,  27,39,101,102,118,133,134,138,141,144,145,148,165,169,189,
00260   15,  12,18,20,36,50,51,53,76,86,120,141,176,178,186,198,
00261   10,  6,8,17,77,109,112,115,124,129,193,
00262   10,  21,31,51,58,86,112,117,126,127,143,
00263   10,  10,74,87,108,123,134,157,180,186,190,
00264   10,  13,14,15,44,67,118,133,142,146,193,
00265   10,  40,44,46,66,73,128,141,161,174,192,
00266   5,  25,117,163,165,192,
00267   5,  40,46,105,121,134,
00268   5,  3,12,56,90,126,
00269   5,  13,95,98,120,188,
00270   5,  3,98,111,128,194,
00271   5,  4,21,51,65,73,
00272   5,  36,106,124,132,197,
00273   5,  5,35,57,91,144,
00274   5,  0,19,122,177,190,
00275   5,  85,98,111,113,134,
00276   5,  49,85,107,139,149,
00277   5,  54,88,102,111,172,
00278   5,  41,74,115,170,184,
00279   5,  33,70,123,151,159,
00280   5,  50,82,117,123,163,
00281   -1};
00282 
00284 static const GraphColorSpec g2 = {
00285   200, g2_e, g2_c
00286 };
00288 
00295 class GraphColor : public Example {
00296 private:
00297   const GraphColorSpec& g;
00299   IntVarArray v;
00301   IntVar m;
00302 public:
00304   GraphColor(const Options& opt)
00305     : g(opt.size == 1 ? g2 : g1), 
00306       v(this,g.n_v,0,g.n_v), 
00307       m(this,0,g.n_v) {
00308     for (int i = g.n_v; i--; )
00309       rel(this, v[i], IRT_LQ, m);
00310     for (int i = 0; g.e[i] != -1; i += 2)
00311       rel(this, v[g.e[i]], IRT_NQ, v[g.e[i+1]]);
00312 
00313     const int* c = g.c;
00314     for (int i = *c++; i--; c++)
00315       rel(this, v[*c], IRT_EQ, i);
00316     while (*c != -1) {
00317       IntVarArgs x(*c); c++;
00318       for (int i = x.size(); i--; c++)
00319         x[i] = v[*c];
00320       distinct(this, x, opt.icl);
00321     }
00322     IntVarArgs ma(1);
00323     ma[0] = m;
00324     branch(this, ma, BVAR_NONE, BVAL_MIN);
00325     if (opt.naive) {
00326       branch(this, v, BVAR_SIZE_MIN, BVAL_MIN);
00327     } else {
00328       branch(this, v, BVAR_DEGREE_MAX, BVAL_MIN);
00329     }
00330   }
00332   GraphColor(bool share, GraphColor& s) : Example(share,s), g(s.g) {
00333     v.update(this, share, s.v);
00334     m.update(this, share, s.m);
00335   }
00337   virtual Space*
00338   copy(bool share) {
00339     return new GraphColor(share,*this);
00340   }
00342   virtual void
00343   print(void) {
00344     std::cout << "\tm = " << m << std::endl
00345               << "\tv[] = {";
00346     for (int i = 0; i < v.size(); i++) {
00347       std::cout << v[i] << ", ";
00348       if ((i+1) % 15 == 0)
00349         std::cout << std::endl << "\t       ";
00350     }
00351     std::cout << "};" << std::endl;
00352   }
00353 };
00354 
00355 
00359 int
00360 main(int argc, char** argv) {
00361   Options opt("GraphColor");
00362   opt.naive      = false;
00363   opt.icl        = ICL_DOM;
00364   opt.iterations = 5;
00365   opt.c_d        = 10;
00366   opt.parse(argc,argv);
00367   Example::run<GraphColor,DFS>(opt);
00368   return 0;
00369 }
00370 
00371 // STATISTICS: example-any
00372