Generated on Sat Feb 7 2015 02:01:20 for Gecode by doxygen 1.8.9.1
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: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
17  * $Revision: 13068 $
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  ExecStatus
114  Region r(home);
115 
116  int* count = r.alloc<int>(k.size());
117  for (int i = k.size(); i--; )
118  count[i] = 0;
119 
120  // total number of assigned views
121  int noa = 0;
122  for (int i = y.size(); i--; )
123  if (y[i].assigned()) {
124  noa++;
125  int idx;
126  if (!lookupValue(k,y[i].val(),idx))
127  return ES_FAILED;
128  count[idx]++;
129  if (Card::propagate && (k[idx].max() == 0))
130  return ES_FAILED;
131  }
132 
133  if (noa == y.size()) {
134  // All views are assigned
135  for (int i = k.size(); i--; ) {
136  if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
137  return ES_FAILED;
138  // the solution contains ci occurences of value k[i].card();
139  if (Card::propagate)
140  GECODE_ME_CHECK(k[i].eq(home, count[i]));
141  }
142  return home.ES_SUBSUMED(*this);
143  }
144 
145  // before propagation performs inferences on cardinality variables:
146  if (Card::propagate) {
147  if (noa > 0)
148  for (int i = k.size(); i--; )
149  if (!k[i].assigned()) {
150  GECODE_ME_CHECK(k[i].lq(home, y.size() - (noa - count[i])));
151  GECODE_ME_CHECK(k[i].gq(home, count[i]));
152  }
153 
154  GECODE_ES_CHECK(prop_card<Card>(home,y,k));
155  if (!card_consistent<Card>(y,k))
156  return ES_FAILED;
157  }
158 
159  if (x.size() == 0) {
160  for (int j = k.size(); j--; )
161  if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
162  return ES_FAILED;
163  return home.ES_SUBSUMED(*this);
164  } else if ((x.size() == 1) && (x[0].assigned())) {
165  int idx;
166  if (!lookupValue(k,x[0].val(),idx))
167  return ES_FAILED;
168  GECODE_ME_CHECK(k[idx].inc());
169  for (int j = k.size(); j--; )
170  if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
171  return ES_FAILED;
172  return home.ES_SUBSUMED(*this);
173  }
174 
175  if (vvg == NULL) {
176  int smin = 0;
177  int smax = 0;
178  for (int i=k.size(); i--; )
179  if (k[i].counter() > k[i].max() ) {
180  return ES_FAILED;
181  } else {
182  smax += (k[i].max() - k[i].counter());
183  if (k[i].counter() < k[i].min())
184  smin += (k[i].min() - k[i].counter());
185  }
186 
187  if ((x.size() < smin) || (smax < x.size()))
188  return ES_FAILED;
189 
190  vvg = new (home) VarValGraph<Card>(home, x, k, smin, smax);
191  GECODE_ES_CHECK(vvg->min_require(home,x,k));
192  GECODE_ES_CHECK(vvg->template maximum_matching<UBC>(home));
193  if (!card_fixed)
194  GECODE_ES_CHECK(vvg->template maximum_matching<LBC>(home));
195  } else {
196  GECODE_ES_CHECK(vvg->sync(home,x,k));
197  }
198 
199  vvg->template free_alternating_paths<UBC>(home);
200  vvg->template strongly_connected_components<UBC>(home);
201 
202  GECODE_ES_CHECK(vvg->template narrow<UBC>(home,x,k));
203 
204  if (!card_fixed) {
205  if (Card::propagate)
206  GECODE_ES_CHECK(vvg->sync(home,x,k));
207 
208  vvg->template free_alternating_paths<LBC>(home);
209  vvg->template strongly_connected_components<LBC>(home);
210 
211  GECODE_ES_CHECK(vvg->template narrow<LBC>(home,x,k));
212  }
213 
214  {
215  bool card_assigned = true;
216  if (Card::propagate) {
217  GECODE_ES_CHECK(prop_card<Card>(home, y, k));
218  card_assigned = k.assigned();
219  }
220 
221  if (card_assigned) {
222  if (x.size() == 0) {
223  for (int j=k.size(); j--; )
224  if ((k[j].min() > k[j].counter()) ||
225  (k[j].max() < k[j].counter()))
226  return ES_FAILED;
227  return home.ES_SUBSUMED(*this);
228  } else if ((x.size() == 1) && x[0].assigned()) {
229  int idx;
230  if (!lookupValue(k,x[0].val(),idx))
231  return ES_FAILED;
232  GECODE_ME_CHECK(k[idx].inc());
233 
234  for (int j = k.size(); j--; )
235  if ((k[j].min() > k[j].counter()) ||
236  (k[j].max() < k[j].counter()))
237  return ES_FAILED;
238  return home.ES_SUBSUMED(*this);
239  }
240  }
241  }
242 
243  for (int i = k.size(); i--; )
244  count[i] = 0;
245 
246  bool all_assigned = true;
247  // total number of assigned views
248  for (int i = y.size(); i--; )
249  if (y[i].assigned()) {
250  int idx;
251  if (!lookupValue(k,y[i].val(),idx))
252  return ES_FAILED;
253  count[idx]++;
254  if (Card::propagate && (k[idx].max() == 0))
255  return ES_FAILED;
256  } else {
257  all_assigned = false;
258  }
259 
260  if (Card::propagate)
261  GECODE_ES_CHECK(prop_card<Card>(home, y, k));
262 
263  if (all_assigned) {
264  for (int i = k.size(); i--; ) {
265  if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
266  return ES_FAILED;
267  // the solution contains count[i] occurences of value k[i].card();
268  if (Card::propagate)
269  GECODE_ME_CHECK(k[i].eq(home,count[i]));
270  }
271  return home.ES_SUBSUMED(*this);
272  }
273 
274  if (Card::propagate) {
275  int ysmax = y.size();
276  for (int i=k.size(); i--; )
277  ysmax -= k[i].max();
278  int smax = 0;
279  bool card_ass = true;
280  for (int i = k.size(); i--; ) {
281  GECODE_ME_CHECK(k[i].gq(home, ysmax + k[i].max()));
282  smax += k[i].max();
283  GECODE_ME_CHECK(k[i].lq(home, y.size() + k[i].min()));
284  if (!k[i].assigned())
285  card_ass = false;
286  }
287  if (card_ass && (smax != y.size()))
288  return ES_FAILED;
289  }
290 
291  return Card::propagate ? ES_NOFIX : ES_FIX;
292  }
293 
294  template<class Card>
295  inline ExecStatus
298  GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
299 
300  if (isDistinct<Card>(home, x, k))
301  return Distinct::Dom<IntView>::post(home,x);
302 
303  bool cardfix = true;
304  for (int i = k.size(); i--; )
305  if (!k[i].assigned()) {
306  cardfix = false; break;
307  }
308 
309  (void) new (home) Dom<Card>(home,x,k,cardfix);
310  return ES_OK;
311  }
312 
313 }}}
314 
315 // STATISTICS: int-prop
void update(Space &, bool share, ViewArray< View > &a)
Update array to be a clone of array a.
Definition: array.hpp:1387
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:2973
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1662
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:326
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:57
Base-class for propagators.
Definition: core.hpp:755
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition: dom.hpp:49
Handle to region.
Definition: region.hpp:61
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition: gcc.hh:229
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
Base-class for both propagators and branchers.
Definition: core.hpp:666
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
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)
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition: dom.hpp:107
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition: dom.hpp:296
Domain consistent global cardinality propagator.
Definition: gcc.hh:219
Execution has resulted in failure.
Definition: core.hpp:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
Dom(Space &home, bool share, Dom< Card > &p)
Constructor for cloning p.
Definition: dom.hpp:83
void subscribe(Space &home, Propagator &p, PropCond pc, bool process=true)
Subscribe propagator p with propagation condition pc to variable.
Definition: array.hpp:1400
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
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:45
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition: core.hpp:4023
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntConLevel)
Post propagator for .
Definition: count.cpp:44
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:2877
Propagation cost.
Definition: core.hpp:537
ExecStatus
Definition: core.hpp:523
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
ViewArray< IntView > y
Views used to channel information between x and k ( ).
Definition: gcc.hh:227
#define forceinline
Definition: config.hpp:132
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
Variable-value-graph used during propagation.
Definition: dom-sup.hpp:391
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
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:113