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 "examples/support.hh"
00039 #include "gecode/minimodel.hh"
00040
00042 class PhotoSpec {
00043 public:
00044 const int n_names;
00045 const int n_prefs;
00046 const int* prefs;
00047 PhotoSpec(const int n_n, const int n_p, const int* p)
00048 : n_names(n_n), n_prefs(n_p), prefs(p) {}
00049 };
00050
00052 const int s_prefs[] = {
00053 0,2, 1,4, 2,3, 2,4, 3,0, 4,3, 4,0, 4,1
00054 };
00056 const PhotoSpec p_small(5, 8, s_prefs);
00057
00059 const int l_prefs[] = {
00060 0,2, 0,4, 0,7, 1,4, 1,8, 2,3, 2,4, 3,0, 3,4,
00061 4,5, 4,0, 5,0, 5,8, 6,2, 6,7, 7,8, 7,6
00062 };
00064 const PhotoSpec p_large(9,17, l_prefs);
00065
00077 class Photo : public Example {
00078 protected:
00080 const PhotoSpec& spec;
00082 IntVarArray pos;
00084 IntVar sat;
00085
00086 public:
00088 enum {
00089 BRANCH_NONE,
00090 BRANCH_DEGREE
00091 };
00093 Photo(const SizeOptions& opt) :
00094 spec(opt.size() == 0 ? p_small : p_large),
00095 pos(this,spec.n_names, 0, spec.n_names-1),
00096 sat(this,0,spec.n_prefs)
00097 {
00098 BoolVarArgs ful(spec.n_prefs);
00099
00100 for (int i = spec.n_prefs; i--; ) {
00101 int pa = spec.prefs[2*i+0];
00102 int pb = spec.prefs[2*i+1];
00103 ful[i] = post(this,
00104 ~(pos[pb]-pos[pa] == 1) ^
00105 ~(pos[pa]-pos[pb] == 1));
00106 }
00107
00108 linear(this, ful, IRT_EQ, sat);
00109
00110 distinct(this, pos, opt.icl());
00111
00112
00113 rel(this, pos[0], IRT_LE, pos[1]);
00114
00115 if (opt.branching() == BRANCH_NONE) {
00116 branch(this, pos, INT_VAR_NONE, INT_VAL_MIN);
00117 } else {
00118 branch(this, pos, INT_VAR_DEGREE_MAX, INT_VAL_MIN);
00119 }
00120 }
00121
00123 Photo(bool share, Photo& s) :
00124 Example(share,s), spec(s.spec) {
00125 pos.update(this, share, s.pos);
00126 sat.update(this, share, s.sat);
00127 }
00128
00130 virtual Space*
00131 copy(bool share) {
00132 return new Photo(share,*this);
00133 }
00134
00136 virtual void
00137 print(std::ostream& os) {
00138 os << "\tpos[] = " << pos << std::endl
00139 << "\tsat: " << sat << std::endl;
00140 }
00141
00143 void
00144 constrain(Space* s) {
00145 rel(this, sat, IRT_GR, static_cast<Photo*>(s)->sat.val());
00146 }
00147
00148 };
00149
00153 int
00154 main(int argc, char* argv[]) {
00155 SizeOptions opt("Photo");
00156 opt.solutions(0);
00157 opt.size(1);
00158 opt.iterations(10);
00159 opt.icl(ICL_BND);
00160 opt.branching(Photo::BRANCH_DEGREE);
00161 opt.branching(Photo::BRANCH_NONE, "none");
00162 opt.branching(Photo::BRANCH_DEGREE, "degree");
00163 opt.parse(argc,argv);
00164 Example::run<Photo,BAB,SizeOptions>(opt);
00165 return 0;
00166 }
00167
00168
00169
00170