Generated on Tue Jul 18 2017 18:41:42 for Gecode by doxygen 1.8.13
dom.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5  *
6  * Contributing authors:
7  * Christian Schulte <schulte@gecode.org>
8  * Guido Tack <tack@gecode.org>
9  *
10  * Copyright:
11  * Patrick Pekczynski, 2004
12  * Christian Schulte, 2009
13  * Guido Tack, 2009
14  *
15  * Last modified:
16  * $Date: 2016-06-29 17:28:17 +0200 (Wed, 29 Jun 2016) $ by $Author: schulte $
17  * $Revision: 15137 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 namespace Gecode { namespace Int { namespace GCC {
45 
46  /*
47  * Analogously to "gcc/bnd.hpp" we split the algorithm
48  * in two parts:
49  * 1) the UBC (Upper Bound Constraint) stating that there are
50  * at most k[i].max() occurences of the value v_i
51  * 2) the LBC (Lower Bound Constraint) stating that there are
52  * at least k[i].min() occurences of the value v_i
53  *
54  * The algorithm proceeds in 5 STEPS:
55  *
56  * STEP 1:
57  * Build the bipartite value-graph G=(<X,D>,E),
58  * with X = all variable nodes (each variable forms a node)
59  * D = all value nodes (union over all domains of the variables)
60  * and (x_i,v) is an edge in G iff value v is in the domain D_i of x_i
61  *
62  * STEP 2: Compute a matching in the value graph.
63  * STEP 3: Compute all even alternating paths from unmatched nodes
64  * STEP 4: Compute strongly connected components in the merged graph
65  * STEP 5: Update the Domains according to the computed edges
66  *
67  */
68 
69  template<class Card>
70  inline
72  ViewArray<Card>& k0, bool cf)
73  : Propagator(home), x(x0), y(home, x0),
74  k(k0), vvg(NULL), card_fixed(cf){
75  // y is used for bounds propagation since prop_bnd needs all variables
76  // values within the domain bounds
77  x.subscribe(home, *this, PC_INT_DOM);
78  k.subscribe(home, *this, PC_INT_DOM);
79  }
80 
81  template<class Card>
83  Dom<Card>::Dom(Space& home, bool share, Dom<Card>& p)
84  : Propagator(home, share, p), vvg(NULL), card_fixed(p.card_fixed) {
85  x.update(home, share, p.x);
86  y.update(home, share, p.y);
87  k.update(home, share, p.k);
88  }
89 
90  template<class Card>
91  forceinline size_t
93  x.cancel(home,*this, PC_INT_DOM);
94  k.cancel(home,*this, PC_INT_DOM);
95  (void) Propagator::dispose(home);
96  return sizeof(*this);
97  }
98 
99  template<class Card>
100  Actor*
101  Dom<Card>::copy(Space& home, bool share) {
102  return new (home) Dom<Card>(home, share, *this);
103  }
104 
105  template<class Card>
106  PropCost
107  Dom<Card>::cost(const Space&, const ModEventDelta&) const {
108  return PropCost::cubic(PropCost::LO, x.size());
109  }
110 
111  template<class Card>
112  void
114  x.reschedule(home, *this, PC_INT_DOM);
115  k.reschedule(home, *this, PC_INT_DOM);
116  }
117 
118  template<class Card>
119  ExecStatus
121  Region r(home);
122 
123  int* count = r.alloc<int>(k.size());
124  for (int i = k.size(); i--; )
125  count[i] = 0;
126 
127  // total number of assigned views
128  int noa = 0;
129  for (int i = y.size(); i--; )
130  if (y[i].assigned()) {
131  noa++;
132  int idx;
133  if (!lookupValue(k,y[i].val(),idx))
134  return ES_FAILED;
135  count[idx]++;
136  if (Card::propagate && (k[idx].max() == 0))
137  return ES_FAILED;
138  }
139 
140  if (noa == y.size()) {
141  // All views are assigned
142  for (int i = k.size(); i--; ) {
143  if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
144  return ES_FAILED;
145  // the solution contains ci occurences of value k[i].card();
146  if (Card::propagate)
147  GECODE_ME_CHECK(k[i].eq(home, count[i]));
148  }
149  return home.ES_SUBSUMED(*this);
150  }
151 
152  // before propagation performs inferences on cardinality variables:
153  if (Card::propagate) {
154  if (noa > 0)
155  for (int i = k.size(); i--; )
156  if (!k[i].assigned()) {
157  GECODE_ME_CHECK(k[i].lq(home, y.size() - (noa - count[i])));
158  GECODE_ME_CHECK(k[i].gq(home, count[i]));
159  }
160 
161  GECODE_ES_CHECK(prop_card<Card>(home,y,k));
162  if (!card_consistent<Card>(y,k))
163  return ES_FAILED;
164  }
165 
166  if (x.size() == 0) {
167  for (int j = k.size(); j--; )
168  if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
169  return ES_FAILED;
170  return home.ES_SUBSUMED(*this);
171  } else if ((x.size() == 1) && (x[0].assigned())) {
172  int idx;
173  if (!lookupValue(k,x[0].val(),idx))
174  return ES_FAILED;
175  GECODE_ME_CHECK(k[idx].inc());
176  for (int j = k.size(); j--; )
177  if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
178  return ES_FAILED;
179  return home.ES_SUBSUMED(*this);
180  }
181 
182  if (vvg == NULL) {
183  int smin = 0;
184  int smax = 0;
185  for (int i=k.size(); i--; )
186  if (k[i].counter() > k[i].max() ) {
187  return ES_FAILED;
188  } else {
189  smax += (k[i].max() - k[i].counter());
190  if (k[i].counter() < k[i].min())
191  smin += (k[i].min() - k[i].counter());
192  }
193 
194  if ((x.size() < smin) || (smax < x.size()))
195  return ES_FAILED;
196 
197  vvg = new (home) VarValGraph<Card>(home, x, k, smin, smax);
198  GECODE_ES_CHECK(vvg->min_require(home,x,k));
199  GECODE_ES_CHECK(vvg->template maximum_matching<UBC>(home));
200  if (!card_fixed)
201  GECODE_ES_CHECK(vvg->template maximum_matching<LBC>(home));
202  } else {
203  GECODE_ES_CHECK(vvg->sync(home,x,k));
204  }
205 
206  vvg->template free_alternating_paths<UBC>(home);
207  vvg->template strongly_connected_components<UBC>(home);
208 
209  GECODE_ES_CHECK(vvg->template narrow<UBC>(home,x,k));
210 
211  if (!card_fixed) {
212  if (Card::propagate)
213  GECODE_ES_CHECK(vvg->sync(home,x,k));
214 
215  vvg->template free_alternating_paths<LBC>(home);
216  vvg->template strongly_connected_components<LBC>(home);
217 
218  GECODE_ES_CHECK(vvg->template narrow<LBC>(home,x,k));
219  }
220 
221  {
222  bool card_assigned = true;
223  if (Card::propagate) {
224  GECODE_ES_CHECK(prop_card<Card>(home, y, k));
225  card_assigned = k.assigned();
226  }
227 
228  if (card_assigned) {
229  if (x.size() == 0) {
230  for (int j=k.size(); j--; )
231  if ((k[j].min() > k[j].counter()) ||
232  (k[j].max() < k[j].counter()))
233  return ES_FAILED;
234  return home.ES_SUBSUMED(*this);
235  } else if ((x.size() == 1) && x[0].assigned()) {
236  int idx;
237  if (!lookupValue(k,x[0].val(),idx))
238  return ES_FAILED;
239  GECODE_ME_CHECK(k[idx].inc());
240 
241  for (int j = k.size(); j--; )
242  if ((k[j].min() > k[j].counter()) ||
243  (k[j].max() < k[j].counter()))
244  return ES_FAILED;
245  return home.ES_SUBSUMED(*this);
246  }
247  }
248  }
249 
250  for (int i = k.size(); i--; )
251  count[i] = 0;
252 
253  bool all_assigned = true;
254  // total number of assigned views
255  for (int i = y.size(); i--; )
256  if (y[i].assigned()) {
257  int idx;
258  if (!lookupValue(k,y[i].val(),idx))
259  return ES_FAILED;
260  count[idx]++;
261  if (Card::propagate && (k[idx].max() == 0))
262  return ES_FAILED;
263  } else {
264  all_assigned = false;
265  }
266 
267  if (Card::propagate)
268  GECODE_ES_CHECK(prop_card<Card>(home, y, k));
269 
270  if (all_assigned) {
271  for (int i = k.size(); i--; ) {
272  if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
273  return ES_FAILED;
274  // the solution contains count[i] occurences of value k[i].card();
275  if (Card::propagate)
276  GECODE_ME_CHECK(k[i].eq(home,count[i]));
277  }
278  return home.ES_SUBSUMED(*this);
279  }
280 
281  if (Card::propagate) {
282  int ysmax = y.size();
283  for (int i=k.size(); i--; )
284  ysmax -= k[i].max();
285  int smax = 0;
286  bool card_ass = true;
287  for (int i = k.size(); i--; ) {
288  GECODE_ME_CHECK(k[i].gq(home, ysmax + k[i].max()));
289  smax += k[i].max();
290  GECODE_ME_CHECK(k[i].lq(home, y.size() + k[i].min()));
291  if (!k[i].assigned())
292  card_ass = false;
293  }
294  if (card_ass && (smax != y.size()))
295  return ES_FAILED;
296  }
297 
298  return Card::propagate ? ES_NOFIX : ES_FIX;
299  }
300 
301  template<class Card>
302  inline ExecStatus
305  GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
306 
307  if (isDistinct<Card>(home, x, k))
308  return Distinct::Dom<IntView>::post(home,x);
309 
310  bool cardfix = true;
311  for (int i = k.size(); i--; )
312  if (!k[i].assigned()) {
313  cardfix = false; break;
314  }
315 
316  (void) new (home) Dom<Card>(home,x,k,cardfix);
317  return ES_OK;
318  }
319 
320 }}}
321 
322 // STATISTICS: int-prop
virtual void reschedule(Space &home)
Schedule function.
Definition: dom.hpp:113
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: array.hpp:1429
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3614
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:44
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
bool card_fixed
Stores whether cardinalities are all assigned.
Definition: gcc.hh:242
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition: view.hpp:48
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
Base-class for propagators.
Definition: core.hpp:1092
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition: dom.hpp:49
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
Handle to region.
Definition: region.hpp:61
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition: gcc.hh:233
Propagation has computed fixpoint.
Definition: core.hpp:545
Computation spaces.
Definition: core.hpp:1748
Base-class for both propagators and branchers.
Definition: core.hpp:696
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
virtual Actor * copy(Space &home, bool share)
Copy propagator during cloning.
Definition: dom.hpp:101
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
Gecode::IntArgs i(4, 1, 2, 3, 4)
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition: dom.hpp:303
Domain consistent global cardinality propagator.
Definition: gcc.hh:223
Execution has resulted in failure.
Definition: core.hpp:542
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: dom.hpp:107
Dom(Space &home, bool share, Dom< Card > &p)
Constructor for cloning p.
Definition: dom.hpp:83
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition: var-type.hpp:100
virtual size_t dispose(Space &home)
Destructor.
Definition: dom.hpp:92
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1408
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
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
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:784
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:4823
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3354
Propagation cost.
Definition: core.hpp:554
ExecStatus
Definition: core.hpp:540
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1436
ViewArray< IntView > y
Views used to channel information between x and k ( ).
Definition: gcc.hh:231
#define forceinline
Definition: config.hpp:173
Post propagator for SetVar x
Definition: set.hh:784
Execution is okay.
Definition: core.hpp:544
Propagation has not computed fixpoint.
Definition: core.hpp:543
Variable-value-graph used during propagation.
Definition: dom-sup.hpp:391
Gecode toplevel namespace
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
int ModEventDelta
Modification event deltas.
Definition: core.hpp:169
Home class for posting propagators
Definition: core.hpp:922
VarValGraph< Card > * vvg
Propagation is performed on a variable-value graph (used as cache)
Definition: gcc.hh:235
ViewArray< IntView > x
Views on which to perform domain-propagation.
Definition: gcc.hh:226
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: dom.hpp:120