Generated on Thu Mar 22 10:39:35 2012 for Gecode by doxygen 1.6.3

circuit.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, 2007
00008  *
00009  *  Last modified:
00010  *     $Date: 2011-06-01 18:12:15 +0200 (Wed, 01 Jun 2011) $ by $Author: schulte $
00011  *     $Revision: 12036 $
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 "test/int.hh"
00039 #include <gecode/minimodel.hh>
00040 
00041 namespace Test { namespace Int {
00042 
00044    namespace Circuit {
00045 
00051 
00052      class Circuit : public Test {
00053      private:
00055        int offset;
00056      public:
00058        Circuit(int n, int min, int max, int off, Gecode::IntConLevel icl)
00059          : Test("Circuit::" + str(icl) + "::" + str(n) + "::" + str(off),
00060                    n,min,max,false,icl), offset(off) {
00061          contest = CTL_NONE;
00062        }
00064        virtual bool solution(const Assignment& x) const {
00065          for (int i=x.size(); i--; )
00066            if ((x[i] < 0) || (x[i] > x.size()-1))
00067              return false;
00068          int reachable = 0;
00069          {
00070            int j=0;
00071            for (int i=x.size(); i--; ) {
00072              j=x[j]; reachable |= (1 << j);
00073            }
00074          }
00075          for (int i=x.size(); i--; )
00076            if (!(reachable & (1 << i)))
00077              return false;
00078          return true;
00079        }
00081        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00082          if (offset > 0) {
00083            Gecode::IntVarArgs xx(x.size());
00084            for (int i=x.size(); i--;)
00085              xx[i] = Gecode::expr(home, x[i]+offset);
00086            Gecode::circuit(home, offset, xx, icl);
00087          } else {
00088            Gecode::circuit(home, x, icl);
00089          }
00090        }
00091      };
00092 
00094      class Path : public Test {
00095      private:
00097        int offset;
00098      public:
00100        Path(int n, int min, int max, int off, Gecode::IntConLevel icl)
00101          : Test("Path::" + str(icl) + "::" + str(n) + "::" + str(off),
00102                 n+2,min,max,false,icl), offset(off) {
00103          contest = CTL_NONE;
00104        }
00106        virtual bool solution(const Assignment& x) const {
00107          int n = x.size() - 2;
00108          int s = x[n];
00109          int e = x[n+1];
00110          if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
00111            return false;
00112          for (int i=n; i--; )
00113            if ((i != e) && ((x[i] < 0) || (x[i] > n)))
00114              return false;
00115          int reachable = (1 << s);
00116          {
00117            int j=s;
00118            for (int i=n; i--; ) {
00119              j=x[j]; reachable |= (1 << j);
00120            }
00121          }
00122          for (int i=n; i--; )
00123            if (!(reachable & (1 << i)))
00124              return false;
00125          return true;
00126        }
00128        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00129          int n = x.size() - 2;
00130          Gecode::IntVarArgs xx(n);
00131          if (offset > 0) {
00132            for (int i=n; i--;)
00133              xx[i] = Gecode::expr(home, x[i]+offset);
00134            Gecode::path(home, offset, xx,
00135                         Gecode::expr(home, x[n]+offset),
00136                         Gecode::expr(home, x[n+1]+offset),icl);
00137          } else {
00138            for (int i=n; i--;)
00139              xx[i] = x[i];
00140            Gecode::path(home, xx, x[n], x[n+1], icl);
00141          }
00142        }
00143      };
00144 
00146      class CircuitCost : public Test {
00147      private:
00149        int offset;
00150      public:
00152        CircuitCost(int n, int min, int max, int off, Gecode::IntConLevel icl)
00153          : Test("Circuit::Cost::"+str(icl)+"::"+str(n)+"::"+str(off),
00154                 n+1,min,max,false,icl), offset(off) {
00155          contest = CTL_NONE;
00156        }
00158        virtual bool solution(const Assignment& x) const {
00159          int n=x.size()-1;
00160          for (int i=n; i--; )
00161            if ((x[i] < 0) || (x[i] > n-1))
00162              return false;
00163          int reachable = 0;
00164          {
00165            int j=0;
00166            for (int i=n; i--; ) {
00167              j=x[j]; reachable |= (1 << j);
00168            }
00169          }
00170          for (int i=n; i--; )
00171            if (!(reachable & (1 << i)))
00172              return false;
00173          int c=0;
00174          for (int i=n; i--; )
00175            c += x[i];
00176          return c == x[n];
00177        }
00179        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00180          using namespace Gecode;
00181          int n=x.size()-1;
00182          IntArgs c(n*n);
00183          for (int i=0; i<n; i++)
00184            for (int j=0; j<n; j++)
00185              c[i*n+j]=j;
00186          IntVarArgs y(n);
00187          if (offset > 0) {
00188            for (int i=n; i--;)
00189              y[i] = Gecode::expr(home, x[i]+offset);
00190            Gecode::circuit(home, c, offset, y, x[n], icl);
00191          } else {
00192            for (int i=0; i<n; i++)
00193              y[i]=x[i];
00194            circuit(home, c, y, x[n], icl);
00195          }
00196        }
00197      };
00198 
00200      class PathCost : public Test {
00201      private:
00203        int offset;
00204      public:
00206        PathCost(int n, int min, int max, int off, Gecode::IntConLevel icl)
00207          : Test("Path::Cost::"+str(icl)+"::"+str(n)+"::"+str(off),
00208                 n+3,min,max,false,icl), offset(off) {
00209          contest = CTL_NONE;
00210        }
00212        virtual bool solution(const Assignment& x) const {
00213          int n = x.size() - 3;
00214          int s = x[n];
00215          int e = x[n+1];
00216          int c = x[n+2] + n;
00217          if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
00218            return false;
00219          for (int i=n; i--; )
00220            if ((i != e) && ((x[i] < 0) || (x[i] > n)))
00221              return false;
00222          int reachable = (1 << s);
00223          {
00224            int j=s;
00225            for (int i=n; i--; ) {
00226              j=x[j]; reachable |= (1 << j);
00227            }
00228          }
00229          for (int i=n; i--; )
00230            if (!(reachable & (1 << i)))
00231              return false;
00232          for (int i=n; i--; )
00233            c -= x[i];
00234          return c == 0;
00235        }
00237        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00238          using namespace Gecode;
00239          int n=x.size()-3;
00240          IntArgs c(n*n);
00241          for (int i=0; i<n; i++)
00242            for (int j=0; j<n; j++)
00243              c[i*n+j]=j;
00244          IntVarArgs y(n);
00245          if (offset > 0) {
00246            for (int i=n; i--;)
00247              y[i] = Gecode::expr(home, x[i]+offset);
00248            path(home, c, offset, y, 
00249                 expr(home, x[n]+offset),
00250                 expr(home, x[n+1]+offset),
00251                 x[n+2], icl);
00252          } else {
00253            for (int i=0; i<n; i++)
00254              y[i]=x[i];
00255            path(home, c, y, x[n], x[n+1], x[n+2], icl);
00256          }
00257        }
00258      };
00259 
00261      class CircuitFullCost : public Test {
00262      private:
00264        int offset;
00265      public:
00267        CircuitFullCost(int n, int min, int max, int off,
00268                        Gecode::IntConLevel icl)
00269          : Test("Circuit::FullCost::" + str(icl)+"::"+str(n)+"::"+str(off),
00270                 2*n+1,min,max,false,icl), offset(off) {
00271          contest = CTL_NONE;
00272        }
00274        virtual bool solution(const Assignment& x) const {
00275          int n=(x.size()-1) / 2;
00276          for (int i=n; i--; )
00277            if ((x[i] < 0) || (x[i] > n-1))
00278              return false;
00279          int reachable = 0;
00280          {
00281            int j=0;
00282            for (int i=n; i--; ) {
00283              j=x[j]; reachable |= (1 << j);
00284            }
00285          }
00286          for (int i=n; i--; )
00287            if (!(reachable & (1 << i)))
00288              return false;
00289          for (int i=n; i--; )
00290            if ((x[i]/2) != x[n+i])
00291              return false;
00292          int c=0;
00293          for (int i=n; i--; )
00294            c += x[n+i];
00295          return c == x[2*n];
00296        }
00298        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00299          using namespace Gecode;
00300          int n=(x.size()-1)/2;
00301          IntArgs c(n*n);
00302          for (int i=0; i<n; i++)
00303            for (int j=0; j<n; j++)
00304              c[i*n+j]=(j/2);
00305          IntVarArgs y(n), z(n);
00306          for (int i=0; i<n; i++) {
00307            z[i]=x[n+i];
00308          }
00309          if (offset > 0) {
00310            for (int i=n; i--;)
00311              y[i] = Gecode::expr(home, x[i]+offset);
00312            Gecode::circuit(home, c, offset, y, z, x[2*n], icl);
00313          } else {
00314            for (int i=0; i<n; i++)
00315              y[i]=x[i];
00316            circuit(home, c, y, z, x[2*n], icl);
00317          }
00318        }
00319      };
00320 
00322      class Create {
00323      public:
00325        Create(void) {
00326          for (int i=1; i<=6; i++) {
00327            (void) new Circuit(i,0,i-1,0,Gecode::ICL_VAL);
00328            (void) new Circuit(i,0,i-1,0,Gecode::ICL_DOM);
00329            (void) new Circuit(i,0,i-1,5,Gecode::ICL_VAL);
00330            (void) new Circuit(i,0,i-1,5,Gecode::ICL_DOM);
00331          }
00332          for (int i=1; i<=4; i++) {
00333            (void) new Path(i,0,i-1,0,Gecode::ICL_VAL);
00334            (void) new Path(i,0,i-1,0,Gecode::ICL_DOM);
00335            (void) new Path(i,0,i-1,5,Gecode::ICL_VAL);
00336            (void) new Path(i,0,i-1,5,Gecode::ICL_DOM);
00337          }
00338          (void) new CircuitCost(4,0,9,0,Gecode::ICL_VAL);
00339          (void) new CircuitCost(4,0,9,0,Gecode::ICL_DOM);
00340          (void) new CircuitFullCost(3,0,3,0,Gecode::ICL_VAL);
00341          (void) new CircuitFullCost(3,0,3,0,Gecode::ICL_DOM);
00342          (void) new CircuitCost(4,0,9,5,Gecode::ICL_VAL);
00343          (void) new CircuitCost(4,0,9,5,Gecode::ICL_DOM);
00344          (void) new CircuitFullCost(3,0,3,5,Gecode::ICL_VAL);
00345          (void) new CircuitFullCost(3,0,3,5,Gecode::ICL_DOM);
00346          (void) new PathCost(3,0,5,0,Gecode::ICL_VAL);
00347          (void) new PathCost(3,0,5,0,Gecode::ICL_DOM);
00348          (void) new PathCost(3,0,5,5,Gecode::ICL_VAL);
00349          (void) new PathCost(3,0,5,5,Gecode::ICL_DOM);
00350        }
00351      };
00352 
00353      Create c;
00355 
00356    }
00357 }}
00358 
00359 // STATISTICS: test-int