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