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:
00055 enum {
00056 MODEL_NONE,
00057 MODEL_MATCHING,
00058 MODEL_SEQ
00059 };
00061 int n;
00063 int noOfTriples;
00064
00066 SetVarArray triples;
00067
00069 Steiner(const SizeOptions& opt)
00070 : n(opt.size()), noOfTriples((n*(n-1))/6),
00071 triples(*this, noOfTriples, IntSet::empty, 1, n, 3, 3) {
00072
00073 for (int i=0; i<noOfTriples; i++) {
00074 for (int j=i+1; j<noOfTriples; j++) {
00075 SetVar x = triples[i];
00076 SetVar y = triples[j];
00077
00078 SetVar atmostOne(*this,IntSet::empty,1,n,0,1);
00079 rel(*this, (x & y) == atmostOne);
00080
00081 IntVar x1(*this,1,n);
00082 IntVar x2(*this,1,n);
00083 IntVar x3(*this,1,n);
00084 IntVar y1(*this,1,n);
00085 IntVar y2(*this,1,n);
00086 IntVar y3(*this,1,n);
00087
00088 if (opt.model() == MODEL_NONE) {
00089
00090
00091
00092 rel(*this, singleton(x1) <= x);
00093 rel(*this, singleton(x2) <= x);
00094 rel(*this, singleton(x3) <= x);
00095 rel(*this, singleton(y1) <= y);
00096 rel(*this, singleton(y2) <= y);
00097 rel(*this, singleton(y3) <= y);
00098
00099 } else if (opt.model() == MODEL_MATCHING) {
00100
00101
00102
00103
00104 channelSorted(*this, IntVarArgs()<<x1<<x2<<x3, x);
00105 channelSorted(*this, IntVarArgs()<<y1<<y2<<y3, y);
00106 } else if (opt.model() == MODEL_SEQ) {
00107 SetVar sx1 = expr(*this, singleton(x1));
00108 SetVar sx2 = expr(*this, singleton(x2));
00109 SetVar sx3 = expr(*this, singleton(x3));
00110 SetVar sy1 = expr(*this, singleton(y1));
00111 SetVar sy2 = expr(*this, singleton(y2));
00112 SetVar sy3 = expr(*this, singleton(y3));
00113 sequence(*this,SetVarArgs()<<sx1<<sx2<<sx3,x);
00114 sequence(*this,SetVarArgs()<<sy1<<sy2<<sy3,y);
00115 }
00116
00117
00118 rel(*this, x1 < x2);
00119 rel(*this, x2 < x3);
00120 rel(*this, x1 < x3);
00121
00122 rel(*this, y1 < y2);
00123 rel(*this, y2 < y3);
00124 rel(*this, y1 < y3);
00125
00126 linear(*this, IntArgs(6,(n+1)*(n+1),n+1,1,-(n+1)*(n+1),-(n+1),-1),
00127 IntVarArgs()<<x1<<x2<<x3<<y1<<y2<<y3, IRT_LE, 0);
00128 }
00129 }
00130
00131 branch(*this, triples, SET_VAR_NONE, SET_VAL_MIN_INC);
00132 }
00134 virtual void
00135 print(std::ostream& os) const {
00136 for (int i=0; i<noOfTriples; i++) {
00137 os << "\t[" << i << "] = " << triples[i] << std::endl;
00138 }
00139 }
00141 Steiner(bool share, Steiner& s) : Script(share,s), n(s.n), noOfTriples(s.noOfTriples) {
00142 triples.update(*this, share, s.triples);
00143 }
00145 virtual Space*
00146 copy(bool share) {
00147 return new Steiner(share,*this);
00148 }
00149 };
00150
00154 int
00155 main(int argc, char* argv[]) {
00156 SizeOptions opt("Steiner");
00157 opt.model(Steiner::MODEL_NONE);
00158 opt.model(Steiner::MODEL_NONE, "rel", "Use simple relation constraints");
00159 opt.model(Steiner::MODEL_MATCHING, "matching", "Use matching constraints");
00160 opt.model(Steiner::MODEL_SEQ, "sequence", "Use sequence constraints");
00161 opt.size(9);
00162 opt.iterations(20);
00163 opt.parse(argc,argv);
00164 Script::run<Steiner,DFS,SizeOptions>(opt);
00165 return 0;
00166 }
00167
00168
00169
00170