Generated on Sat Feb 7 2015 02:01:21 for Gecode by doxygen 1.8.9.1
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: 2011-06-01 18:12:15 +0200 (Wed, 01 Jun 2011) $ by $Author: schulte $
11  * $Revision: 12036 $
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::IntConLevel icl)
59  : Test("Circuit::" + str(icl) + "::" + str(n) + "::" + str(off),
60  n,min,max,false,icl), offset(off) {
61  contest = CTL_NONE;
62  }
64  virtual bool solution(const Assignment& x) const {
65  for (int i=x.size(); i--; )
66  if ((x[i] < 0) || (x[i] > x.size()-1))
67  return false;
68  int reachable = 0;
69  {
70  int j=0;
71  for (int i=x.size(); i--; ) {
72  j=x[j]; reachable |= (1 << j);
73  }
74  }
75  for (int i=x.size(); i--; )
76  if (!(reachable & (1 << i)))
77  return false;
78  return true;
79  }
81  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
82  if (offset > 0) {
83  Gecode::IntVarArgs xx(x.size());
84  for (int i=x.size(); i--;)
85  xx[i] = Gecode::expr(home, x[i]+offset);
86  Gecode::circuit(home, offset, xx, icl);
87  } else {
88  Gecode::circuit(home, x, icl);
89  }
90  }
91  };
92 
94  class Path : public Test {
95  private:
97  int offset;
98  public:
100  Path(int n, int min, int max, int off, Gecode::IntConLevel icl)
101  : Test("Path::" + str(icl) + "::" + str(n) + "::" + str(off),
102  n+2,min,max,false,icl), offset(off) {
103  contest = CTL_NONE;
104  }
106  virtual bool solution(const Assignment& x) const {
107  int n = x.size() - 2;
108  int s = x[n];
109  int e = x[n+1];
110  if ((s < 0) || (s > n) || (e < 0) || (e > n) || (x[e] != n))
111  return false;
112  for (int i=n; i--; )
113  if ((i != e) && ((x[i] < 0) || (x[i] > n)))
114  return false;
115  int reachable = (1 << s);
116  {
117  int j=s;
118  for (int i=n; i--; ) {
119  j=x[j]; reachable |= (1 << j);
120  }
121  }
122  for (int i=n; i--; )
123  if (!(reachable & (1 << i)))
124  return false;
125  return true;
126  }
128  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
129  int n = x.size() - 2;
130  Gecode::IntVarArgs xx(n);
131  if (offset > 0) {
132  for (int i=n; i--;)
133  xx[i] = Gecode::expr(home, x[i]+offset);
134  Gecode::path(home, offset, xx,
135  Gecode::expr(home, x[n]+offset),
136  Gecode::expr(home, x[n+1]+offset),icl);
137  } else {
138  for (int i=n; i--;)
139  xx[i] = x[i];
140  Gecode::path(home, xx, x[n], x[n+1], icl);
141  }
142  }
143  };
144 
146  class CircuitCost : public Test {
147  private:
149  int offset;
150  public:
152  CircuitCost(int n, int min, int max, int off, Gecode::IntConLevel icl)
153  : Test("Circuit::Cost::"+str(icl)+"::"+str(n)+"::"+str(off),
154  n+1,min,max,false,icl), offset(off) {
155  contest = CTL_NONE;
156  }
158  virtual bool solution(const Assignment& x) const {
159  int n=x.size()-1;
160  for (int i=n; i--; )
161  if ((x[i] < 0) || (x[i] > n-1))
162  return false;
163  int reachable = 0;
164  {
165  int j=0;
166  for (int i=n; i--; ) {
167  j=x[j]; reachable |= (1 << j);
168  }
169  }
170  for (int i=n; i--; )
171  if (!(reachable & (1 << i)))
172  return false;
173  int c=0;
174  for (int i=n; i--; )
175  c += x[i];
176  return c == x[n];
177  }
179  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
180  using namespace Gecode;
181  int n=x.size()-1;
182  IntArgs c(n*n);
183  for (int i=0; i<n; i++)
184  for (int j=0; j<n; j++)
185  c[i*n+j]=j;
186  IntVarArgs y(n);
187  if (offset > 0) {
188  for (int i=n; i--;)
189  y[i] = Gecode::expr(home, x[i]+offset);
190  Gecode::circuit(home, c, offset, y, x[n], icl);
191  } else {
192  for (int i=0; i<n; i++)
193  y[i]=x[i];
194  circuit(home, c, y, x[n], icl);
195  }
196  }
197  };
198 
200  class PathCost : public Test {
201  private:
203  int offset;
204  public:
206  PathCost(int n, int min, int max, int off, Gecode::IntConLevel icl)
207  : Test("Path::Cost::"+str(icl)+"::"+str(n)+"::"+str(off),
208  n+3,min,max,false,icl), offset(off) {
209  contest = CTL_NONE;
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], icl);
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], icl);
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(icl)+"::"+str(n)+"::"+str(off),
270  2*n+1,min,max,false,icl), offset(off) {
271  contest = CTL_NONE;
272  }
274  virtual bool solution(const Assignment& x) const {
275  int n=(x.size()-1) / 2;
276  for (int i=n; i--; )
277  if ((x[i] < 0) || (x[i] > n-1))
278  return false;
279  int reachable = 0;
280  {
281  int j=0;
282  for (int i=n; i--; ) {
283  j=x[j]; reachable |= (1 << j);
284  }
285  }
286  for (int i=n; i--; )
287  if (!(reachable & (1 << i)))
288  return false;
289  for (int i=n; i--; )
290  if ((x[i]/2) != x[n+i])
291  return false;
292  int c=0;
293  for (int i=n; i--; )
294  c += x[n+i];
295  return c == x[2*n];
296  }
298  virtual void post(Gecode::Space& home, Gecode::IntVarArray& x) {
299  using namespace Gecode;
300  int n=(x.size()-1)/2;
301  IntArgs c(n*n);
302  for (int i=0; i<n; i++)
303  for (int j=0; j<n; j++)
304  c[i*n+j]=(j/2);
305  IntVarArgs y(n), z(n);
306  for (int i=0; i<n; i++) {
307  z[i]=x[n+i];
308  }
309  if (offset > 0) {
310  for (int i=n; i--;)
311  y[i] = Gecode::expr(home, x[i]+offset);
312  Gecode::circuit(home, c, offset, y, z, x[2*n], icl);
313  } else {
314  for (int i=0; i<n; i++)
315  y[i]=x[i];
316  circuit(home, c, y, z, x[2*n], icl);
317  }
318  }
319  };
320 
322  class Create {
323  public:
325  Create(void) {
326  for (int i=1; i<=6; i++) {
327  (void) new Circuit(i,0,i-1,0,Gecode::ICL_VAL);
328  (void) new Circuit(i,0,i-1,0,Gecode::ICL_DOM);
329  (void) new Circuit(i,0,i-1,5,Gecode::ICL_VAL);
330  (void) new Circuit(i,0,i-1,5,Gecode::ICL_DOM);
331  }
332  for (int i=1; i<=4; i++) {
333  (void) new Path(i,0,i-1,0,Gecode::ICL_VAL);
334  (void) new Path(i,0,i-1,0,Gecode::ICL_DOM);
335  (void) new Path(i,0,i-1,5,Gecode::ICL_VAL);
336  (void) new Path(i,0,i-1,5,Gecode::ICL_DOM);
337  }
338  (void) new CircuitCost(4,0,9,0,Gecode::ICL_VAL);
339  (void) new CircuitCost(4,0,9,0,Gecode::ICL_DOM);
340  (void) new CircuitFullCost(3,0,3,0,Gecode::ICL_VAL);
341  (void) new CircuitFullCost(3,0,3,0,Gecode::ICL_DOM);
342  (void) new CircuitCost(4,0,9,5,Gecode::ICL_VAL);
343  (void) new CircuitCost(4,0,9,5,Gecode::ICL_DOM);
344  (void) new CircuitFullCost(3,0,3,5,Gecode::ICL_VAL);
345  (void) new CircuitFullCost(3,0,3,5,Gecode::ICL_DOM);
346  (void) new PathCost(3,0,5,0,Gecode::ICL_VAL);
347  (void) new PathCost(3,0,5,0,Gecode::ICL_DOM);
348  (void) new PathCost(3,0,5,5,Gecode::ICL_VAL);
349  (void) new PathCost(3,0,5,5,Gecode::ICL_DOM);
350  }
351  };
352 
355 
356  }
357 }}
358 
359 // STATISTICS: test-int
PathCost(int n, int min, int max, int off, Gecode::IntConLevel icl)
Create and register test.
Definition: circuit.cpp:206
Create(void)
Perform creation and registration.
Definition: circuit.cpp:325
IntConLevel
Consistency levels for integer propagators.
Definition: int.hh:937
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
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
Help class to create and register tests.
Definition: circuit.cpp:322
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:298
Value propagation or consistency (naive)
Definition: int.hh:938
Path(int n, int min, int max, int off, Gecode::IntConLevel icl)
Create and register test.
Definition: circuit.cpp:100
CircuitCost(int n, int min, int max, int off, Gecode::IntConLevel icl)
Create and register test.
Definition: circuit.cpp:152
void path(Home home, const IntArgs &c, const IntVarArgs &x, IntVar s, IntVar e, IntVar z, IntConLevel icl)
Post propagator such that x forms a Hamiltonian path with cost z.
Definition: circuit.cpp:221
Integer variable array.
Definition: int.hh:741
Simple test for path constraint with total cost.
Definition: circuit.cpp:200
void path(Home home, int offset, const IntVarArgs &x, IntVar s, IntVar e, IntConLevel icl)
Post propagator such that x forms a Hamiltonian path.
Definition: circuit.cpp:128
Circuit(int n, int min, int max, int off, Gecode::IntConLevel icl)
Create and register test.
Definition: circuit.cpp:58
ConTestLevel contest
Whether to test for certain consistency.
Definition: int.hh:228
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:81
Computation spaces.
Definition: core.hpp:1362
void circuit(Home home, const IntArgs &c, const IntVarArgs &x, IntVar z, IntConLevel icl)
Post propagator such that x forms a circuit with cost z.
Definition: circuit.cpp:121
static std::string str(Gecode::ExtensionalPropKind epk)
Map extensional propagation kind to string.
Definition: int.hpp:212
const FloatNum min
Smallest allowed float value.
Definition: float.hh:833
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:94
No consistency-test.
Definition: int.hh:144
Gecode::IntConLevel icl
Consistency level.
Definition: int.hh:226
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:158
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:274
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:106
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post path constraint on x.
Definition: circuit.cpp:128
Simple test for circuit constraint with total cost.
Definition: circuit.cpp:146
Passing integer variables.
Definition: int.hh:636
virtual void post(Gecode::Space &home, Gecode::IntVarArray &x)
Post circuit constraint on x.
Definition: circuit.cpp:179
Passing integer arguments.
Definition: int.hh:607
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:64
CircuitFullCost(int n, int min, int max, int off, Gecode::IntConLevel icl)
Create and register test.
Definition: circuit.cpp:267
General test support.
Definition: afc.cpp:43
BoolVar expr(Home home, const BoolExpr &e, IntConLevel icl)
Post Boolean expression and return its value.
Definition: bool-expr.cpp:632
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Base class for assignments
Definition: int.hh:63
Gecode toplevel namespace
virtual bool solution(const Assignment &x) const
Check whether x is solution.
Definition: circuit.cpp:212
void circuit(Home home, int offset, const IntVarArgs &x, IntConLevel icl)
Post propagator such that x forms a circuit.
Definition: circuit.cpp:45
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:985
int size(void) const
Return number of variables.
Definition: int.hpp:50
Domain propagation or consistency.
Definition: int.hh:940
Simple test for circuit constraint.
Definition: circuit.cpp:52