1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  *  Main authors:
4  *     Christian Schulte <schulte@gecode.org>
5  *
6  *  Copyright:
7  *     Christian Schulte, 2007
8  *
9  *  This file is part of Gecode, the generic constraint
10  *  development environment:
11  *     http://www.gecode.org
12  *
13  *  Permission is hereby granted, free of charge, to any person obtaining
14  *  a copy of this software and associated documentation files (the
15  *  "Software"), to deal in the Software without restriction, including
16  *  without limitation the rights to use, copy, modify, merge, publish,
17  *  distribute, sublicense, and/or sell copies of the Software, and to
18  *  permit persons to whom the Software is furnished to do so, subject to
19  *  the following conditions:
20  *
21  *  The above copyright notice and this permission notice shall be
22  *  included in all copies or substantial portions of the Software.
23  *
24  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31  *
32  */
33 
34 #include "test/int.hh"
35 #include <gecode/minimodel.hh>
36 
37 namespace Test { namespace Int {
38 
39    /// %Tests for circuit constraints
40    namespace Circuit {
41 
42      /**
43       * \defgroup TaskTestIntCircuit Circuit constraints
44       * \ingroup TaskTestInt
45       */
46      //@{
47      /// Simple test for circuit constraint
48      class Circuit : public Test {
49      private:
50        /// Offset
51        int offset;
52      public:
53        /// Create and register test
Circuit(int n,int min,int max,int off,Gecode::IntPropLevel ipl)54        Circuit(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
55          : Test("Circuit::" + str(ipl) + "::" + str(n) + "::" + str(off),
56                 n,min,max,false,ipl), offset(off) {
57          contest = CTL_NONE;
58          testfix = false;
59        }
60        /// Check whether \a x is solution
solution(const Assignment & x) const61        virtual bool solution(const Assignment& x) const {
62          for (int i=x.size(); i--; )
63            if ((x[i] < 0) || (x[i] > x.size()-1))
64              return false;
65          int reachable = 0;
66          {
67            int j=0;
68            for (int i=x.size(); i--; ) {
69              j=x[j]; reachable |= (1 << j);
70            }
71          }
72          for (int i=x.size(); i--; )
73            if (!(reachable & (1 << i)))
74              return false;
75          return true;
76        }
77        /// Post circuit constraint on \a x
post(Gecode::Space & home,Gecode::IntVarArray & x)78        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
79          if (offset > 0) {
80            Gecode::IntVarArgs xx(x.size());
81            for (int i=x.size(); i--;)
82              xx[i] = Gecode::expr(home, x[i]+offset);
83            Gecode::circuit(home, offset, xx, ipl);
84          } else {
85            Gecode::circuit(home, x, ipl);
86          }
87        }
88      };
89 
90      /// Simple test for Hamiltonian path constraint
91      class Path : public Test {
92      private:
93        /// Offset
94        int offset;
95      public:
96        /// Create and register test
Path(int n,int min,int max,int off,Gecode::IntPropLevel ipl)97        Path(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
98          : Test("Path::" + str(ipl) + "::" + str(n) + "::" + str(off),
99                 n+2,min,max,false,ipl), offset(off) {
100          contest = CTL_NONE;
101          testfix = false;
102        }
103        /// Check whether \a x is solution
solution(const Assignment & x) const104        virtual bool solution(const Assignment& x) const {
105          int n = x.size() - 2;
106          int s = x[n];
107          int e = x[n+1];
108          if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
109            return false;
110          for (int i=n; i--; )
111            if ((i != e) && ((x[i] < 0) || (x[i] > n)))
112              return false;
113          int reachable = (1 << s);
114          {
115            int j=s;
116            for (int i=n; i--; ) {
117              j=x[j]; reachable |= (1 << j);
118            }
119          }
120          for (int i=n; i--; )
121            if (!(reachable & (1 << i)))
122              return false;
123          return true;
124        }
125        /// Post path constraint on \a x
post(Gecode::Space & home,Gecode::IntVarArray & x)126        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
127          int n = x.size() - 2;
128          Gecode::IntVarArgs xx(n);
129          if (offset > 0) {
130            for (int i=n; i--;)
131              xx[i] = Gecode::expr(home, x[i]+offset);
132            Gecode::path(home, offset, xx,
133                         Gecode::expr(home, x[n]+offset),
134                         Gecode::expr(home, x[n+1]+offset),ipl);
135          } else {
136            for (int i=n; i--;)
137              xx[i] = x[i];
138            Gecode::path(home, xx, x[n], x[n+1], ipl);
139          }
140        }
141      };
142 
143      /// Simple test for circuit constraint with total cost
144      class CircuitCost : public Test {
145      private:
146        /// Offset
147        int offset;
148      public:
149        /// Create and register test
CircuitCost(int n,int min,int max,int off,Gecode::IntPropLevel ipl)150        CircuitCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
151          : Test("Circuit::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
152                 n+1,min,max,false,ipl), offset(off) {
153          contest = CTL_NONE;
154          testfix = false;
155        }
156        /// Check whether \a x is solution
solution(const Assignment & x) const157        virtual bool solution(const Assignment& x) const {
158          int n=x.size()-1;
159          for (int i=n; i--; )
160            if ((x[i] < 0) || (x[i] > n-1))
161              return false;
162          int reachable = 0;
163          {
164            int j=0;
165            for (int i=n; i--; ) {
166              j=x[j]; reachable |= (1 << j);
167            }
168          }
169          for (int i=n; i--; )
170            if (!(reachable & (1 << i)))
171              return false;
172          int c=0;
173          for (int i=n; i--; )
174            c += x[i];
175          return c == x[n];
176        }
177        /// Post circuit constraint on \a x
post(Gecode::Space & home,Gecode::IntVarArray & x)178        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
179          using namespace Gecode;
180          int n=x.size()-1;
181          IntArgs c(n*n);
182          for (int i=0; i<n; i++)
183            for (int j=0; j<n; j++)
184              c[i*n+j]=j;
185          IntVarArgs y(n);
186          if (offset > 0) {
187            for (int i=n; i--;)
188              y[i] = Gecode::expr(home, x[i]+offset);
189            Gecode::circuit(home, c, offset, y, x[n], ipl);
190          } else {
191            for (int i=0; i<n; i++)
192              y[i]=x[i];
193            circuit(home, c, y, x[n], ipl);
194          }
195        }
196      };
197 
198      /// Simple test for path constraint with total cost
199      class PathCost : public Test {
200      private:
201        /// Offset
202        int offset;
203      public:
204        /// Create and register test
PathCost(int n,int min,int max,int off,Gecode::IntPropLevel ipl)205        PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
206          : Test("Path::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
207                 n+3,min,max,false,ipl), offset(off) {
208          contest = CTL_NONE;
209          testfix = false;
210        }
211        /// Check whether \a x is solution
solution(const Assignment & x) const212        virtual bool solution(const Assignment& x) const {
213          int n = x.size() - 3;
214          int s = x[n];
215          int e = x[n+1];
216          int c = x[n+2] + n;
217          if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
218            return false;
219          for (int i=n; i--; )
220            if ((i != e) && ((x[i] < 0) || (x[i] > n)))
221              return false;
222          int reachable = (1 << s);
223          {
224            int j=s;
225            for (int i=n; i--; ) {
226              j=x[j]; reachable |= (1 << j);
227            }
228          }
229          for (int i=n; i--; )
230            if (!(reachable & (1 << i)))
231              return false;
232          for (int i=n; i--; )
233            c -= x[i];
234          return c == 0;
235        }
236        /// Post circuit constraint on \a x
post(Gecode::Space & home,Gecode::IntVarArray & x)237        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
238          using namespace Gecode;
239          int n=x.size()-3;
240          IntArgs c(n*n);
241          for (int i=0; i<n; i++)
242            for (int j=0; j<n; j++)
243              c[i*n+j]=j;
244          IntVarArgs y(n);
245          if (offset > 0) {
246            for (int i=n; i--;)
247              y[i] = Gecode::expr(home, x[i]+offset);
248            path(home, c, offset, y,
249                 expr(home, x[n]+offset),
250                 expr(home, x[n+1]+offset),
251                 x[n+2], ipl);
252          } else {
253            for (int i=0; i<n; i++)
254              y[i]=x[i];
255            path(home, c, y, x[n], x[n+1], x[n+2], ipl);
256          }
257        }
258      };
259 
260      /// Simple test for circuit constraint with full cost information
261      class CircuitFullCost : public Test {
262      private:
263        /// Offset
264        int offset;
265      public:
266        /// Create and register test
CircuitFullCost(int n,int min,int max,int off,Gecode::IntPropLevel ipl)267        CircuitFullCost(int n, int min, int max, int off,
268                        Gecode::IntPropLevel ipl)
269          : Test("Circuit::FullCost::" + str(ipl)+"::"+str(n)+"::"+str(off),
270                 2*n+1,min,max,false,ipl), offset(off) {
271          contest = CTL_NONE;
272          testfix = false;
273        }
274        /// Check whether \a x is solution
solution(const Assignment & x) const275        virtual bool solution(const Assignment& x) const {
276          int n=(x.size()-1) / 2;
277          for (int i=n; i--; )
278            if ((x[i] < 0) || (x[i] > n-1))
279              return false;
280          int reachable = 0;
281          {
282            int j=0;
283            for (int i=n; i--; ) {
284              j=x[j]; reachable |= (1 << j);
285            }
286          }
287          for (int i=n; i--; )
288            if (!(reachable & (1 << i)))
289              return false;
290          for (int i=n; i--; )
291            if ((x[i]/2) != x[n+i])
292              return false;
293          int c=0;
294          for (int i=n; i--; )
295            c += x[n+i];
296          return c == x[2*n];
297        }
298        /// Post circuit constraint on \a x
post(Gecode::Space & home,Gecode::IntVarArray & x)299        virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
300          using namespace Gecode;
301          int n=(x.size()-1)/2;
302          IntArgs c(n*n);
303          for (int i=0; i<n; i++)
304            for (int j=0; j<n; j++)
305              c[i*n+j]=(j/2);
306          IntVarArgs y(n), z(n);
307          for (int i=0; i<n; i++) {
308            z[i]=x[n+i];
309          }
310          if (offset > 0) {
311            for (int i=n; i--;)
312              y[i] = Gecode::expr(home, x[i]+offset);
313            Gecode::circuit(home, c, offset, y, z, x[2*n], ipl);
314          } else {
315            for (int i=0; i<n; i++)
316              y[i]=x[i];
317            circuit(home, c, y, z, x[2*n], ipl);
318          }
319        }
320      };
321 
322      /// Help class to create and register tests
323      class Create {
324      public:
325        /// Perform creation and registration
Create(void)326        Create(void) {
327          for (int i=1; i<=6; i++) {
328            (void) new Circuit(i,0,i-1,0,Gecode::IPL_VAL);
329            (void) new Circuit(i,0,i-1,0,Gecode::IPL_DOM);
330            (void) new Circuit(i,0,i-1,5,Gecode::IPL_VAL);
331            (void) new Circuit(i,0,i-1,5,Gecode::IPL_DOM);
332          }
333          for (int i=1; i<=4; i++) {
334            (void) new Path(i,0,i-1,0,Gecode::IPL_VAL);
335            (void) new Path(i,0,i-1,0,Gecode::IPL_DOM);
336            (void) new Path(i,0,i-1,5,Gecode::IPL_VAL);
337            (void) new Path(i,0,i-1,5,Gecode::IPL_DOM);
338          }
339          (void) new CircuitCost(4,0,9,0,Gecode::IPL_VAL);
340          (void) new CircuitCost(4,0,9,0,Gecode::IPL_DOM);
341          (void) new CircuitFullCost(3,0,3,0,Gecode::IPL_VAL);
342          (void) new CircuitFullCost(3,0,3,0,Gecode::IPL_DOM);
343          (void) new CircuitCost(4,0,9,5,Gecode::IPL_VAL);
344          (void) new CircuitCost(4,0,9,5,Gecode::IPL_DOM);
345          (void) new CircuitFullCost(3,0,3,5,Gecode::IPL_VAL);
346          (void) new CircuitFullCost(3,0,3,5,Gecode::IPL_DOM);
347          (void) new PathCost(3,0,5,0,Gecode::IPL_VAL);
348          (void) new PathCost(3,0,5,0,Gecode::IPL_DOM);
349          (void) new PathCost(3,0,5,5,Gecode::IPL_VAL);
350          (void) new PathCost(3,0,5,5,Gecode::IPL_DOM);
351        }
352      };
353 
354      Create c;
355      //@}
356 
357    }
358 }}
359 
360 // STATISTICS: test-int
361