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, {x1,x2,x3}, x);
00101 channelSorted(*this, {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,{sx1,sx2,sx3},x);
00110 sequence(*this,{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,
00123 {(n+1)*(n+1), n+1, 1, -(n+1)*(n+1), -(n+1), -1},
00124 {x1, x2, x3, y1, y2, y3},
00125 IRT_LE, 0);
00126 }
00127 }
00128
00129 branch(*this, triples, SET_VAR_NONE(), SET_VAL_MIN_INC());
00130 }
00132 virtual void
00133 print(std::ostream& os) const {
00134 for (int i=0; i<noOfTriples; i++) {
00135 os << "\t[" << i << "] = " << triples[i] << std::endl;
00136 }
00137 }
00139 Steiner(Steiner& s) : Script(s), n(s.n), noOfTriples(s.noOfTriples) {
00140 triples.update(*this, s.triples);
00141 }
00143 virtual Space*
00144 copy(void) {
00145 return new Steiner(*this);
00146 }
00147 };
00148
00152 int
00153 main(int argc, char* argv[]) {
00154 SizeOptions opt("Steiner");
00155 opt.model(Steiner::MODEL_NONE);
00156 opt.model(Steiner::MODEL_NONE, "rel", "Use simple relation constraints");
00157 opt.model(Steiner::MODEL_MATCHING, "matching", "Use matching constraints");
00158 opt.model(Steiner::MODEL_SEQ, "sequence", "Use sequence constraints");
00159 opt.size(9);
00160 opt.iterations(20);
00161 opt.parse(argc,argv);
00162 Script::run<Steiner,DFS,SizeOptions>(opt);
00163 return 0;
00164 }
00165
00166
00167
00168