Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

steiner.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Guido Tack <tack@gecode.org>
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2004
00008  *     Christian Schulte, 2004
00009  *
00010  *  Last modified:
00011  *     $Date: 2005-11-14 09:32:41 +0100 (Mon, 14 Nov 2005) $ by $Author: tack $
00012  *     $Revision: 2550 $
00013  *
00014  *  This file is part of Gecode, the generic constraint
00015  *  development environment:
00016  *     http://www.gecode.org
00017  *
00018  *  See the file "LICENSE" for information on usage and
00019  *  redistribution of this file, and for a
00020  *     DISCLAIMER OF ALL WARRANTIES.
00021  *
00022  */
00023 
00024 #include "set.hh"
00025 #include "examples/support.hh"
00026 
00035 class Steiner : public Example {
00036 public:
00037 
00038   int n;
00039   int n1;
00040   int n1n1;
00041   int len;
00042 
00043   SetVarArray root;
00044 
00045   Steiner(const Options& o)
00046     : n(o.size),
00047       n1(n+1), n1n1(n1*n1), len((n*(n-1))/6),
00048       root(this,len, IntSet::empty, 1, n, 3, 3) {
00049 
00050     if (!o.naive)
00051       atmostOne(this, root, 3);
00052 
00053     for (int i=0; i<len; i++) {
00054       for (int j=i+1; j<len; j++) {
00055         SetVar x = root[i];
00056         SetVar y = root[j];
00057 
00058         SetVar atmostOne(this,IntSet::empty,1,n,0,1);
00059         cardinality(this, atmostOne,0,1);
00060         rel(this, x, SOT_INTER, y, SRT_EQ, atmostOne);
00061 
00062         IntVar x1(this,1,n);
00063         IntVar x2(this,1,n);
00064         IntVar x3(this,1,n);
00065         IntVar y1(this,1,n);
00066         IntVar y2(this,1,n);
00067         IntVar y3(this,1,n);
00068 
00069         /* First alternative:
00070          * Using "the" and sequence constraints
00071          * Gives best propagation
00072          */
00073         {
00074           SetVarArray temp2(this,6);
00075           rel(this, temp2[0], SRT_EQ, x1);
00076           rel(this, temp2[1], SRT_EQ, x2);
00077           rel(this, temp2[2], SRT_EQ, x3);
00078           rel(this, temp2[3], SRT_EQ, y1);
00079           rel(this, temp2[4], SRT_EQ, y2);
00080           rel(this, temp2[5], SRT_EQ, y3);
00081 
00082           SetVarArgs xargs(3);
00083           xargs[0]=temp2[0]; xargs[1]=temp2[1]; xargs[2]=temp2[2];
00084           SetVarArgs yargs(3);
00085           yargs[0]=temp2[3]; yargs[1]=temp2[4]; yargs[2]=temp2[5];
00086           
00087           sequentialUnion(this, xargs,x);
00088           sequentialUnion(this, yargs,y);
00089         }
00090 
00091         /* Second alternative:
00092          * Using minElement,include,maxElement
00093          */
00094 
00095         //         {
00096         //           IntVarArgs xargs(3);
00097         //           xargs[0] = x1; xargs[1] = x2; xargs[2] = x3;
00098         //           match(this, x,xargs);
00099         
00100         //           IntVarArgs yargs(3);
00101         //           yargs[0] = y1; yargs[1] = y2; yargs[2] = y3;
00102         //           match(this, y,yargs);
00103         
00104         //           minElement(this,x,x1);
00105         //           rel(this,x,SRT_SUP,x2);
00106         //           maxElement(this,x,x3);
00107         
00108         //           minElement(this,y,y1);
00109         //           rel(this,y,SRT_SUP,y2);
00110         //           maxElement(this,y,y3);
00111         
00112         //         }
00113 
00114         /* Third alternative:
00115          * using just include
00116          */
00117         //      {
00118         //        rel(this, x, SRT_SUP, x1);
00119         //        rel(this, x, SRT_SUP, x2);
00120         //        rel(this, x, SRT_SUP, x3);
00121         //        rel(this, y, SRT_SUP, y1);
00122         //        rel(this, y, SRT_SUP, y2);
00123         //        rel(this, y, SRT_SUP, y3);
00124         //      }
00125         
00126         /* Breaking symmetries */
00127 
00128         rel(this, x1,IRT_LE,x2);
00129         rel(this, x2,IRT_LE,x3);
00130         rel(this, x1,IRT_LE,x3);
00131         
00132         rel(this, y1,IRT_LE,y2);
00133         rel(this, y2,IRT_LE,y3);
00134         rel(this, y1,IRT_LE,y3);
00135         
00136         IntArgs ia(6,n1n1,n1,1,-n1n1,-n1,-1);
00137         IntVarArgs iva(6);
00138         iva[0]=x1; iva[1]=x2; iva[2]=x3;
00139         iva[3]=y1; iva[4]=y2; iva[5]=y3;
00140         linear(this, ia, iva, IRT_LE, 0);
00141         
00142       }
00143     }
00144     
00145     branch(this, root, SETBVAR_NONE, SETBVAL_MIN);
00146   }
00147 
00148   Steiner(bool share, Steiner& s) : Example(share,s),
00149                                     n(s.n), n1(s.n1), n1n1(s.n1n1), len(s.len)
00150   {
00151     root.update(this, share, s.root);
00152   }
00153 
00154   virtual Space*
00155   copy(bool share) {
00156     return new Steiner(share,*this);
00157   }
00158 
00159   virtual void
00160   print(void) {
00161     for (int i=0; i<len; i++) {
00162       std::cout << "\t[" << i << "]" << root[i] << std::endl;
00163     }
00164   }
00165 
00166 };
00167 
00168 int
00169 main(int argc, char** argv) {
00170   Options o("Steiner");
00171   o.size = 9;
00172   o.naive = false;
00173   o.iterations = 20;
00174   o.parse(argc,argv);
00175   Example::run<Steiner,DFS>(o);
00176   return 0;
00177 }
00178 
00179 
00180 // STATISTICS: example-any
00181