Generated on Sat Jun 2 2018 07:17:44 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  * 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 namespace Gecode { namespace Int { namespace GCC {
41 
42  /*
43  * Analogously to "gcc/bnd.hpp" we split the algorithm
44  * in two parts:
45  * 1) the UBC (Upper Bound Constraint) stating that there are
46  * at most k[i].max() occurences of the value v_i
47  * 2) the LBC (Lower Bound Constraint) stating that there are
48  * at least k[i].min() occurences of the value v_i
49  *
50  * The algorithm proceeds in 5 STEPS:
51  *
52  * STEP 1:
53  * Build the bipartite value-graph G=(<X,D>,E),
54  * with X = all variable nodes (each variable forms a node)
55  * D = all value nodes (union over all domains of the variables)
56  * and (x_i,v) is an edge in G iff value v is in the domain D_i of x_i
57  *
58  * STEP 2: Compute a matching in the value graph.
59  * STEP 3: Compute all even alternating paths from unmatched nodes
60  * STEP 4: Compute strongly connected components in the merged graph
61  * STEP 5: Update the Domains according to the computed edges
62  *
63  */
64 
65  template<class Card>
66  inline
68  ViewArray<Card>& k0, bool cf)
69  : Propagator(home), x(x0), y(home, x0),
70  k(k0), vvg(NULL), card_fixed(cf){
71  // y is used for bounds propagation since prop_bnd needs all variables
72  // values within the domain bounds
73  x.subscribe(home, *this, PC_INT_DOM);
74  k.subscribe(home, *this, PC_INT_DOM);
75  }
76 
77  template<class Card>
80  : Propagator(home, p), vvg(NULL), card_fixed(p.card_fixed) {
81  x.update(home, p.x);
82  y.update(home, p.y);
83  k.update(home, p.k);
84  }
85 
86  template<class Card>
87  forceinline size_t
89  x.cancel(home,*this, PC_INT_DOM);
90  k.cancel(home,*this, PC_INT_DOM);
91  (void) Propagator::dispose(home);
92  return sizeof(*this);
93  }
94 
95  template<class Card>
96  Actor*
98  return new (home) Dom<Card>(home, *this);
99  }
100 
101  template<class Card>
102  PropCost
103  Dom<Card>::cost(const Space&, const ModEventDelta&) const {
104  return PropCost::cubic(PropCost::LO, x.size());
105  }
106 
107  template<class Card>
108  void
110  x.reschedule(home, *this, PC_INT_DOM);
111  k.reschedule(home, *this, PC_INT_DOM);
112  }
113 
114  template<class Card>
115  ExecStatus
117  Region r;
118 
119  int* count = r.alloc<int>(k.size());
120  for (int i = k.size(); i--; )
121  count[i] = 0;
122 
123  // total number of assigned views
124  int noa = 0;
125  for (int i = y.size(); i--; )
126  if (y[i].assigned()) {
127  noa++;
128  int idx;
129  if (!lookupValue(k,y[i].val(),idx))
130  return ES_FAILED;
131  count[idx]++;
132  if (Card::propagate && (k[idx].max() == 0))
133  return ES_FAILED;
134  }
135 
136  if (noa == y.size()) {
137  // All views are assigned
138  for (int i = k.size(); i--; ) {
139  if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
140  return ES_FAILED;
141  // the solution contains ci occurences of value k[i].card();
142  if (Card::propagate)
143  GECODE_ME_CHECK(k[i].eq(home, count[i]));
144  }
145  return home.ES_SUBSUMED(*this);
146  }
147 
148  // before propagation performs inferences on cardinality variables:
149  if (Card::propagate) {
150  if (noa > 0)
151  for (int i = k.size(); i--; )
152  if (!k[i].assigned()) {
153  GECODE_ME_CHECK(k[i].lq(home, y.size() - (noa - count[i])));
154  GECODE_ME_CHECK(k[i].gq(home, count[i]));
155  }
156 
157  GECODE_ES_CHECK(prop_card<Card>(home,y,k));
158  if (!card_consistent<Card>(y,k))
159  return ES_FAILED;
160  }
161 
162  if (x.size() == 0) {
163  for (int j = k.size(); j--; )
164  if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
165  return ES_FAILED;
166  return home.ES_SUBSUMED(*this);
167  } else if ((x.size() == 1) && (x[0].assigned())) {
168  int idx;
169  if (!lookupValue(k,x[0].val(),idx))
170  return ES_FAILED;
171  GECODE_ME_CHECK(k[idx].inc());
172  for (int j = k.size(); j--; )
173  if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
174  return ES_FAILED;
175  return home.ES_SUBSUMED(*this);
176  }
177 
178  if (vvg == NULL) {
179  int smin = 0;
180  int smax = 0;
181  for (int i=k.size(); i--; )
182  if (k[i].counter() > k[i].max() ) {
183  return ES_FAILED;
184  } else {
185  smax += (k[i].max() - k[i].counter());
186  if (k[i].counter() < k[i].min())
187  smin += (k[i].min() - k[i].counter());
188  }
189 
190  if ((x.size() < smin) || (smax < x.size()))
191  return ES_FAILED;
192 
193  vvg = new (home) VarValGraph<Card>(home, x, k, smin, smax);
194  GECODE_ES_CHECK(vvg->min_require(home,x,k));
195  GECODE_ES_CHECK(vvg->template maximum_matching<UBC>());
196  if (!card_fixed)
197  GECODE_ES_CHECK(vvg->template maximum_matching<LBC>());
198  } else {
199  GECODE_ES_CHECK(vvg->sync(x,k));
200  }
201 
202  vvg->template free_alternating_paths<UBC>();
203  vvg->template strongly_connected_components<UBC>();
204 
205  GECODE_ES_CHECK(vvg->template narrow<UBC>(home,x,k));
206 
207  if (!card_fixed) {
208  if (Card::propagate)
209  GECODE_ES_CHECK(vvg->sync(x,k));
210 
211  vvg->template free_alternating_paths<LBC>();
212  vvg->template strongly_connected_components<LBC>();
213 
214  GECODE_ES_CHECK(vvg->template narrow<LBC>(home,x,k));
215  }
216 
217  {
218  bool card_assigned = true;
219  if (Card::propagate) {
220  GECODE_ES_CHECK(prop_card<Card>(home, y, k));
221  card_assigned = k.assigned();
222  }
223 
224  if (card_assigned) {
225  if (x.size() == 0) {
226  for (int j=k.size(); j--; )
227  if ((k[j].min() > k[j].counter()) ||
228  (k[j].max() < k[j].counter()))
229  return ES_FAILED;
230  return home.ES_SUBSUMED(*this);
231  } else if ((x.size() == 1) && x[0].assigned()) {
232  int idx;
233  if (!lookupValue(k,x[0].val(),idx))
234  return ES_FAILED;
235  GECODE_ME_CHECK(k[idx].inc());
236 
237  for (int j = k.size(); j--; )
238  if ((k[j].min() > k[j].counter()) ||
239  (k[j].max() < k[j].counter()))
240  return ES_FAILED;
241  return home.ES_SUBSUMED(*this);
242  }
243  }
244  }
245 
246  for (int i = k.size(); i--; )
247  count[i] = 0;
248 
249  bool all_assigned = true;
250  // total number of assigned views
251  for (int i = y.size(); i--; )
252  if (y[i].assigned()) {
253  int idx;
254  if (!lookupValue(k,y[i].val(),idx))
255  return ES_FAILED;
256  count[idx]++;
257  if (Card::propagate && (k[idx].max() == 0))
258  return ES_FAILED;
259  } else {
260  all_assigned = false;
261  }
262 
263  if (Card::propagate)
264  GECODE_ES_CHECK(prop_card<Card>(home, y, k));
265 
266  if (all_assigned) {
267  for (int i = k.size(); i--; ) {
268  if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
269  return ES_FAILED;
270  // the solution contains count[i] occurences of value k[i].card();
271  if (Card::propagate)
272  GECODE_ME_CHECK(k[i].eq(home,count[i]));
273  }
274  return home.ES_SUBSUMED(*this);
275  }
276 
277  if (Card::propagate) {
278  int ysmax = y.size();
279  for (int i=k.size(); i--; )
280  ysmax -= k[i].max();
281  int smax = 0;
282  bool card_ass = true;
283  for (int i = k.size(); i--; ) {
284  GECODE_ME_CHECK(k[i].gq(home, ysmax + k[i].max()));
285  smax += k[i].max();
286  GECODE_ME_CHECK(k[i].lq(home, y.size() + k[i].min()));
287  if (!k[i].assigned())
288  card_ass = false;
289  }
290  if (card_ass && (smax != y.size()))
291  return ES_FAILED;
292  }
293 
294  return Card::propagate ? ES_NOFIX : ES_FIX;
295  }
296 
297  template<class Card>
298  inline ExecStatus
301  GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
302 
303  if (isDistinct<Card>(x,k))
304  return Distinct::Dom<IntView>::post(home,x);
305 
306  bool cardfix = true;
307  for (int i = k.size(); i--; )
308  if (!k[i].assigned()) {
309  cardfix = false; break;
310  }
311 
312  (void) new (home) Dom<Card>(home,x,k,cardfix);
313  return ES_OK;
314  }
315 
316 }}}
317 
318 // STATISTICS: int-prop
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: dom.hpp:97
virtual void reschedule(Space &home)
Schedule function.
Definition: dom.hpp:109
void reschedule(Space &home, Propagator &p, PropCond pc)
Re-schedule propagator p with propagation condition pc.
Definition: array.hpp:1413
void update(Space &home, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1371
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3482
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel)
Post propagator for .
Definition: count.cpp:40
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:380
bool card_fixed
Stores whether cardinalities are all assigned.
Definition: gcc.hh:238
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition: view.hpp:45
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:49
Base-class for propagators.
Definition: core.hpp:1023
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition: dom.hpp:45
void subscribe(Space &home, Propagator &p, PropCond pc, bool schedule=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1384
Handle to region.
Definition: region.hpp:53
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition: gcc.hh:229
#define forceinline
Definition: config.hpp:185
Propagation has computed fixpoint.
Definition: core.hpp:476
Computation spaces.
Definition: core.hpp:1701
Base-class for both propagators and branchers.
Definition: core.hpp:627
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:232
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:299
Domain consistent global cardinality propagator.
Definition: gcc.hh:219
Execution has resulted in failure.
Definition: core.hpp:473
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: dom.hpp:103
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:88
void cancel(Space &home, Propagator &p, PropCond pc)
Cancel subscription of propagator p with propagation condition pc to all views.
Definition: array.hpp:1392
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:765
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:67
Post propagator for SetVar SetOpType SetVar y
Definition: set.hh:765
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:4697
Dom(Space &home, Dom< Card > &p)
Constructor for cloning p.
Definition: dom.hpp:79
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3209
Propagation cost.
Definition: core.hpp:485
ExecStatus
Definition: core.hpp:471
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:43
bool assigned(void) const
Test if all variables are assigned.
Definition: array.hpp:1420
ViewArray< IntView > y
Views used to channel information between x and k ( ).
Definition: gcc.hh:227
Post propagator for SetVar x
Definition: set.hh:765
Execution is okay.
Definition: core.hpp:475
Propagation has not computed fixpoint.
Definition: core.hpp:474
Variable-value-graph used during propagation.
Definition: dom-sup.hpp:387
Gecode toplevel namespace
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1199
int ModEventDelta
Modification event deltas.
Definition: core.hpp:89
Home class for posting propagators
Definition: core.hpp:853
VarValGraph< Card > * vvg
Propagation is performed on a variable-value graph (used as cache)
Definition: gcc.hh:231
ViewArray< IntView > x
Views on which to perform domain-propagation.
Definition: gcc.hh:222
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: dom.hpp:116