Generated on Tue Feb 11 2025 17:33:26 for Gecode by doxygen 1.12.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.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
37namespace Test { namespace Int {
38
40 namespace Circuit {
41
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("Circuit::" + str(ipl) + "::" + str(n) + "::" + str(off),
56 n,min,max,false,ipl), offset(off) {
58 testfix = false;
59 }
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 }
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
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("Path::" + str(ipl) + "::" + str(n) + "::" + str(off),
99 n+2,min,max,false,ipl), offset(off) {
101 testfix = false;
102 }
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 }
126 virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
127 int n = x.size() - 2;
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("Circuit::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
152 n+1,min,max,false,ipl), offset(off) {
154 testfix = false;
155 }
157 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 }
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
199 class PathCost : public Test {
200 private:
202 int offset;
203 public:
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) {
209 testfix = false;
210 }
212 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 }
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
261 class CircuitFullCost : public Test {
262 private:
264 int offset;
265 public:
267 CircuitFullCost(int n, int min, int max, int off,
269 : Test("Circuit::FullCost::" + str(ipl)+"::"+str(n)+"::"+str(off),
270 2*n+1,min,max,false,ipl), offset(off) {
272 testfix = false;
273 }
275 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 }
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
323 class Create {
324 public:
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
356
357 }
358}}
359
360// STATISTICS: test-int
int n
Number of negative literals for node type.
Node * x
Pointer to corresponding Boolean expression node.
int size(void) const
Return size of array (number of elements)
Definition array.hpp:1607
Passing integer arguments.
Definition int.hh:628
Passing integer variables.
Definition int.hh:656
Integer variable array.
Definition int.hh:763
Computation spaces.
Definition core.hpp:1742
Base class for assignments
Definition int.hh:59
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:178
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:157
Simple test for circuit constraint with full cost information.
Definition circuit.cpp:261
CircuitFullCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:267
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:275
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition circuit.cpp:299
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:323
Create(void)
Perform creation and registration.
Definition circuit.cpp:326
Simple test for path constraint with total cost.
Definition circuit.cpp:199
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition circuit.cpp:212
PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition circuit.cpp:205
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition circuit.cpp:237
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
bool testfix
Whether to perform fixpoint test.
Definition int.hh:240
Gecode::IntPropLevel ipl
Propagation level.
Definition int.hh:234
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition int.hpp:209
ConTestLevel contest
Whether to test for certain consistency.
Definition int.hh:236
IntPropLevel
Propagation levels for integer propagators.
Definition int.hh:974
@ IPL_DOM
Domain propagation Options: basic versus advanced propagation.
Definition int.hh:979
@ IPL_VAL
Value propagation.
Definition int.hh:977
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:915
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 circuit(Home home, const IntVarArgs &x, IntPropLevel ipl=IPL_DEF)
Post propagator such that x forms a circuit.
Definition circuit.cpp:73
@ CTL_NONE
No consistency-test.
Definition int.hh:140
General test support.
Definition afc.cpp:39