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