Generated on Wed Jan 4 17:49:07 2006 for Gecode by doxygen 1.4.6

photo.cc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Christian Schulte <schulte@gecode.org>
00004  *
00005  *  Copyright:
00006  *     Christian Schulte, 2001
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-11-04 22:52:06 +0100 (Fri, 04 Nov 2005) $ by $Author: schulte $
00010  *     $Revision: 2507 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */
00021 
00022 #include "examples/support.hh"
00023 #include "minimodel.hh"
00024 
00026 class PhotoSpec {
00027 public:
00028   const int  n_names; 
00029   const int  n_prefs; 
00030   const int* prefs;   
00031 };
00032 
00034 static const int s_prefs[] = {
00035   0,2, 1,4, 2,3, 2,4, 3,0, 4,3, 4,0, 4,1
00036 };
00038 static const PhotoSpec p_small = { 5, 8, s_prefs};
00039 
00041 static const int l_prefs[] = {
00042   0,2, 0,4, 0,7, 1,4, 1,8, 2,3, 2,4, 3,0, 3,4,
00043   4,5, 4,0, 5,0, 5,8, 6,2, 6,7, 7,8, 7,6
00044 };
00046 static const PhotoSpec p_large = { 9,17, l_prefs };
00047 
00059 class Photo : public Example {
00060 protected:
00062   const PhotoSpec& spec;
00064   IntVarArray      pos;
00066   IntVar           sat;
00067 
00068 public:
00070   Photo(const Options& opt) :
00071     spec(opt.size == 0 ? p_small : p_large),
00072     pos(this,spec.n_names, 0, spec.n_names-1),
00073     sat(this,0,spec.n_prefs)
00074   {
00075     BoolVarArgs ful(spec.n_prefs);
00076     // Map preferences to fulfilment
00077     for (int i = spec.n_prefs; i--; ) {
00078       int pa = spec.prefs[2*i+0];
00079       int pb = spec.prefs[2*i+1];
00080       ful[i] = post(this,
00081                     ~(pos[pb]-pos[pa] == 1) ^
00082                     ~(pos[pa]-pos[pb] == 1));
00083     }
00084     // Sum of fulfilment
00085     {
00086       IntVarArgs eq(spec.n_prefs+1);
00087       IntArgs    c(spec.n_prefs+1);
00088       eq[spec.n_prefs] = sat; c[spec.n_prefs] = -1;
00089       for (int i = spec.n_prefs; i--; ) {
00090         eq[i] = ful[i]; c[i] = 1;
00091       }
00092       linear(this, c, eq, IRT_EQ, 0);
00093     }
00094     distinct(this, pos, opt.icl);
00095 
00096     // Break some symmetries
00097     rel(this, pos[0], IRT_LE, pos[1]);
00098 
00099     branch(this, pos, BVAR_DEGREE_MAX, BVAL_MIN);
00100   }
00101 
00103   Photo(bool share, Photo& s) :
00104     Example(share,s), spec(s.spec) {
00105     pos.update(this, share, s.pos);
00106     sat.update(this, share, s.sat);
00107   }
00108 
00110   virtual Space*
00111   copy(bool share) {
00112     return new Photo(share,*this);
00113   }
00114 
00116   virtual void
00117   print(void) {
00118     std::cout << "\tpos[] = {";
00119     for (int i = 0; i < spec.n_names; i++)
00120       std::cout << pos[i] << ((i<spec.n_names-1)?",":"};\n");
00121     std::cout << "\tsat: " << sat << std::endl;
00122   }
00123 
00125   void
00126   constrain(Space* s) {
00127     rel(this, sat, IRT_GR, static_cast<Photo*>(s)->sat.val());
00128   }
00129 
00130 };
00131 
00135 int
00136 main(int argc, char** argv) {
00137   Options opt("Photo");
00138   opt.solutions  = 0;
00139   opt.size       = 1;
00140   opt.iterations = 10;
00141   opt.icl        = ICL_BND;
00142   opt.parse(argc,argv);
00143   Example::run<Photo,BAB>(opt);
00144   return 0;
00145 }
00146 
00147 
00148 // STATISTICS: example-any
00149