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