Generated on Sat Jun 2 2018 07:17:44 for Gecode by doxygen 1.8.13
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 
37 namespace Test { namespace Int {
38 
40  namespace Circuit {
41 
47  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) {
57  contest = CTL_NONE;
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) {
100  contest = CTL_NONE;
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;
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("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  }
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) {
208  contest = CTL_NONE;
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) {
271  contest = CTL_NONE;
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
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition: int.hpp:208
Create(void)
Perform creation and registration.
Definition: circuit.cpp:326
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:237
Simple test for circuit constraint with full cost information.
Definition: circuit.cpp:261
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:969
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
int size(void) const
Return number of variables.
Definition: int.hpp:46
Help class to create and register tests.
Definition: circuit.cpp:323
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:299
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:157
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntPropLevel ipl)
Post propagator such that x forms a Hamiltonian path.
Definition: circuit.cpp:124
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:212
Integer variable array.
Definition: int.hh:738
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:61
void circuit(Home home, int offset, const IntVarArgs &x, IntPropLevel ipl)
Post propagator such that x forms a circuit.
Definition: circuit.cpp:41
Simple test for path constraint with total cost.
Definition: circuit.cpp:199
ConTestLevel contest
Whether to test for certain consistency.
Definition: int.hh:236
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:78
Computation spaces.
Definition: core.hpp:1701
Circuit(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition: circuit.cpp:54
const FloatNum min
Smallest allowed float value.
Definition: float.hh:846
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:234
Simple test for Hamiltonian path constraint.
Definition: circuit.cpp:91
CircuitFullCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition: circuit.cpp:267
No consistency-test.
Definition: int.hh:140
Value propagation.
Definition: int.hh:952
void path(Home home, const IntArgs &c, const IntVarArgs &x, IntVar s, IntVar e, IntVar z, IntPropLevel ipl)
Post propagator such that x forms a Hamiltonian path with cost z.
Definition: circuit.cpp:217
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:765
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post path constraint on x.
Definition: circuit.cpp:126
Simple test for circuit constraint with total cost.
Definition: circuit.cpp:144
Gecode::IntPropLevel ipl
Propagation level.
Definition: int.hh:234
Passing integer variables.
Definition: int.hh:633
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:178
Passing integer arguments.
Definition: int.hh:604
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:628
bool testfix
Whether to perform fixpoint test.
Definition: int.hh:240
General test support.
Definition: afc.cpp:39
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:949
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:104
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:765
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:249
Base class for assignments
Definition: int.hh:59
PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition: circuit.cpp:205
Domain propagation Options: basic versus advanced propagation.
Definition: int.hh:954
Gecode toplevel namespace
Path(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition: circuit.cpp:97
void circuit(Home home, const IntArgs &c, const IntVarArgs &x, IntVar z, IntPropLevel ipl)
Post propagator such that x forms a circuit with cost z.
Definition: circuit.cpp:117
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:275
Simple test for circuit constraint.
Definition: circuit.cpp:48