Generated on Sat Jul 29 2017 12:41:24 for Gecode by doxygen 1.8.13
int.cpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Guido Tack <tack@gecode.org>
5  * Christian Schulte <schulte@gecode.org>
6  *
7  * Copyright:
8  * Guido Tack, 2004
9  * Christian Schulte, 2004
10  *
11  * Last modified:
12  * $Date: 2017-03-10 10:28:56 +0100 (Fri, 10 Mar 2017) $ by $Author: schulte $
13  * $Revision: 15567 $
14  *
15  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <gecode/set.hh>
41 
42 #include <gecode/set/int.hh>
43 #include <gecode/set/rel.hh>
44 
45 namespace Gecode {
46 
47  void
48  rel(Home home, SetVar s, IntRelType rt, IntVar x) {
50  switch (rt) {
51  case IRT_EQ:
52  {
54  Set::SingletonView xsingle(xv);
57  ::post(home,s,xsingle)));
58 
59  }
60  break;
61  case IRT_NQ:
62  {
64  GECODE_ME_FAIL( sv.cardMin(home, 1));
66  Set::SingletonView xsingle(xv);
69  ::post(home,xsingle,sv)));
70 
71  }
72  break;
73  case IRT_LQ:
74  {
76  rel(home, tmp, IRT_LQ, x);
78  }
79  break;
80  case IRT_LE:
81  {
83  rel(home, tmp, IRT_LE, x);
85  }
86  break;
87  case IRT_GQ:
88  {
90  rel(home, tmp, IRT_GQ, x);
92  }
93  break;
94  case IRT_GR:
95  {
97  rel(home, tmp, IRT_GR, x);
99  }
100  break;
101  default:
102  throw Int::UnknownRelation("Set::rel");
103  }
104 
105  }
106 
107 }
108 
109 namespace Gecode { namespace Set { namespace Int {
110 
112  void remin(Home home, SetVar s, IntVar m, Reify r) {
113  IntVar c(home, 0, static_cast<int>(Set::Limits::card));
114  cardinality(home, s, c);
115  // Whether set is not empty
116  BoolVar ne(home, 0, 1);
117  rel(home, c, IRT_GR, 0, ne);
118  if (r.mode() != RM_PMI)
119  rel(home, r.var(), BOT_IMP, ne, 1);
120  min(home, s, m, ne);
121  }
122 
124  void remax(Home home, SetVar s, IntVar m, Reify r) {
125  IntVar c(home, 0, static_cast<int>(Set::Limits::card));
126  cardinality(home, s, c);
127  // Whether set is not empty
128  BoolVar ne(home, 0, 1);
129  rel(home, c, IRT_GR, 0, ne);
130  if (r.mode() != RM_PMI)
131  rel(home, r.var(), BOT_IMP, ne, 1);
132  max(home, s, m, ne);
133  }
134 
135 }}}
136 
137 namespace Gecode {
138 
139  void
140  rel(Home home, SetVar s, IntRelType rt, IntVar x, Reify r) {
141  GECODE_POST;
142  switch (rt) {
143  case IRT_EQ:
144  {
145  Gecode::Int::IntView xv(x);
146  Set::SingletonView xs(xv);
147  switch (r.mode()) {
148  case RM_EQV:
151  ::post(home,s,xs,r.var())));
152  break;
153  case RM_IMP:
156  ::post(home,s,xs,r.var())));
157  break;
158  case RM_PMI:
161  ::post(home,s,xs,r.var())));
162  break;
163  default:
164  throw Gecode::Int::UnknownReifyMode("Set::rel");
165  }
166  }
167  break;
168  case IRT_NQ:
169  {
170  IntVar c(home, 0, static_cast<int>(Set::Limits::card));
171  cardinality(home, s, c);
172  // Whether set is not empty
173  BoolVar ne(home, 0 , 1);
174  rel(home, c, IRT_GR, 0, ne);
175  // Whether {x} is a subset of s
176  BoolVar ss(home, 0 , 1);
177  rel(home, x, SRT_SUB, s, ss);
178  BoolVar b;
179  switch (r.mode()) {
180  case RM_EQV:
181  b=r.var();
182  break;
183  case RM_IMP:
184  b=BoolVar(home, 0, 1);
185  rel(home, r.var(), BOT_IMP, b, 1);
186  break;
187  case RM_PMI:
188  b=BoolVar(home, 0, 1);
189  rel(home, b, BOT_IMP, r.var(), 1);
190  break;
191  default:
192  throw Gecode::Int::UnknownReifyMode("Set::rel");
193  }
194  BoolVarArgs p(1); p[0]=ne;
195  BoolVarArgs n(1); n[0]=ss;
196  clause(home, BOT_AND, p, n, b);
197  }
198  break;
199  case IRT_LQ:
200  {
202  rel(home, tmp, IRT_LQ, x, r);
203  Gecode::Set::Int::remax(home, s, tmp, r);
204  }
205  break;
206  case IRT_LE:
207  {
209  rel(home, tmp, IRT_LE, x, r);
210  Gecode::Set::Int::remax(home, s, tmp, r);
211  }
212  break;
213  case IRT_GQ:
214  {
216  rel(home, tmp, IRT_GQ, x, r);
217  Gecode::Set::Int::remin(home, s, tmp, r);
218  }
219  break;
220  case IRT_GR:
221  {
223  rel(home, tmp, IRT_GR, x, r);
224  Gecode::Set::Int::remin(home, s, tmp, r);
225  }
226  break;
227  default:
228  throw Int::UnknownRelation("Set::rel");
229  }
230  }
231 
232  void
233  min(Home home, SetVar s, IntVar x){
234  GECODE_POST;
236  }
237 
238  void
239  notMin(Home home, SetVar s, IntVar x){
240  GECODE_POST;
242  }
243 
244  void
245  min(Home home, SetVar s, IntVar x, Reify r){
246  GECODE_POST;
247  switch (r.mode()) {
248  case RM_EQV:
250  ::post(home,s,x,r.var())));
251  break;
252  case RM_IMP:
254  ::post(home,s,x,r.var())));
255  break;
256  case RM_PMI:
258  ::post(home,s,x,r.var())));
259  break;
260  default: throw Gecode::Int::UnknownReifyMode("Set::min");
261  }
262  }
263 
264  void
265  max(Home home, SetVar s, IntVar x){
266  GECODE_POST;
268  }
269 
270  void
271  notMax(Home home, SetVar s, IntVar x){
272  GECODE_POST;
274  }
275 
276  void
277  max(Home home, SetVar s, IntVar x, Reify r){
278  GECODE_POST;
279  switch (r.mode()) {
280  case RM_EQV:
282  ::post(home,s,x,r.var())));
283  break;
284  case RM_IMP:
286  ::post(home,s,x,r.var())));
287  break;
288  case RM_PMI:
290  ::post(home,s,x,r.var())));
291  break;
292  default: throw Gecode::Int::UnknownReifyMode("Set::max");
293  }
294  }
295 
297  SetVar x, IntVar y) {
298  GECODE_POST;
300  weights,x,y));
301  }
302 
303 }
304 
305 // STATISTICS: set-post
void notMin(Home home, SetVar s, IntVar x)
Definition: int.cpp:239
Inverse implication for reification.
Definition: int.hh:850
ReifyMode mode(void) const
Return reification mode.
Definition: reify.hpp:60
Propagator for not maximum element
Definition: int.hh:174
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
Less or equal ( )
Definition: int.hh:909
Conjunction.
Definition: int.hh:932
void remin(Home home, SetVar s, IntVar m, Reify r)
Reify m to be the minimum of s.
Definition: int.cpp:112
Implication.
Definition: int.hh:934
unsigned int cardMin(void) const
Return minimum cardinality.
Definition: set.hpp:86
void remax(Home home, SetVar s, IntVar m, Reify r)
Reify m to be the maximum of s.
Definition: int.cpp:124
Greater ( )
Definition: int.hh:912
const unsigned int card
Maximum cardinality of an integer set.
Definition: set.hh:105
const int max
Largest allowed integer value.
Definition: int.hh:116
Greater or equal ( )
Definition: int.hh:911
const int min
Smallest allowed integer value.
Definition: int.hh:118
Propagator for reified minimum element
Definition: int.hh:115
Gecode::FloatVal c(-8, 8)
Exception: Unknown relation passed as argument
Definition: exception.hpp:91
Reified equality propagator
Definition: rel.hh:174
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Equality ( )
Definition: int.hh:907
Propagator for not minimum element
Definition: int.hh:87
IntRelType
Relation types for integers.
Definition: int.hh:906
Reification specification.
Definition: int.hh:857
struct Gecode::@579::NNF::@61::@62 b
For binary nodes (and, or, eqv)
Subset ( )
Definition: set.hh:648
Less ( )
Definition: int.hh:910
Passing Boolean variables.
Definition: int.hh:693
Singleton set view.
Definition: view.hpp:589
Boolean integer variables.
Definition: int.hh:494
LinIntExpr cardinality(const SetExpr &e)
Cardinality of set expression.
Definition: set-expr.cpp:818
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:784
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:71
Set view for set variables
Definition: view.hpp:60
Propagator for maximum element
Definition: int.hh:147
Integer view for integer variables.
Definition: view.hpp:129
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
Set variables
Definition: set.hh:131
Integer variables.
Definition: int.hh:353
Reified propagator for maximum element
Definition: int.hh:202
void rel(Home home, FloatVar x0, FloatRelType frt, FloatVal n)
Propagates .
Definition: rel.cpp:47
BoolVar var(void) const
Return Boolean control variable.
Definition: reify.hpp:52
Propagator for set equality
Definition: rel.hh:150
void notMax(Home home, SetVar s, IntVar x)
Definition: int.cpp:271
Post propagator for SetVar x
Definition: set.hh:784
Propagator for the negated subset constraint
Definition: rel.hh:90
#define GECODE_ME_FAIL(me)
Check whether modification event me is failed, and fail space home.
Definition: macros.hpp:81
Propagator for weight of a set
Definition: int.hh:261
Exception: Unknown reification mode passed as argument
Definition: exception.hpp:119
Gecode toplevel namespace
void weights(Home home, IntSharedArray elements, IntSharedArray weights, SetVar x, IntVar y)
Definition: int.cpp:296
Implication for reification.
Definition: int.hh:843
Disequality ( )
Definition: int.hh:908
#define GECODE_POST
Check for failure in a constraint post function.
Definition: macros.hpp:44
Home class for posting propagators
Definition: core.hpp:922
#define GECODE_ES_FAIL(es)
Check whether execution status es is failed, and fail space home.
Definition: macros.hpp:107
Shared array with arbitrary number of elements.
Propagator for minimum element
Definition: int.hh:59
TFE post(PropagatorGroup g)
Only post functions (but not propagators) from g are considered.
void clause(Home home, BoolOpType o, const BoolVarArgs &x, const BoolVarArgs &y, int n, IntPropLevel)
Post domain consistent propagator for Boolean clause with positive variables x and negative variables...
Definition: bool.cpp:910
Equivalence for reification (default)
Definition: int.hh:836
Boolean view for Boolean variables.
Definition: view.hpp:1315