Generated on Wed Jan 24 2018 21:22:26 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  * Last modified:
10  * $Date: 2016-05-23 22:18:23 +0200 (Mon, 23 May 2016) $ by $Author: schulte $
11  * $Revision: 15073 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 #include "test/int.hh"
39 #include <gecode/minimodel.hh>
40 
41 namespace Test { namespace Int {
42 
44  namespace Circuit {
45 
51  class Circuit : public Test {
53  private:
55  int offset;
56  public:
58  Circuit(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
59  : Test("Circuit::" + str(ipl) + "::" + str(n) + "::" + str(off),
60  n,min,max,false,ipl), offset(off) {
61  contest = CTL_NONE;
62  testfix = false;
63  }
65  virtual bool solution(const Assignment& x) const {
66  for (int i=x.size(); i--; )
67  if ((x[i] < 0) || (x[i] > x.size()-1))
68  return false;
69  int reachable = 0;
70  {
71  int j=0;
72  for (int i=x.size(); i--; ) {
73  j=x[j]; reachable |= (1 << j);
74  }
75  }
76  for (int i=x.size(); i--; )
77  if (!(reachable & (1 << i)))
78  return false;
79  return true;
80  }
82  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
83  if (offset > 0) {
84  Gecode::IntVarArgs xx(x.size());
85  for (int i=x.size(); i--;)
86  xx[i] = Gecode::expr(home, x[i]+offset);
87  Gecode::circuit(home, offset, xx, ipl);
88  } else {
89  Gecode::circuit(home, x, ipl);
90  }
91  }
92  };
93 
95  class Path : public Test {
96  private:
98  int offset;
99  public:
101  Path(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
102  : Test("Path::" + str(ipl) + "::" + str(n) + "::" + str(off),
103  n+2,min,max,false,ipl), offset(off) {
104  contest = CTL_NONE;
105  testfix = false;
106  }
108  virtual bool solution(const Assignment& x) const {
109  int n = x.size() - 2;
110  int s = x[n];
111  int e = x[n+1];
112  if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
113  return false;
114  for (int i=n; i--; )
115  if ((i != e) && ((x[i] < 0) || (x[i] > n)))
116  return false;
117  int reachable = (1 << s);
118  {
119  int j=s;
120  for (int i=n; i--; ) {
121  j=x[j]; reachable |= (1 << j);
122  }
123  }
124  for (int i=n; i--; )
125  if (!(reachable & (1 << i)))
126  return false;
127  return true;
128  }
130  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
131  int n = x.size() - 2;
132  Gecode::IntVarArgs xx(n);
133  if (offset > 0) {
134  for (int i=n; i--;)
135  xx[i] = Gecode::expr(home, x[i]+offset);
136  Gecode::path(home, offset, xx,
137  Gecode::expr(home, x[n]+offset),
138  Gecode::expr(home, x[n+1]+offset),ipl);
139  } else {
140  for (int i=n; i--;)
141  xx[i] = x[i];
142  Gecode::path(home, xx, x[n], x[n+1], ipl);
143  }
144  }
145  };
146 
148  class CircuitCost : public Test {
149  private:
151  int offset;
152  public:
154  CircuitCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
155  : Test("Circuit::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
156  n+1,min,max,false,ipl), offset(off) {
157  contest = CTL_NONE;
158  testfix = false;
159  }
161  virtual bool solution(const Assignment& x) const {
162  int n=x.size()-1;
163  for (int i=n; i--; )
164  if ((x[i] < 0) || (x[i] > n-1))
165  return false;
166  int reachable = 0;
167  {
168  int j=0;
169  for (int i=n; i--; ) {
170  j=x[j]; reachable |= (1 << j);
171  }
172  }
173  for (int i=n; i--; )
174  if (!(reachable & (1 << i)))
175  return false;
176  int c=0;
177  for (int i=n; i--; )
178  c += x[i];
179  return c == x[n];
180  }
182  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
183  using namespace Gecode;
184  int n=x.size()-1;
185  IntArgs c(n*n);
186  for (int i=0; i<n; i++)
187  for (int j=0; j<n; j++)
188  c[i*n+j]=j;
189  IntVarArgs y(n);
190  if (offset > 0) {
191  for (int i=n; i--;)
192  y[i] = Gecode::expr(home, x[i]+offset);
193  Gecode::circuit(home, c, offset, y, x[n], ipl);
194  } else {
195  for (int i=0; i<n; i++)
196  y[i]=x[i];
197  circuit(home, c, y, x[n], ipl);
198  }
199  }
200  };
201 
203  class PathCost : public Test {
204  private:
206  int offset;
207  public:
209  PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
210  : Test("Path::Cost::"+str(ipl)+"::"+str(n)+"::"+str(off),
211  n+3,min,max,false,ipl), offset(off) {
212  contest = CTL_NONE;
213  testfix = false;
214  }
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  }
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("Circuit::FullCost::" + str(ipl)+"::"+str(n)+"::"+str(off),
274  2*n+1,min,max,false,ipl), offset(off) {
275  contest = CTL_NONE;
276  testfix = false;
277  }
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  }
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
static std::string str(Gecode::IntPropLevel ipl)
Map integer propagation level to string.
Definition: int.hpp:212
Create(void)
Perform creation and registration.
Definition: circuit.cpp:330
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:241
Simple test for circuit constraint with full cost information.
Definition: circuit.cpp:265
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
int size(void) const
Return number of variables.
Definition: int.hpp:50
Help class to create and register tests.
Definition: circuit.cpp:327
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:303
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:161
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:128
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:216
Integer variable array.
Definition: int.hh:744
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:65
void circuit(Home home, int offset, const IntVarArgs &x, IntPropLevel ipl)
Post propagator such that x forms a circuit.
Definition: circuit.cpp:45
Simple test for path constraint with total cost.
Definition: circuit.cpp:203
ConTestLevel contest
Whether to test for certain consistency.
Definition: int.hh:240
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:82
Computation spaces.
Definition: core.hpp:1748
Circuit(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition: circuit.cpp:58
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Simple test for Hamiltonian path constraint.
Definition: circuit.cpp:95
CircuitFullCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition: circuit.cpp:271
No consistency-test.
Definition: int.hh:144
Value propagation.
Definition: int.hh:958
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:221
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:784
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post path constraint on x.
Definition: circuit.cpp:130
Simple test for circuit constraint with total cost.
Definition: circuit.cpp:148
Gecode::IntPropLevel ipl
Propagation level.
Definition: int.hh:238
Passing integer variables.
Definition: int.hh:639
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:182
Passing integer arguments.
Definition: int.hh:610
BoolVar expr(Home home, const BoolExpr &e, IntPropLevel ipl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
bool testfix
Whether to perform fixpoint test.
Definition: int.hh:244
General test support.
Definition: afc.cpp:43
IntPropLevel
Propagation levels for integer propagators.
Definition: int.hh:955
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:108
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Base class for assignments
Definition: int.hh:63
PathCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition: circuit.cpp:209
Domain propagation Preferences: prefer speed or memory.
Definition: int.hh:960
Gecode toplevel namespace
Path(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition: circuit.cpp:101
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:121
CircuitCost(int n, int min, int max, int off, Gecode::IntPropLevel ipl)
Create and register test.
Definition: circuit.cpp:154
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:279
Simple test for circuit constraint.
Definition: circuit.cpp:52