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/minimodel.hh>
00037
00038 using namespace Gecode;
00039
00045 class EFPAOptions : public Options {
00046 private:
00047 Driver::UnsignedIntOption _v;
00048 Driver::UnsignedIntOption _q;
00049 Driver::UnsignedIntOption _l;
00050 Driver::UnsignedIntOption _d;
00051 Driver::StringOption _permutation;
00052
00053 public:
00055 EFPAOptions(const char* s,
00056 int v0 = 5, int q0 = 3, int lambda0 = 2, int d0 = 4)
00057 : Options(s),
00058 _v("v", "number of sequences", v0 ),
00059 _q("q", "number of symbols", q0 ),
00060 _l("l", "sets of symbols per sequence (lambda)", lambda0),
00061 _d("d", "Hamming distance between sequences", d0 ),
00062 _permutation("permutation", "use permutation constraints if d=4",
00063 false)
00064 {
00065
00066 add(_d);
00067 add(_l);
00068 add(_q);
00069 add(_v);
00070 add(_permutation);
00071 add(_symmetry);
00072
00073
00074 _permutation.add(true, "full" );
00075 _permutation.add(false, "none");
00076
00077 _symmetry.add(true, "true" );
00078 _symmetry.add(false, "false");
00079 }
00081 void parse(int& argc, char* argv[]) {
00082 Options::parse(argc,argv);
00083 }
00085 int v(void) const { return _v.value(); }
00087 int q(void) const { return _q.value(); }
00089 int l(void) const { return _l.value(); }
00091 int d(void) const { return _d.value(); }
00092
00094 bool permutation(void) const { return d() == 4 && _permutation.value(); }
00096 bool symmetry(void) const { return _symmetry.value(); }
00097 };
00098
00099
00114 class EFPA : public Script {
00115 protected:
00116 int v;
00117 int q;
00118 int l;
00119 int d;
00120 int n;
00121 int nseqpair;
00122 IntVarArray c;
00123 BoolVarArray diff;
00124
00125 public:
00127 EFPA(const EFPAOptions& opt)
00128 : Script(opt),
00129 v(opt.v()),
00130 q(opt.q()),
00131 l(opt.l()),
00132 d(opt.d()),
00133 n(q*l),
00134 nseqpair((v*(v-1))/2),
00135 c(*this, n*v, 1,q),
00136 diff(*this, n*nseqpair, 0, 1)
00137 {
00138
00139
00140 Matrix<IntVarArray> cm(c, n, v);
00141
00142 Matrix<BoolVarArray> diffm(diff, n, nseqpair);
00143
00144
00145 {
00146 IntArgs values(q);
00147 for (int i = q; i--; ) values[i] = i+1;
00148 IntSet cardinality(l, l);
00149 for (int i = v; i--; )
00150 count(*this, cm.row(i), cardinality, values, opt.ipl());
00151 }
00152
00153
00154 {
00155 int nseqi = 0;
00156 for (int a = 0; a < v; ++a) {
00157 for (int b = a+1; b < v; ++b) {
00158 for (int i = n; i--; ) {
00159 rel(*this, cm(i, a), IRT_NQ, cm(i, b), diffm(i, nseqi));
00160 }
00161 ++nseqi;
00162 }
00163 }
00164 assert(nseqi == nseqpair);
00165 }
00166
00167
00168 {
00169 for (int i = nseqpair; i--; ) {
00170 linear(*this, diffm.row(i), IRT_EQ, d);
00171 }
00172 }
00173
00174
00175 if (opt.symmetry()) {
00176 IntRelType row_less = d==0 ? IRT_EQ : IRT_LE;
00177
00178 for (int r = 0; r<v-1; ++r) {
00179 rel(*this, cm.row(r), row_less, cm.row(r+1));
00180 }
00181
00182 for (int c = 0; c<n-1; ++c) {
00183 rel(*this, cm.col(c), IRT_LQ, cm.col(c+1));
00184 }
00185
00186 int color = 1;
00187 int ncolor = 0;
00188 for (int c = 0; c < n; ++c) {
00189 rel(*this, cm(c, 0), IRT_EQ, color);
00190 if (++ncolor == l) {
00191 ncolor = 0;
00192 ++color;
00193 }
00194 }
00195 }
00196
00197
00198 if (opt.permutation()) {
00199 const int k[][4] = {
00200 {0, 1, 3, 2},
00201 {1, 2, 3, 0},
00202 };
00203 assert(d == 4);
00204
00205 for (int r1 = 0; r1 < v; ++r1) {
00206 for (int r2 = r1+1; r2 < v; ++r2) {
00207 IntVarArgs row1 = cm.row(r1);
00208 IntVarArgs row2 = cm.row(r2);
00209
00210 IntVarArgs perm(d);
00211 for (int i = d; i--; ) perm[i] = IntVar(*this, 0, n-1);
00212
00213 IntVar cform(*this, 0, 1);
00214 BoolVar cformb = channel(*this, cform);
00215
00216
00217
00218 IntVarArgs _p(2*d);
00219 for (int i = 2*d; i--; ) _p[i] = IntVar(*this, 1, q);
00220 Matrix<IntVarArgs> p(_p, d, 2);
00221 for (int i = 0; i < 2; ++i) {
00222 for (int j = 0; j < d; ++j) {
00223 element(*this, row1, perm[k[i][j]], p(j, i));
00224 }
00225 }
00226
00227
00228 for (int i = 0; i < d; ++i) {
00229 IntVar index(*this, 0, 2*d);
00230 rel(*this, cform*d + i == index);
00231 IntVar value(*this, 1, q);
00232 element(*this, _p, index, value);
00233 element(*this, row2, perm[i], value);
00234 }
00235
00236
00237
00238 BoolVarArgs p1b(*this, n, 0, 1);
00239 channel(*this, p1b, perm[0]);
00240 BoolVarArgs p2b(*this, n, 0, 1);
00241 channel(*this, p2b, perm[1]);
00242 BoolVarArgs p3b(*this, n, 0, 1);
00243 channel(*this, p3b, perm[2]);
00244 BoolVarArgs p4b(*this, n, 0, 1);
00245 channel(*this, p4b, perm[3]);
00246 for (int i = n; i--; ) {
00247
00248
00249 rel(*this, (!p1b[i] && !p2b[i] && !p3b[i] && !p4b[i]) ==
00250 (row1[i] == row2[i]));
00251 }
00252
00253
00254
00255 rel(*this, perm[0], IRT_NQ, perm[1]);
00256 rel(*this, perm[2], IRT_NQ, perm[3]);
00257
00258
00259 rel(*this, perm[0], IRT_NQ, perm[2], cformb);
00260 rel(*this, perm[0], IRT_NQ, perm[3], cformb);
00261 rel(*this, perm[1], IRT_NQ, perm[2], cformb);
00262 rel(*this, perm[1], IRT_NQ, perm[3], cformb);
00263
00264 rel(*this, perm[0], IRT_LE, perm[1]);
00265 rel(*this, perm[0], IRT_LE, perm[2]);
00266 rel(*this, perm[0], IRT_LE, perm[3]);
00267
00268 rel(*this, (!cformb) >> (perm[2] < perm[3]));
00269 }
00270 }
00271 }
00272
00273 branch(*this, c, INT_VAR_NONE(), INT_VAL_MIN());
00274 }
00275
00277 virtual void
00278 print(std::ostream& os) const {
00279 Matrix<IntVarArray> cm(c, n, v);
00280 for (int i = 0; i < v; ++i) {
00281 IntVarArgs r = cm.row(i);
00282 os << r << std::endl;
00283 }
00284 os << std::endl;
00285 }
00286
00288 EFPA(EFPA& s)
00289 : Script(s),
00290 v(s.v),
00291 q(s.q),
00292 l(s.l),
00293 d(s.d),
00294 n(s.n),
00295 nseqpair(s.nseqpair)
00296 {
00297 c.update(*this, s.c);
00298 diff.update(*this, s.diff);
00299 }
00301 virtual Space*
00302 copy(void) {
00303 return new EFPA(*this);
00304 }
00305 };
00306
00310 int
00311 main(int argc, char* argv[]) {
00312 EFPAOptions opt("Equidistant Frequency Permutation Arrays");
00313 opt.ipl(IPL_DOM);
00314 opt.parse(argc,argv);
00315
00316 Script::run<EFPA,DFS,EFPAOptions>(opt);
00317 return 0;
00318 }
00319
00320