Generated on Mon Nov 30 23:53:18 2009 for Gecode by doxygen 1.6.1

steiner.cpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Guido Tack <tack@gecode.org>
00005  *
00006  *  Copyright:
00007  *     Guido Tack, 2004
00008  *
00009  *  Last modified:
00010  *     $Date: 2009-05-14 19:26:10 +0200 (Thu, 14 May 2009) $ by $Author: tack $
00011  *     $Revision: 9116 $
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/set.hh>
00041 
00042 using namespace Gecode;
00043 
00052 class Steiner : public Script {
00053 public:
00054 
00056   enum {
00057     MODEL_NONE,   
00058     MODEL_MATCHING, 
00059     MODEL_SEQ 
00060   };
00061 
00063   int n;
00065   int noOfTriples;
00066 
00068   SetVarArray triples;
00069 
00071   Steiner(const SizeOptions& opt)
00072     : n(opt.size()), noOfTriples((n*(n-1))/6),
00073       triples(*this, noOfTriples, IntSet::empty, 1, n, 3, 3) {
00074 
00075     for (int i=0; i<noOfTriples; i++) {
00076       for (int j=i+1; j<noOfTriples; j++) {
00077         SetVar x = triples[i];
00078         SetVar y = triples[j];
00079 
00080         SetVar atmostOne(*this,IntSet::empty,1,n,0,1);
00081         cardinality(*this, atmostOne,0,1);
00082         rel(*this, x, SOT_INTER, y, SRT_EQ, atmostOne);
00083 
00084         IntVar x1(*this,1,n);
00085         IntVar x2(*this,1,n);
00086         IntVar x3(*this,1,n);
00087         IntVar y1(*this,1,n);
00088         IntVar y2(*this,1,n);
00089         IntVar y3(*this,1,n);
00090 
00091         if (opt.model() == MODEL_NONE) {
00092           /* Naive alternative:
00093            * just including the ints in the set
00094            */
00095           rel(*this, x, SRT_SUP, x1);
00096           rel(*this, x, SRT_SUP, x2);
00097           rel(*this, x, SRT_SUP, x3);
00098           rel(*this, y, SRT_SUP, y1);
00099           rel(*this, y, SRT_SUP, y2);
00100           rel(*this, y, SRT_SUP, y3);
00101 
00102         } else  if (opt.model() == MODEL_MATCHING) {
00103           /* Smart alternative:
00104            * Using matching constraints
00105            */
00106 
00107           IntVarArgs xargs(3);
00108           xargs[0] = x1; xargs[1] = x2; xargs[2] = x3;
00109           channel(*this, xargs, x);
00110 
00111           IntVarArgs yargs(3);
00112           yargs[0] = y1; yargs[1] = y2; yargs[2] = y3;
00113           channel(*this, yargs, y);
00114         } else if (opt.model() == MODEL_SEQ) {
00115           SetVar tmp20(*this,IntSet::empty,1,n);
00116           SetVar tmp21(*this,IntSet::empty,1,n);
00117           SetVar tmp22(*this,IntSet::empty,1,n);
00118           SetVar tmp23(*this,IntSet::empty,1,n);
00119           SetVar tmp24(*this,IntSet::empty,1,n);
00120           SetVar tmp25(*this,IntSet::empty,1,n);
00121           rel(*this, tmp20, SRT_EQ, x1);
00122           rel(*this, tmp21, SRT_EQ, x2);
00123           rel(*this, tmp22, SRT_EQ, x3);
00124           rel(*this, tmp23, SRT_EQ, y1);
00125           rel(*this, tmp24, SRT_EQ, y2);
00126           rel(*this, tmp25, SRT_EQ, y3);
00127           SetVarArgs xargs(3);
00128           xargs[0] = tmp20; xargs[1] = tmp21; xargs[2] = tmp22;
00129           SetVarArgs yargs(3);
00130           yargs[0] = tmp23; yargs[1] = tmp24; yargs[2] = tmp25;
00131           sequence(*this,xargs,x);
00132           sequence(*this,yargs,y);
00133         }
00134 
00135         /* Breaking symmetries */
00136 
00137         rel(*this, x1,IRT_LE,x2);
00138         rel(*this, x2,IRT_LE,x3);
00139         rel(*this, x1,IRT_LE,x3);
00140 
00141         rel(*this, y1,IRT_LE,y2);
00142         rel(*this, y2,IRT_LE,y3);
00143         rel(*this, y1,IRT_LE,y3);
00144 
00145         IntArgs ia(6,(n+1)*(n+1),n+1,1,-(n+1)*(n+1),-(n+1),-1);
00146         IntVarArgs iva(6);
00147         iva[0]=x1; iva[1]=x2; iva[2]=x3;
00148         iva[3]=y1; iva[4]=y2; iva[5]=y3;
00149         linear(*this, ia, iva, IRT_LE, 0);
00150       }
00151     }
00152 
00153     branch(*this, triples, SET_VAR_NONE, SET_VAL_MIN_INC);
00154   }
00155 
00157   virtual void
00158   print(std::ostream& os) const {
00159     for (int i=0; i<noOfTriples; i++) {
00160       os << "\t[" << i << "] = " << triples[i] << std::endl;
00161     }
00162   }
00163 
00165   Steiner(bool share, Steiner& s) : Script(share,s), n(s.n), noOfTriples(s.noOfTriples) {
00166     triples.update(*this, share, s.triples);
00167   }
00169   virtual Space*
00170   copy(bool share) {
00171     return new Steiner(share,*this);
00172   }
00173 
00174 };
00175 
00179 int
00180 main(int argc, char* argv[]) {
00181   SizeOptions opt("Steiner");
00182   opt.model(Steiner::MODEL_NONE);
00183   opt.model(Steiner::MODEL_NONE, "rel", "Use simple relation constraints");
00184   opt.model(Steiner::MODEL_MATCHING, "matching", "Use matching constraints");
00185   opt.model(Steiner::MODEL_SEQ, "sequence", "Use sequence constraints");
00186   opt.size(9);
00187   opt.iterations(20);
00188   opt.parse(argc,argv);
00189   Script::run<Steiner,DFS,SizeOptions>(opt);
00190   return 0;
00191 }
00192 
00193 
00194 // STATISTICS: example-any
00195