00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
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
00070
00071
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
00092
00093
00094
00095
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109
00110
00111
00112
00113
00114
00115
00116
00117
00118
00119
00120
00121
00122
00123
00124
00125
00126
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
00181