Generated on Mon May 10 06:46:31 2010 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: 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 "test/int.hh"
00039 #include <gecode/graph.hh>
00040 
00041 namespace Test { namespace Int {
00042 
00044    namespace Circuit {
00045 
00051 
00052      class Circuit : public Test {
00053      public:
00055        Circuit(int n, int min, int max, Gecode::IntConLevel icl)
00056          : Test("Circuit::" + str(icl) + "::" + str(n),
00057                    n,min,max,false,icl) {
00058          contest = CTL_NONE;
00059        }
00061        virtual bool solution(const Assignment& x) const {
00062          for (int i=x.size(); i--; )
00063            if ((x[i] < 0) || (x[i] > x.size()-1))
00064              return false;
00065          int reachable = 0;
00066          {
00067            int j=0;
00068            for (int i=x.size(); i--; ) {
00069              j=x[j]; reachable |= (1 << j);
00070            }
00071          }
00072          for (int i=x.size(); i--; )
00073            if (!(reachable & (1 << i)))
00074              return false;
00075          return true;
00076        }
00078        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00079          Gecode::circuit(home, x, icl);
00080        }
00081      };
00082 
00084      class CircuitCost : public Test {
00085      public:
00087        CircuitCost(int n, int min, int max, Gecode::IntConLevel icl)
00088          : Test("Circuit::Cost::" + str(icl) + "::" + str(n),
00089                 n+1,min,max,false,icl) {
00090          contest = CTL_NONE;
00091        }
00093        virtual bool solution(const Assignment& x) const {
00094          int n=x.size()-1;
00095          for (int i=n; i--; )
00096            if ((x[i] < 0) || (x[i] > n-1))
00097              return false;
00098          int reachable = 0;
00099          {
00100            int j=0;
00101            for (int i=n; i--; ) {
00102              j=x[j]; reachable |= (1 << j);
00103            }
00104          }
00105          for (int i=n; i--; )
00106            if (!(reachable & (1 << i)))
00107              return false;
00108          int c=0;
00109          for (int i=n; i--; )
00110            c += x[i];
00111          return c == x[n];
00112        }
00114        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00115          using namespace Gecode;
00116          int n=x.size()-1;
00117          IntArgs c(n*n);
00118          for (int i=0; i<n; i++)
00119            for (int j=0; j<n; j++)
00120              c[i*n+j]=j;
00121          IntVarArgs y(n);
00122          for (int i=0; i<n; i++)
00123            y[i]=x[i];
00124          circuit(home, c, y, x[n], icl);
00125        }
00126      };
00127 
00129      class CircuitFullCost : public Test {
00130      public:
00132        CircuitFullCost(int n, int min, int max, Gecode::IntConLevel icl)
00133          : Test("Circuit::FullCost::" + str(icl) + "::" + str(n),
00134                 2*n+1,min,max,false,icl) {
00135          contest = CTL_NONE;
00136        }
00138        virtual bool solution(const Assignment& x) const {
00139          int n=(x.size()-1) / 2;
00140          for (int i=n; i--; )
00141            if ((x[i] < 0) || (x[i] > n-1))
00142              return false;
00143          int reachable = 0;
00144          {
00145            int j=0;
00146            for (int i=n; i--; ) {
00147              j=x[j]; reachable |= (1 << j);
00148            }
00149          }
00150          for (int i=n; i--; )
00151            if (!(reachable & (1 << i)))
00152              return false;
00153          for (int i=n; i--; )
00154            if ((x[i]/2) != x[n+i])
00155              return false;
00156          int c=0;
00157          for (int i=n; i--; )
00158            c += x[n+i];
00159          return c == x[2*n];
00160        }
00162        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
00163          using namespace Gecode;
00164          int n=(x.size()-1)/2;
00165          IntArgs c(n*n);
00166          for (int i=0; i<n; i++)
00167            for (int j=0; j<n; j++)
00168              c[i*n+j]=(j/2);
00169          IntVarArgs y(n), z(n);
00170          for (int i=0; i<n; i++) {
00171            y[i]=x[i]; z[i]=x[n+i];
00172          }
00173          circuit(home, c, y, z, x[2*n], icl);
00174        }
00175      };
00176 
00178      class Create {
00179      public:
00181        Create(void) {
00182          for (int i=1; i<=6; i++) {
00183            (void) new Circuit(i,0,i-1,Gecode::ICL_VAL);
00184            (void) new Circuit(i,0,i-1,Gecode::ICL_DOM);
00185          }
00186          (void) new CircuitCost(4,0,9,Gecode::ICL_VAL);
00187          (void) new CircuitCost(4,0,9,Gecode::ICL_DOM);
00188          (void) new CircuitFullCost(3,0,3,Gecode::ICL_VAL);
00189          (void) new CircuitFullCost(3,0,3,Gecode::ICL_DOM);
00190        }
00191      };
00192 
00193      Create c;
00195 
00196    }
00197 }}
00198 
00199 // STATISTICS: test-graph