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 #include <gecode/set.hh>
00041
00042 using namespace Gecode;
00043
00052 class Steiner : public Script {
00053 public:
00054
00056 enum {
00057 MODEL_NONE,
00058 MODEL_MATCHING,
00059 MODEL_SEQ
00060 };
00061
00063 int n;
00065 int noOfTriples;
00066
00068 SetVarArray triples;
00069
00071 Steiner(const SizeOptions& opt)
00072 : n(opt.size()), noOfTriples((n*(n-1))/6),
00073 triples(*this, noOfTriples, IntSet::empty, 1, n, 3, 3) {
00074
00075 for (int i=0; i<noOfTriples; i++) {
00076 for (int j=i+1; j<noOfTriples; j++) {
00077 SetVar x = triples[i];
00078 SetVar y = triples[j];
00079
00080 SetVar atmostOne(*this,IntSet::empty,1,n,0,1);
00081 cardinality(*this, atmostOne,0,1);
00082 rel(*this, x, SOT_INTER, y, SRT_EQ, atmostOne);
00083
00084 IntVar x1(*this,1,n);
00085 IntVar x2(*this,1,n);
00086 IntVar x3(*this,1,n);
00087 IntVar y1(*this,1,n);
00088 IntVar y2(*this,1,n);
00089 IntVar y3(*this,1,n);
00090
00091 if (opt.model() == MODEL_NONE) {
00092
00093
00094
00095 rel(*this, x, SRT_SUP, x1);
00096 rel(*this, x, SRT_SUP, x2);
00097 rel(*this, x, SRT_SUP, x3);
00098 rel(*this, y, SRT_SUP, y1);
00099 rel(*this, y, SRT_SUP, y2);
00100 rel(*this, y, SRT_SUP, y3);
00101
00102 } else if (opt.model() == MODEL_MATCHING) {
00103
00104
00105
00106
00107 IntVarArgs xargs(3);
00108 xargs[0] = x1; xargs[1] = x2; xargs[2] = x3;
00109 channel(*this, xargs, x);
00110
00111 IntVarArgs yargs(3);
00112 yargs[0] = y1; yargs[1] = y2; yargs[2] = y3;
00113 channel(*this, yargs, y);
00114 } else if (opt.model() == MODEL_SEQ) {
00115 SetVar tmp20(*this,IntSet::empty,1,n);
00116 SetVar tmp21(*this,IntSet::empty,1,n);
00117 SetVar tmp22(*this,IntSet::empty,1,n);
00118 SetVar tmp23(*this,IntSet::empty,1,n);
00119 SetVar tmp24(*this,IntSet::empty,1,n);
00120 SetVar tmp25(*this,IntSet::empty,1,n);
00121 rel(*this, tmp20, SRT_EQ, x1);
00122 rel(*this, tmp21, SRT_EQ, x2);
00123 rel(*this, tmp22, SRT_EQ, x3);
00124 rel(*this, tmp23, SRT_EQ, y1);
00125 rel(*this, tmp24, SRT_EQ, y2);
00126 rel(*this, tmp25, SRT_EQ, y3);
00127 SetVarArgs xargs(3);
00128 xargs[0] = tmp20; xargs[1] = tmp21; xargs[2] = tmp22;
00129 SetVarArgs yargs(3);
00130 yargs[0] = tmp23; yargs[1] = tmp24; yargs[2] = tmp25;
00131 sequence(*this,xargs,x);
00132 sequence(*this,yargs,y);
00133 }
00134
00135
00136
00137 rel(*this, x1,IRT_LE,x2);
00138 rel(*this, x2,IRT_LE,x3);
00139 rel(*this, x1,IRT_LE,x3);
00140
00141 rel(*this, y1,IRT_LE,y2);
00142 rel(*this, y2,IRT_LE,y3);
00143 rel(*this, y1,IRT_LE,y3);
00144
00145 IntArgs ia(6,(n+1)*(n+1),n+1,1,-(n+1)*(n+1),-(n+1),-1);
00146 IntVarArgs iva(6);
00147 iva[0]=x1; iva[1]=x2; iva[2]=x3;
00148 iva[3]=y1; iva[4]=y2; iva[5]=y3;
00149 linear(*this, ia, iva, IRT_LE, 0);
00150 }
00151 }
00152
00153 branch(*this, triples, SET_VAR_NONE, SET_VAL_MIN_INC);
00154 }
00155
00157 virtual void
00158 print(std::ostream& os) const {
00159 for (int i=0; i<noOfTriples; i++) {
00160 os << "\t[" << i << "] = " << triples[i] << std::endl;
00161 }
00162 }
00163
00165 Steiner(bool share, Steiner& s) : Script(share,s), n(s.n), noOfTriples(s.noOfTriples) {
00166 triples.update(*this, share, s.triples);
00167 }
00169 virtual Space*
00170 copy(bool share) {
00171 return new Steiner(share,*this);
00172 }
00173
00174 };
00175
00179 int
00180 main(int argc, char* argv[]) {
00181 SizeOptions opt("Steiner");
00182 opt.model(Steiner::MODEL_NONE);
00183 opt.model(Steiner::MODEL_NONE, "rel", "Use simple relation constraints");
00184 opt.model(Steiner::MODEL_MATCHING, "matching", "Use matching constraints");
00185 opt.model(Steiner::MODEL_SEQ, "sequence", "Use sequence constraints");
00186 opt.size(9);
00187 opt.iterations(20);
00188 opt.parse(argc,argv);
00189 Script::run<Steiner,DFS,SizeOptions>(opt);
00190 return 0;
00191 }
00192
00193
00194
00195