Generated on for Gecode by doxygen 1.17.0
circuit.cpp
Go to the documentation of this file.
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Christian Schulte <schulte@gecode.dev>
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.dev
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
37namespace Test { namespace Int {
38
40 namespace Circuit {
41
47
48 class Circuit : public Test {
49 private:
51 int offset;
52 public:
54 Circuit(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
55 : Test(TestTags::sweep(),"Circuit::" + str(ipl) + "::" + str(n) + "::" + str(off),
56 n,min,max,false,ipl), offset(off) {
58 testfix = false;
59 }
60
61 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
78 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
79 if (offset > 0) {
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
91 class Path : public Test {
92 private:
94 int offset;
95 public:
97 Path(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
98 : Test(TestTags::sweep(),"Path::" + str(ipl) + "::" + str(n) + "::" + str(off),
99 n+2,min,max,false,ipl), offset(off) {
101 testfix = false;
102 }
103
104 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
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
144 class CircuitCost : public Test {
145 private:
147 int offset;
148 public:
150 CircuitCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
151 : Test((ipl == Gecode::IPL_DOM) && (n == 4) && (off == 0)
153 "Circuit::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
154 n+1,min,max,false,ipl), offset(off) {
156 testfix = false;
157 }
158
159 virtual bool solution(const Assignment& x) const {
160 int n=x.size()-1;
161 for (int i=n; i--; )
162 if ((x[i] < 0) || (x[i] > n-1))
163 return false;
164 int reachable = 0;
165 {
166 int j=0;
167 for (int i=n; i--; ) {
168 j=x[j]; reachable |= (1 << j);
169 }
170 }
171 for (int i=n; i--; )
172 if (!(reachable & (1 << i)))
173 return false;
174 int c=0;
175 for (int i=n; i--; )
176 c += x[i];
177 return c == x[n];
178 }
179
180 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
181 using namespace Gecode;
182 int n=x.size()-1;
183 IntArgs c(n*n);
184 for (int i=0; i<n; i++)
185 for (int j=0; j<n; j++)
186 c[i*n+j]=j;
187 IntVarArgs y(n);
188 if (offset > 0) {
189 for (int i=n; i--;)
190 y[i] = Gecode::expr(home, x[i]+offset);
191 Gecode::circuit(home, c, offset, y, x[n], ipl);
192 } else {
193 for (int i=0; i<n; i++)
194 y[i]=x[i];
195 circuit(home, c, y, x[n], ipl);
196 }
197 }
198 };
199
201 class PathCost : public Test {
202 private:
204 int offset;
205 public:
207 PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
208 : Test((ipl == Gecode::IPL_DOM) && (n == 3) && (off == 0)
210 "Path::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
211 n+3,min,max,false,ipl), offset(off) {
213 testfix = false;
214 }
215
216 virtual bool solution(const Assignment& x) const {
217 int n = x.size() - 3;
218 int s = x[n];
219 int e = x[n+1];
220 int c = x[n+2] + n;
221 if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
222 return false;
223 for (int i=n; i--; )
224 if ((i != e) && ((x[i] < 0) || (x[i] > n)))
225 return false;
226 int reachable = (1 << s);
227 {
228 int j=s;
229 for (int i=n; i--; ) {
230 j=x[j]; reachable |= (1 << j);
231 }
232 }
233 for (int i=n; i--; )
234 if (!(reachable & (1 << i)))
235 return false;
236 for (int i=n; i--; )
237 c -= x[i];
238 return c == 0;
239 }
240
241 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
242 using namespace Gecode;
243 int n=x.size()-3;
244 IntArgs c(n*n);
245 for (int i=0; i<n; i++)
246 for (int j=0; j<n; j++)
247 c[i*n+j]=j;
248 IntVarArgs y(n);
249 if (offset > 0) {
250 for (int i=n; i--;)
251 y[i] = Gecode::expr(home, x[i]+offset);
252 path(home, c, offset, y,
253 expr(home, x[n]+offset),
254 expr(home, x[n+1]+offset),
255 x[n+2], ipl);
256 } else {
257 for (int i=0; i<n; i++)
258 y[i]=x[i];
259 path(home, c, y, x[n], x[n+1], x[n+2], ipl);
260 }
261 }
262 };
263
265 class CircuitFullCost : public Test {
266 private:
268 int offset;
269 public:
271 CircuitFullCost(int n, int min, int max, int off,
273 : Test(TestTags::sweep(),"Circuit::FullCost::" + str(ipl)+"::"+str(n)+"::"+str(off),
274 2*n+1,min,max,false,ipl), offset(off) {
276 testfix = false;
277 }
278
279 virtual bool solution(const Assignment& x) const {
280 int n=(x.size()-1) / 2;
281 for (int i=n; i--; )
282 if ((x[i] < 0) || (x[i] > n-1))
283 return false;
284 int reachable = 0;
285 {
286 int j=0;
287 for (int i=n; i--; ) {
288 j=x[j]; reachable |= (1 << j);
289 }
290 }
291 for (int i=n; i--; )
292 if (!(reachable & (1 << i)))
293 return false;
294 for (int i=n; i--; )
295 if ((x[i]/2) != x[n+i])
296 return false;
297 int c=0;
298 for (int i=n; i--; )
299 c += x[n+i];
300 return c == x[2*n];
301 }
302
303 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
304 using namespace Gecode;
305 int n=(x.size()-1)/2;
306 IntArgs c(n*n);
307 for (int i=0; i<n; i++)
308 for (int j=0; j<n; j++)
309 c[i*n+j]=(j/2);
310 IntVarArgs y(n), z(n);
311 for (int i=0; i<n; i++) {
312 z[i]=x[n+i];
313 }
314 if (offset > 0) {
315 for (int i=n; i--;)
316 y[i] = Gecode::expr(home, x[i]+offset);
317 Gecode::circuit(home, c, offset, y, z, x[2*n], ipl);
318 } else {
319 for (int i=0; i<n; i++)
320 y[i]=x[i];
321 circuit(home, c, y, z, x[2*n], ipl);
322 }
323 }
324 };
325
327 class Create {
328 public:
330 Create(void) {
331 for (int i=1; i<=6; i++) {
332 (void) new Circuit(i,0,i-1,0,Gecode::IPL_VAL);
333 (void) new Circuit(i,0,i-1,0,Gecode::IPL_DOM);
334 (void) new Circuit(i,0,i-1,5,Gecode::IPL_VAL);
335 (void) new Circuit(i,0,i-1,5,Gecode::IPL_DOM);
336 }
337 for (int i=1; i<=4; i++) {
338 (void) new Path(i,0,i-1,0,Gecode::IPL_VAL);
339 (void) new Path(i,0,i-1,0,Gecode::IPL_DOM);
340 (void) new Path(i,0,i-1,5,Gecode::IPL_VAL);
341 (void) new Path(i,0,i-1,5,Gecode::IPL_DOM);
342 }
343 (void) new CircuitCost(4,0,9,0,Gecode::IPL_VAL);
344 (void) new CircuitCost(4,0,9,0,Gecode::IPL_DOM);
345 (void) new CircuitFullCost(3,0,3,0,Gecode::IPL_VAL);
346 (void) new CircuitFullCost(3,0,3,0,Gecode::IPL_DOM);
347 (void) new CircuitCost(4,0,9,5,Gecode::IPL_VAL);
348 (void) new CircuitCost(4,0,9,5,Gecode::IPL_DOM);
349 (void) new CircuitFullCost(3,0,3,5,Gecode::IPL_VAL);
350 (void) new CircuitFullCost(3,0,3,5,Gecode::IPL_DOM);
351 (void) new PathCost(3,0,5,0,Gecode::IPL_VAL);
352 (void) new PathCost(3,0,5,0,Gecode::IPL_DOM);
353 (void) new PathCost(3,0,5,5,Gecode::IPL_VAL);
354 (void) new PathCost(3,0,5,5,Gecode::IPL_DOM);
355 }
356 };
357
360
361 }
362}}
363
364// STATISTICS: test-int
Passing integer arguments.
Definition int.hh:653
Passing integer variables.
Definition int.hh:681
Integer variable array.
Definition int.hh:792
Computation spaces.
Definition core.hpp:1787
int size(void) const
Return size of array (number of elements).
Definition array.hpp:945
Base class for assignments
Definition int.hh:73
int size(void) const
Return number of variables.
Definition int.hpp:46
Simple test for circuit constraint with total cost.
Definition circuit.cpp:144
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition circuit.cpp:180
CircuitCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:150
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:159
Simple test for circuit constraint with full cost information.
Definition circuit.cpp:265
CircuitFullCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:271
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:279
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition circuit.cpp:303
Simple test for circuit constraint.
Definition circuit.cpp:48
Circuit(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:54
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition circuit.cpp:78
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:61
Help class to create and register tests.
Definition circuit.cpp:327
Create(void)
Perform creation and registration.
Definition circuit.cpp:330
Simple test for path constraint with total cost.
Definition circuit.cpp:201
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:216
PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:207
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition circuit.cpp:241
Simple test for Hamiltonian path constraint.
Definition circuit.cpp:91
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post path constraint on x.
Definition circuit.cpp:126
Path(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:97
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:104
static std::string str(bool b)
Map bool to string.
Definition int.hpp:278
bool testfix
Whether to perform fixpoint test.
Definition int.hh:287
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:281
ConTestLevel contest
Whether to test for certain consistency.
Definition int.hh:283
Set of test tags.
Definition test.hh:105
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:1274
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:1279
@ IPL_VAL
Value propagation.
Definition int.hh:1277
Gecode toplevel namespace
IntVar expr(Home home, const LinIntExpr &e, const IntPropLevels &ipls=IntPropLevels::def)
Post linear expression and return its value.
Definition int-expr.cpp:988
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void path(Home home, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a Hamiltonian path.
Definition circuit.cpp:169
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
void circuit(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a circuit.
Definition circuit.cpp:73
Testing finite domain integers.
Definition int.cpp:41
@ CTL_NONE
No consistency-test.
Definition int.hh:154
General test support.
Definition afc.cpp:41
@ standard
Standard test suite.
Definition test.hh:100
@ sweep
Really heavy sweep tests.
Definition test.hh:101