Generated on Thu Apr 5 2018 19:44:19 for Gecode by doxygen 1.8.13
propagate.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  * Copyright:
7  * Patrick Pekczynski, 2004
8  *
9  * Last modified:
10  * $Date$ by $Author$
11  * $Revision$
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 <gecode/int/rel.hh>
39 #include <gecode/int/distinct.hh>
40 
41 namespace Gecode { namespace Int { namespace Sorted {
42 
43 
44  /*
45  * Summary of the propagation algorithm as implemented in the
46  * propagate method below:
47  *
48  * STEP 1: Normalize the domains of the y variables
49  * STEP 2: Sort the domains of the x variables according to their lower
50  * and upper endpoints
51  * STEP 3: Compute the matchings phi and phiprime with
52  * Glover's matching algorithm
53  * STEP 4: Compute the strongly connected components in
54  * the oriented intersection graph
55  * STEP 5: Narrow the domains of the variables
56  *
57  */
58 
75  template<class View, bool Perm>
81  bool& repairpass,
82  bool& nofix,
83  bool& match_fixed){
84 
85  int n = x.size();
86 
87  Region r;
88  int* tau = r.alloc<int>(n);
89  int* phi = r.alloc<int>(n);
90  int* phiprime = r.alloc<int>(n);
92  int* vertices = r.alloc<int>(n);
93 
94  if (match_fixed) {
95  // sorting is determined, sigma and tau coincide
96  for (int i=n; i--; )
97  tau[z[i].val()] = i;
98  } else {
99  for (int i = n; i--; )
100  tau[i] = i;
101  }
102 
103  if (Perm) {
104  // normalized and sorted
105  // collect all bounds
106 
107  Rank* allbnd = r.alloc<Rank>(x.size());
108 #ifndef NDEBUG
109  for (int i=n; i--;)
110  allbnd[i].min = allbnd[i].max = -1;
111 #endif
112  for (int i=n; i--;) {
113  int min = x[i].min();
114  int max = x[i].max();
115  for (int j=0; j<n; j++) {
116  if ( (y[j].min() > min) ||
117  (y[j].min() <= min && min <= y[j].max()) ) {
118  allbnd[i].min = j;
119  break;
120  }
121  }
122  for (int j=n; j--;) {
123  if (y[j].min() > max) {
124  allbnd[i].max = j-1;
125  break;
126  } else if (y[j].min() <= max && min <= y[j].max()) {
127  allbnd[i].max = j;
128  break;
129  }
130  }
131  }
132 
133  for (int i = n; i--; ) {
134  // minimum reachable y-variable
135  int minr = allbnd[i].min;
136  assert(minr != -1);
137  int maxr = allbnd[i].max;
138  assert(maxr != -1);
139 
140  ModEvent me = x[i].gq(home, y[minr].min());
141  if (me_failed(me))
142  return ES_FAILED;
143  nofix |= (me_modified(me) && (x[i].min() != y[minr].min()));
144 
145  me = x[i].lq(home, y[maxr].max());
146  if (me_failed(me))
147  return ES_FAILED;
148  nofix |= (me_modified(me) && (x[i].min() != y[maxr].max()));
149 
150  me = z[i].gq(home, minr);
151  if (me_failed(me))
152  return ES_FAILED;
153  nofix |= (me_modified(me) && (z[i].min() != minr));
154 
155  me = z[i].lq(home, maxr);
156  if (me_failed(me))
157  return ES_FAILED;
158  nofix |= (me_modified(me) && (z[i].max() != maxr));
159  }
160 
161  // channel information from x to y through permutation variables in z
162  if (!channel(home,x,y,z,nofix))
163  return ES_FAILED;
164  if (nofix)
165  return ES_NOFIX;
166  }
167 
168  /*
169  * STEP 1:
170  * normalization is implemented in "order.hpp"
171  * o setting the lower bounds of the y_i domains (\lb E_i)
172  * to max(\lb E_{i-1},\lb E_i)
173  * o setting the upper bounds of the y_i domains (\ub E_i)
174  * to min(\ub E_i,\ub E_{i+1})
175  */
176 
177  if (!normalize(home, y, x, nofix))
178  return ES_FAILED;
179 
180  if (Perm) {
181  // check consistency of channeling after normalization
182  if (!channel(home,x,y,z,nofix))
183  return ES_FAILED;
184  if (nofix)
185  return ES_NOFIX;
186  }
187 
188 
189  // if bounds have changed we have to recreate sigma to restore
190  // optimized dropping of variables
191 
192  sort_sigma<View,Perm>(x,z);
193 
194  bool subsumed = true;
195  bool array_subs = false;
196  int dropfst = 0;
197  bool noperm_bc = false;
198 
199  if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst) ||
200  !array_assigned<View,Perm>(home,x,y,z,array_subs,match_fixed,nofix,noperm_bc))
201  return ES_FAILED;
202 
203  if (subsumed || array_subs)
204  return home.ES_SUBSUMED(p);
205 
206  /*
207  * STEP 2: creating tau
208  * Sort the domains of the x variables according
209  * to their lower bounds, where we use an
210  * intermediate array of integers for sorting
211  */
212  sort_tau<View,Perm>(x,z,tau);
213 
214  /*
215  * STEP 3:
216  * Compute the matchings \phi and \phi' between
217  * the x and the y variables
218  * with Glover's matching algorithm.
219  * o phi is computed with the glover function
220  * o phiprime is computed with the revglover function
221  * glover and revglover are implemented in "matching.hpp"
222  */
223 
224  if (!match_fixed) {
225  if (!glover(x,y,tau,phi,sequence,vertices))
226  return ES_FAILED;
227  } else {
228  for (int i = x.size(); i--; ) {
229  phi[i] = z[i].val();
230  phiprime[i] = phi[i];
231  }
232  }
233 
234  for (int i = n; i--; )
235  if (!y[i].assigned()) {
236  // phiprime is not needed to narrow the domains of the x-variables
237  if (!match_fixed &&
238  !revglover(x,y,tau,phiprime,sequence,vertices))
239  return ES_FAILED;
240 
241  if (!narrow_domy(home,x,y,phi,phiprime,nofix))
242  return ES_FAILED;
243 
244  if (nofix && !match_fixed) {
245  // data structures (matching) destroyed by domains with holes
246 
247  for (int j = y.size(); j--; )
248  phi[j]=phiprime[j]=0;
249 
250  if (!glover(x,y,tau,phi,sequence,vertices))
251  return ES_FAILED;
252 
253  if (!revglover(x,y,tau,phiprime,sequence,vertices))
254  return ES_FAILED;
255 
256  if (!narrow_domy(home,x,y,phi,phiprime,nofix))
257  return ES_FAILED;
258  }
259  break;
260  }
261 
262  if (Perm) {
263  // check consistency of channeling after normalization
264  if (!channel(home,x,y,z,nofix))
265  return ES_FAILED;
266  if (nofix)
267  return ES_NOFIX;
268  }
269 
270  /*
271  * STEP 4:
272  * Compute the strongly connected components in
273  * the oriented intersection graph
274  * the computation of the sccs is implemented in
275  * "narrowing.hpp" in the function narrow_domx
276  */
277 
278  int* scclist = r.alloc<int>(n);
279  SccComponent* sinfo = r.alloc<SccComponent>(n);
280 
281  for(int i = n; i--; )
282  sinfo[i].left=sinfo[i].right=sinfo[i].rightmost=sinfo[i].leftmost= i;
283 
284  computesccs(x,y,phi,sinfo,scclist);
285 
286  /*
287  * STEP 5:
288  * Narrow the domains of the variables
289  * Also implemented in "narrowing.hpp"
290  * in the functions narrow_domx and narrow_domy
291  */
292 
293  if (!narrow_domx<View,Perm>(home,x,y,z,tau,phi,scclist,sinfo,nofix))
294  return ES_FAILED;
295 
296  if (Perm) {
297  if (!noperm_bc &&
298  !perm_bc<View>
299  (home, tau, sinfo, scclist, x,z, repairpass, nofix))
300  return ES_FAILED;
301 
302  // channeling also needed after normal propagation steps
303  // in order to ensure consistency after possible modification in perm_bc
304  if (!channel(home,x,y,z,nofix))
305  return ES_FAILED;
306  if (nofix)
307  return ES_NOFIX;
308  }
309 
310  sort_tau<View,Perm>(x,z,tau);
311 
312  if (Perm) {
313  // special case of sccs of size 2 denoted by permutation variables
314  // used to enforce consistency from x to y
315  // case of the upper bound ordering tau
316  for (int i = x.size() - 1; i--; ) {
317  // two x variables are in the same scc of size 2
318  if (z[tau[i]].min() == z[tau[i+1]].min() &&
319  z[tau[i]].max() == z[tau[i+1]].max() &&
320  z[tau[i]].size() == 2 && z[tau[i]].range()) {
321  // if bounds are strictly smaller
322  if (x[tau[i]].max() < x[tau[i+1]].max()) {
323  ModEvent me = y[z[tau[i]].min()].lq(home, x[tau[i]].max());
324  if (me_failed(me))
325  return ES_FAILED;
326  nofix |= (me_modified(me) &&
327  y[z[tau[i]].min()].max() != x[tau[i]].max());
328 
329  me = y[z[tau[i+1]].max()].lq(home, x[tau[i+1]].max());
330  if (me_failed(me))
331  return ES_FAILED;
332  nofix |= (me_modified(me) &&
333  y[z[tau[i+1]].max()].max() != x[tau[i+1]].max());
334  }
335  }
336  }
337  }
338  return nofix ? ES_NOFIX : ES_FIX;
339  }
340 
341  template<class View, bool Perm>
344  Propagator(home, p),
345  reachable(p.reachable) {
346  x.update(home, p.x);
347  y.update(home, p.y);
348  z.update(home, p.z);
349  w.update(home, p.w);
350  }
351 
352  template<class View, bool Perm>
356  Propagator(home), x(x0), y(y0), z(z0), w(home,y0), reachable(-1) {
357  x.subscribe(home, *this, PC_INT_BND);
358  y.subscribe(home, *this, PC_INT_BND);
359  if (Perm)
360  z.subscribe(home, *this, PC_INT_BND);
361  }
362 
363  template<class View, bool Perm>
364  forceinline size_t
366  x.cancel(home,*this, PC_INT_BND);
367  y.cancel(home,*this, PC_INT_BND);
368  if (Perm)
369  z.cancel(home,*this, PC_INT_BND);
370  (void) Propagator::dispose(home);
371  return sizeof(*this);
372  }
373 
374  template<class View, bool Perm>
376  return new (home) Sorted<View,Perm>(home, *this);
377  }
378 
379  template<class View, bool Perm>
381  return PropCost::linear(PropCost::LO, x.size());
382  }
383 
384  template<class View, bool Perm>
385  void
387  x.reschedule(home, *this, PC_INT_BND);
388  y.reschedule(home, *this, PC_INT_BND);
389  if (Perm)
390  z.reschedule(home, *this, PC_INT_BND);
391  }
392 
393  template<class View, bool Perm>
394  ExecStatus
396  int n = x.size();
397  bool secondpass = false;
398  bool nofix = false;
399  int dropfst = 0;
400 
401  bool subsumed = false;
402  bool array_subs = false;
403  bool match_fixed = false;
404 
405  // normalization of x and y
406  if (!normalize(home, y, x, nofix))
407  return ES_FAILED;
408 
409  // create sigma sorting
410  sort_sigma<View,Perm>(x,z);
411 
412  bool noperm_bc = false;
413  if (!array_assigned<View,Perm>
414  (home, x, y, z, array_subs, match_fixed, nofix, noperm_bc))
415  return ES_FAILED;
416 
417  if (array_subs)
418  return home.ES_SUBSUMED(*this);
419 
420  sort_sigma<View,Perm>(x,z);
421 
422  // in this case check_subsumptions is guaranteed to find
423  // the xs ordered by sigma
424 
425  if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst))
426  return ES_FAILED;
427 
428  if (subsumed)
429  return home.ES_SUBSUMED(*this);
430 
431  if (Perm) {
432  // dropping possibly yields inconsistent indices on permutation variables
433  if (dropfst) {
434  reachable = w[dropfst - 1].max();
435  bool unreachable = true;
436  for (int i = x.size(); unreachable && i-- ; ) {
437  unreachable &= (reachable < x[i].min());
438  }
439 
440  if (unreachable) {
441  x.drop_fst(dropfst, home, *this, PC_INT_BND);
442  y.drop_fst(dropfst, home, *this, PC_INT_BND);
443  z.drop_fst(dropfst, home, *this, PC_INT_BND);
444  } else {
445  dropfst = 0;
446  }
447  }
448 
449  n = x.size();
450 
451  if (n < 2) {
452  if (x[0].max() < y[0].min() || y[0].max() < x[0].min())
453  return ES_FAILED;
454  if (Perm) {
455  GECODE_ME_CHECK(z[0].eq(home, w.size() - 1));
456  }
457  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this), x[0], y[0])));
458  }
459 
460  // check whether shifting the permutation variables
461  // is necessary after dropping x and y vars
462  // highest reachable index
463  int valid = n - 1;
464  int index = 0;
465  int shift = 0;
466 
467  for (int i = n; i--; ){
468  if (z[i].max() > index)
469  index = z[i].max();
470  if (index > valid)
471  shift = index - valid;
472  }
473 
474  if (shift) {
475  ViewArray<OffsetView> ox(home,n), oy(home,n), oz(home,n);
476 
477  for (int i = n; i--; ) {
478  GECODE_ME_CHECK(z[i].gq(home, shift));
479 
480  oz[i] = OffsetView(z[i], -shift);
481  ox[i] = OffsetView(x[i], 0);
482  oy[i] = OffsetView(y[i], 0);
483  }
484 
485  GECODE_ES_CHECK((bounds_propagation<OffsetView,Perm>
486  (home,*this,ox,oy,oz,secondpass,nofix,match_fixed)));
487 
488  if (secondpass) {
489  GECODE_ES_CHECK((bounds_propagation<OffsetView,Perm>
490  (home,*this,ox,oy,oz,secondpass,nofix,match_fixed)));
491  }
492  } else {
493  GECODE_ES_CHECK((bounds_propagation<View,Perm>
494  (home,*this,x,y,z,secondpass,nofix,match_fixed)));
495 
496  if (secondpass) {
497  GECODE_ES_CHECK((bounds_propagation<View,Perm>
498  (home,*this,x,y,z,secondpass,nofix,match_fixed)));
499  }
500  }
501  } else {
502  // dropping has no consequences
503  if (dropfst) {
504  x.drop_fst(dropfst, home, *this, PC_INT_BND);
505  y.drop_fst(dropfst, home, *this, PC_INT_BND);
506  }
507 
508  n = x.size();
509 
510  if (n < 2) {
511  if (x[0].max() < y[0].min() || y[0].max() < x[0].min())
512  return ES_FAILED;
513  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this), x[0], y[0])));
514  }
515 
516  GECODE_ES_CHECK((bounds_propagation<View,Perm>
517  (home, *this, x, y, z,secondpass, nofix, match_fixed)));
518  // no second pass possible if there are no permvars
519  }
520 
521  if (!normalize(home, y, x, nofix))
522  return ES_FAILED;
523 
524  Region r;
525  int* tau = r.alloc<int>(n);
526  if (match_fixed) {
527  // sorting is determined
528  // sigma and tau coincide
529  for (int i = x.size(); i--; ) {
530  int pi = z[i].val();
531  tau[pi] = i;
532  }
533  } else {
534  for (int i = n; i--; ) {
535  tau[i] = i;
536  }
537  }
538 
539  sort_tau<View,Perm>(x,z,tau);
540  // recreate consistency for already assigned subparts
541  // in order of the upper bounds starting at the end of the array
542  bool xbassigned = true;
543  for (int i = x.size(); i--; ) {
544  if (x[tau[i]].assigned() && xbassigned) {
545  GECODE_ME_CHECK(y[i].eq(home, x[tau[i]].val()));
546  } else {
547  xbassigned = false;
548  }
549  }
550 
551  subsumed = true;
552  array_subs = false;
553  noperm_bc = false;
554 
555  // creating sorting anew
556  sort_sigma<View,Perm>(x,z);
557 
558  if (Perm) {
559  for (int i = 0; i < x.size() - 1; i++) {
560  // special case of subsccs of size2 for the lower bounds
561  // two x variables are in the same scc of size 2
562  if (z[i].min() == z[i+1].min() &&
563  z[i].max() == z[i+1].max() &&
564  z[i].size() == 2 && z[i].range()) {
565  if (x[i].min() < x[i+1].min()) {
566  ModEvent me = y[z[i].min()].gq(home, x[i].min());
567  GECODE_ME_CHECK(me);
568  nofix |= (me_modified(me) &&
569  y[z[i].min()].min() != x[i].min());
570 
571  me = y[z[i+1].max()].gq(home, x[i+1].min());
572  GECODE_ME_CHECK(me);
573  nofix |= (me_modified(me) &&
574  y[z[i+1].max()].min() != x[i+1].min());
575  }
576  }
577  }
578  }
579 
580  // check assigned
581  // should be sorted
582  bool xassigned = true;
583  for (int i = 0; i < x.size(); i++) {
584  if (x[i].assigned() && xassigned) {
585  GECODE_ME_CHECK(y[i].eq(home,x[i].val()));
586  } else {
587  xassigned = false;
588  }
589  }
590 
591  // sorted check bounds
592  // final check that variables are consitent with least and greatest possible
593  // values
594  int tlb = std::min(x[0].min(), y[0].min());
595  int tub = std::max(x[x.size() - 1].max(), y[y.size() - 1].max());
596  for (int i = x.size(); i--; ) {
597  ModEvent me = y[i].lq(home, tub);
598  GECODE_ME_CHECK(me);
599  nofix |= me_modified(me) && (y[i].max() != tub);
600 
601  me = y[i].gq(home, tlb);
602  GECODE_ME_CHECK(me);
603  nofix |= me_modified(me) && (y[i].min() != tlb);
604 
605  me = x[i].lq(home, tub);
606  GECODE_ME_CHECK(me);
607  nofix |= me_modified(me) && (x[i].max() != tub);
608 
609  me = x[i].gq(home, tlb);
610  GECODE_ME_CHECK(me);
611  nofix |= me_modified(me) && (x[i].min() != tlb);
612  }
613 
614  if (!array_assigned<View,Perm>
615  (home, x, y, z, array_subs, match_fixed, nofix, noperm_bc))
616  return ES_FAILED;
617 
618  if (array_subs)
619  return home.ES_SUBSUMED(*this);
620 
621  if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst))
622  return ES_FAILED;
623 
624  if (subsumed)
625  return home.ES_SUBSUMED(*this);
626 
627  return nofix ? ES_NOFIX : ES_FIX;
628  }
629 
630  template<class View, bool Perm>
631  ExecStatus
633  post(Home home,
635  int n = x0.size();
636  if (n < 2) {
637  if ((x0[0].max() < y0[0].min()) || (y0[0].max() < x0[0].min()))
638  return ES_FAILED;
639  GECODE_ES_CHECK((Rel::EqBnd<View,View>::post(home,x0[0],y0[0])));
640  if (Perm) {
641  GECODE_ME_CHECK(z0[0].eq(home,0));
642  }
643  } else {
644  if (Perm) {
645  ViewArray<View> z(home,n);
646  for (int i=n; i--; ) {
647  z[i]=z0[i];
648  GECODE_ME_CHECK(z[i].gq(home,0));
649  GECODE_ME_CHECK(z[i].lq(home,n-1));
650  }
652  }
653  new (home) Sorted<View,Perm>(home,x0,y0,z0);
654  }
655  return ES_OK;
656  }
657 
658 }}}
659 
660 // STATISTICS: int-prop
661 
662 
663 
bool glover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phi[], OfflineMinItem sequence[], int vertices[])
Glover&#39;s maximum matching in a bipartite graph.
Definition: matching.hpp:59
ViewArray< View > w
Original y array.
Definition: sorted.hh:72
#define GECODE_REWRITE(prop, post)
Rewrite propagator by executing post function.
Definition: macros.hpp:120
virtual size_t dispose(Space &home)
Delete propagator and return its size.
Definition: propagate.hpp:365
Bounds consistent sortedness propagator.
Definition: sorted.hh:63
bool narrow_domy(Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], int phiprime[], bool &nofix)
Narrowing the domains of the y views.
Definition: narrowing.hpp:226
Storage class for mininmum and maximum of a variable.
Definition: sortsup.hpp:43
bool valid(const FloatVal &n)
Return whether float n is a valid number.
Definition: limits.hpp:43
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1657
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4643
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntPropLevel)
Post propagator for .
Definition: sequence.cpp:51
ExecStatus ES_SUBSUMED(Propagator &p)
Definition: core.hpp:3433
const FloatNum max
Largest allowed float value.
Definition: float.hh:848
Sorted(Home home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z)
Constructor for posting.
Definition: propagate.hpp:354
ExecStatus subsumed(Space &home, Propagator &p, int c, TaskArray< Task > &t)
Check for subsumption (all tasks must be assigned)
Definition: subsumption.hpp:42
T * alloc(long unsigned int n)
Allocate block of n objects of type T from region.
Definition: region.hpp:384
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:53
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition: propagate.hpp:375
Item used to construct the OfflineMin sequence.
Definition: sortsup.hpp:121
int ModEvent
Type for modification events.
Definition: core.hpp:64
Base-class for propagators.
Definition: core.hpp:1016
bool revglover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phiprime[], OfflineMinItem sequence[], int vertices[])
Symmetric glover function for the upper domain bounds.
Definition: matching.hpp:118
Handle to region.
Definition: region.hpp:57
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function returning low linear.
Definition: propagate.hpp:380
#define forceinline
Definition: config.hpp:182
Propagation has computed fixpoint.
Definition: core.hpp:469
Computation spaces.
Definition: core.hpp:1668
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
Definition: order.hpp:97
int reachable
connection to dropped view
Definition: sorted.hh:74
Base-class for both propagators and branchers.
Definition: core.hpp:620
ExecStatus bounds_propagation(Space &home, Propagator &p, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &repairpass, bool &nofix, bool &match_fixed)
Perform bounds consistent sortedness propagation.
Definition: propagate.hpp:77
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:95
bool channel(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, bool &nofix)
Channel between x, y and z.
Definition: sortsup.hpp:494
int p
Number of positive literals for node type.
Definition: bool-expr.cpp:236
const FloatNum min
Smallest allowed float value.
Definition: float.hh:850
Gecode::IntArgs i(4, 1, 2, 3, 4)
int min
stores the mininmum of a variable
Definition: sortsup.hpp:46
int n
Number of negative literals for node type.
Definition: bool-expr.cpp:238
Execution has resulted in failure.
Definition: core.hpp:466
const Gecode::PropCond PC_INT_BND
Propagate when minimum or maximum of a view changes.
Definition: var-type.hpp:91
Binary bounds consistent equality propagator.
Definition: rel.hh:137
const int * pi[]
Definition: photo.cpp:14266
Post propagator for SetVar SetOpType SetVar SetRelType SetVar z
Definition: set.hh:769
Offset integer view.
Definition: view.hpp:426
View arrays.
Definition: array.hpp:228
ViewArray< View > z
Permutation variables (none, if Perm is false)
Definition: sorted.hh:70
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:56
Representation of a strongly connected component.
Definition: sortsup.hpp:57
ViewArray< View > y
Views denoting the sorted version of x.
Definition: sorted.hh:68
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:769
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:769
static ExecStatus post(Home home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z)
Post propagator for views x, y, and z.
Definition: propagate.hpp:633
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition: propagate.hpp:395
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition: core.hpp:3172
Propagation cost.
Definition: core.hpp:478
ExecStatus
Definition: core.hpp:464
bool assigned(View x, int v)
Whether x is assigned to value v.
Definition: single.hpp:47
int max
stores the mininmum of a variable
Definition: sortsup.hpp:48
ViewArray< View > x
Views to be sorted.
Definition: sorted.hh:66
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
Post propagator for SetVar x
Definition: set.hh:769
Execution is okay.
Definition: core.hpp:468
Propagation has not computed fixpoint.
Definition: core.hpp:467
void computesccs(ViewArray< View > &x, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
Compute the sccs of the oriented intersection-graph.
Definition: narrowing.hpp:58
Bounds consistent distinct propagator.
Definition: distinct.hh:129
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
Definition: core.hpp:91
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1203
Home class for posting propagators
Definition: core.hpp:846
virtual void reschedule(Space &home)
Schedule function.
Definition: propagate.hpp:386
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58