Generated on Mon May 10 06:46:29 2010 for Gecode by doxygen 1.6.3

photo.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Christian Schulte, 2001
00008  *
00009  *  Last modified:
00010  *     $Date: 2010-04-08 12:35:31 +0200 (Thu, 08 Apr 2010) $ by $Author: schulte $
00011  *     $Revision: 10684 $
00012  *
00013  *  This file is part of Gecode, the generic constraint
00014  *  development environment:
00015  *     http://www.gecode.org
00016  *
00017  *  Permission is hereby granted, free of charge, to any person obtaining
00018  *  a copy of this software and associated documentation files (the
00019  *  "Software"), to deal in the Software without restriction, including
00020  *  without limitation the rights to use, copy, modify, merge, publish,
00021  *  distribute, sublicense, and/or sell copies of the Software, and to
00022  *  permit persons to whom the Software is furnished to do so, subject to
00023  *  the following conditions:
00024  *
00025  *  The above copyright notice and this permission notice shall be
00026  *  included in all copies or substantial portions of the Software.
00027  *
00028  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00029  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00030  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00031  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00032  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00033  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00034  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00035  *
00036  */
00037 
00038 #include <gecode/driver.hh>
00039 #include <gecode/int.hh>
00040 #include <gecode/minimodel.hh>
00041 
00042 using namespace Gecode;
00043 
00045 class PhotoSpec {
00046 public:
00047   const int  n_names; 
00048   const int  n_prefs; 
00049   const int* prefs;   
00050   PhotoSpec(const int n_n, const int n_p, const int* p)
00051     : n_names(n_n), n_prefs(n_p), prefs(p) {}
00052 };
00053 
00055 const int s_prefs[] = {
00056   0,2, 1,4, 2,3, 2,4, 3,0, 4,3, 4,0, 4,1
00057 };
00059 const PhotoSpec p_small(5, 8, s_prefs);
00060 
00062 const int l_prefs[] = {
00063   0,2, 0,4, 0,7, 1,4, 1,8, 2,3, 2,4, 3,0, 3,4,
00064   4,5, 4,0, 5,0, 5,8, 6,2, 6,7, 7,8, 7,6
00065 };
00067 const PhotoSpec p_large(9,17, l_prefs);
00068 
00080 class Photo : public MaximizeScript {
00081 protected:
00083   const PhotoSpec& spec;
00085   IntVarArray      pos;
00087   IntVar           sat;
00088 
00089 public:
00091   enum {
00092     BRANCH_NONE,  
00093     BRANCH_DEGREE 
00094   };
00096   Photo(const SizeOptions& opt) :
00097     spec(opt.size() == 0 ? p_small : p_large),
00098     pos(*this,spec.n_names, 0, spec.n_names-1),
00099     sat(*this,0,spec.n_prefs)
00100   {
00101     BoolVarArgs ful(spec.n_prefs);
00102     // Map preferences to fulfilment
00103     for (int i = spec.n_prefs; i--; ) {
00104       int pa = spec.prefs[2*i+0];
00105       int pb = spec.prefs[2*i+1];
00106       ful[i] = post(*this,
00107                     ~(pos[pb]-pos[pa] == 1) ^
00108                     ~(pos[pa]-pos[pb] == 1));
00109     }
00110     // Sum of fulfilment
00111     linear(*this, ful, IRT_EQ, sat);
00112 
00113     distinct(*this, pos, opt.icl());
00114 
00115     // Break some symmetries
00116     rel(*this, pos[0], IRT_LE, pos[1]);
00117 
00118     if (opt.branching() == BRANCH_NONE) {
00119       branch(*this, pos, INT_VAR_NONE, INT_VAL_MIN);
00120     } else {
00121       branch(*this, pos, tiebreak(INT_VAR_DEGREE_MAX,INT_VAR_SIZE_MIN),
00122              INT_VAL_MIN);
00123     }
00124   }
00125 
00127   Photo(bool share, Photo& s) :
00128     MaximizeScript(share,s), spec(s.spec) {
00129     pos.update(*this, share, s.pos);
00130     sat.update(*this, share, s.sat);
00131   }
00133   virtual Space*
00134   copy(bool share) {
00135     return new Photo(share,*this);
00136   }
00138   virtual void
00139   print(std::ostream& os) const {
00140     os << "\tpos[] = " << pos << std::endl
00141        << "\tsat: " << sat << std::endl;
00142   }
00144   virtual IntVar cost(void) const {
00145     return sat;
00146   }
00147 };
00148 
00152 int
00153 main(int argc, char* argv[]) {
00154   SizeOptions opt("Photo");
00155   opt.solutions(0);
00156   opt.size(1);
00157   opt.iterations(10);
00158   opt.icl(ICL_BND);
00159   opt.branching(Photo::BRANCH_DEGREE);
00160   opt.branching(Photo::BRANCH_NONE, "none");
00161   opt.branching(Photo::BRANCH_DEGREE, "degree");
00162   opt.parse(argc,argv);
00163   MaximizeScript::run<Photo,BAB,SizeOptions>(opt);
00164   return 0;
00165 }
00166 
00167 
00168 // STATISTICS: example-any
00169