Generated on Sat Feb 7 2015 02:01:19 for Gecode by doxygen 1.8.9.1
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: 2013-09-30 13:48:20 +0200 (Mon, 30 Sep 2013) $ by $Author: tack $
11  * $Revision: 14017 $
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>
79  ViewArray<View>& y,
80  ViewArray<View>& z,
81  bool& repairpass,
82  bool& nofix,
83  bool& match_fixed){
84 
85  int n = x.size();
86 
87  Region r(home);
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>(home,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(home,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>
343  Sorted(Space& home, bool share, Sorted<View,Perm>& p):
344  Propagator(home, share, p),
345  reachable(p.reachable) {
346  x.update(home, share, p.x);
347  y.update(home, share, p.y);
348  z.update(home, share, p.z);
349  w.update(home, share, 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>
375  Actor* Sorted<View,Perm>::copy(Space& home, bool share) {
376  return new (home) Sorted<View,Perm>(home, share, *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  ExecStatus
387  int n = x.size();
388  bool secondpass = false;
389  bool nofix = false;
390  int dropfst = 0;
391 
392  bool subsumed = false;
393  bool array_subs = false;
394  bool match_fixed = false;
395 
396  // normalization of x and y
397  if (!normalize(home, y, x, nofix))
398  return ES_FAILED;
399 
400  // create sigma sorting
401  sort_sigma<View,Perm>(home,x,z);
402 
403  bool noperm_bc = false;
404  if (!array_assigned<View,Perm>
405  (home, x, y, z, array_subs, match_fixed, nofix, noperm_bc))
406  return ES_FAILED;
407 
408  if (array_subs)
409  return home.ES_SUBSUMED(*this);
410 
411  sort_sigma<View,Perm>(home,x,z);
412 
413  // in this case check_subsumptions is guaranteed to find
414  // the xs ordered by sigma
415 
416  if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst))
417  return ES_FAILED;
418 
419  if (subsumed)
420  return home.ES_SUBSUMED(*this);
421 
422  if (Perm) {
423  // dropping possibly yields inconsistent indices on permutation variables
424  if (dropfst) {
425  reachable = w[dropfst - 1].max();
426  bool unreachable = true;
427  for (int i = x.size(); unreachable && i-- ; ) {
428  unreachable &= (reachable < x[i].min());
429  }
430 
431  if (unreachable) {
432  x.drop_fst(dropfst, home, *this, PC_INT_BND);
433  y.drop_fst(dropfst, home, *this, PC_INT_BND);
434  z.drop_fst(dropfst, home, *this, PC_INT_BND);
435  } else {
436  dropfst = 0;
437  }
438  }
439 
440  n = x.size();
441 
442  if (n < 2) {
443  if (x[0].max() < y[0].min() || y[0].max() < x[0].min())
444  return ES_FAILED;
445  if (Perm) {
446  GECODE_ME_CHECK(z[0].eq(home, w.size() - 1));
447  }
448  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this), x[0], y[0])));
449  }
450 
451  // check whether shifting the permutation variables
452  // is necessary after dropping x and y vars
453  // highest reachable index
454  int valid = n - 1;
455  int index = 0;
456  int shift = 0;
457 
458  for (int i = n; i--; ){
459  if (z[i].max() > index)
460  index = z[i].max();
461  if (index > valid)
462  shift = index - valid;
463  }
464 
465  if (shift) {
466  ViewArray<OffsetView> ox(home,n), oy(home,n), oz(home,n);
467 
468  for (int i = n; i--; ) {
469  GECODE_ME_CHECK(z[i].gq(home, shift));
470 
471  oz[i] = OffsetView(z[i], -shift);
472  ox[i] = OffsetView(x[i], 0);
473  oy[i] = OffsetView(y[i], 0);
474  }
475 
476  GECODE_ES_CHECK((bounds_propagation<OffsetView,Perm>
477  (home,*this,ox,oy,oz,secondpass,nofix,match_fixed)));
478 
479  if (secondpass) {
480  GECODE_ES_CHECK((bounds_propagation<OffsetView,Perm>
481  (home,*this,ox,oy,oz,secondpass,nofix,match_fixed)));
482  }
483  } else {
484  GECODE_ES_CHECK((bounds_propagation<View,Perm>
485  (home,*this,x,y,z,secondpass,nofix,match_fixed)));
486 
487  if (secondpass) {
488  GECODE_ES_CHECK((bounds_propagation<View,Perm>
489  (home,*this,x,y,z,secondpass,nofix,match_fixed)));
490  }
491  }
492  } else {
493  // dropping has no consequences
494  if (dropfst) {
495  x.drop_fst(dropfst, home, *this, PC_INT_BND);
496  y.drop_fst(dropfst, home, *this, PC_INT_BND);
497  }
498 
499  n = x.size();
500 
501  if (n < 2) {
502  if (x[0].max() < y[0].min() || y[0].max() < x[0].min())
503  return ES_FAILED;
504  GECODE_REWRITE(*this,(Rel::EqBnd<View,View>::post(home(*this), x[0], y[0])));
505  }
506 
507  GECODE_ES_CHECK((bounds_propagation<View,Perm>
508  (home, *this, x, y, z,secondpass, nofix, match_fixed)));
509  // no second pass possible if there are no permvars
510  }
511 
512  if (!normalize(home, y, x, nofix))
513  return ES_FAILED;
514 
515  Region r(home);
516  int* tau = r.alloc<int>(n);
517  if (match_fixed) {
518  // sorting is determined
519  // sigma and tau coincide
520  for (int i = x.size(); i--; ) {
521  int pi = z[i].val();
522  tau[pi] = i;
523  }
524  } else {
525  for (int i = n; i--; ) {
526  tau[i] = i;
527  }
528  }
529 
530  sort_tau<View,Perm>(x,z,tau);
531  // recreate consistency for already assigned subparts
532  // in order of the upper bounds starting at the end of the array
533  bool xbassigned = true;
534  for (int i = x.size(); i--; ) {
535  if (x[tau[i]].assigned() && xbassigned) {
536  GECODE_ME_CHECK(y[i].eq(home, x[tau[i]].val()));
537  } else {
538  xbassigned = false;
539  }
540  }
541 
542  subsumed = true;
543  array_subs = false;
544  noperm_bc = false;
545 
546  // creating sorting anew
547  sort_sigma<View,Perm>(home,x,z);
548 
549  if (Perm) {
550  for (int i = 0; i < x.size() - 1; i++) {
551  // special case of subsccs of size2 for the lower bounds
552  // two x variables are in the same scc of size 2
553  if (z[i].min() == z[i+1].min() &&
554  z[i].max() == z[i+1].max() &&
555  z[i].size() == 2 && z[i].range()) {
556  if (x[i].min() < x[i+1].min()) {
557  ModEvent me = y[z[i].min()].gq(home, x[i].min());
558  GECODE_ME_CHECK(me);
559  nofix |= (me_modified(me) &&
560  y[z[i].min()].min() != x[i].min());
561 
562  me = y[z[i+1].max()].gq(home, x[i+1].min());
563  GECODE_ME_CHECK(me);
564  nofix |= (me_modified(me) &&
565  y[z[i+1].max()].min() != x[i+1].min());
566  }
567  }
568  }
569  }
570 
571  // check assigned
572  // should be sorted
573  bool xassigned = true;
574  for (int i = 0; i < x.size(); i++) {
575  if (x[i].assigned() && xassigned) {
576  GECODE_ME_CHECK(y[i].eq(home,x[i].val()));
577  } else {
578  xassigned = false;
579  }
580  }
581 
582  // sorted check bounds
583  // final check that variables are consitent with least and greatest possible
584  // values
585  int tlb = std::min(x[0].min(), y[0].min());
586  int tub = std::max(x[x.size() - 1].max(), y[y.size() - 1].max());
587  for (int i = x.size(); i--; ) {
588  ModEvent me = y[i].lq(home, tub);
589  GECODE_ME_CHECK(me);
590  nofix |= me_modified(me) && (y[i].max() != tub);
591 
592  me = y[i].gq(home, tlb);
593  GECODE_ME_CHECK(me);
594  nofix |= me_modified(me) && (y[i].min() != tlb);
595 
596  me = x[i].lq(home, tub);
597  GECODE_ME_CHECK(me);
598  nofix |= me_modified(me) && (x[i].max() != tub);
599 
600  me = x[i].gq(home, tlb);
601  GECODE_ME_CHECK(me);
602  nofix |= me_modified(me) && (x[i].min() != tlb);
603  }
604 
605  if (!array_assigned<View,Perm>
606  (home, x, y, z, array_subs, match_fixed, nofix, noperm_bc))
607  return ES_FAILED;
608 
609  if (array_subs)
610  return home.ES_SUBSUMED(*this);
611 
612  if (!check_subsumption<View,Perm>(x,y,z,subsumed,dropfst))
613  return ES_FAILED;
614 
615  if (subsumed)
616  return home.ES_SUBSUMED(*this);
617 
618  return nofix ? ES_NOFIX : ES_FIX;
619  }
620 
621  template<class View, bool Perm>
622  ExecStatus
624  post(Home home,
626  int n = x0.size();
627  if (n < 2) {
628  if ((x0[0].max() < y0[0].min()) || (y0[0].max() < x0[0].min()))
629  return ES_FAILED;
630  GECODE_ES_CHECK((Rel::EqBnd<View,View>::post(home,x0[0],y0[0])));
631  if (Perm) {
632  GECODE_ME_CHECK(z0[0].eq(home,0));
633  }
634  } else {
635  if (Perm) {
636  ViewArray<View> z(home,n);
637  for (int i=n; i--; ) {
638  z[i]=z0[i];
639  GECODE_ME_CHECK(z[i].gq(home,0));
640  GECODE_ME_CHECK(z[i].lq(home,n-1));
641  }
643  }
644  new (home) Sorted<View,Perm>(home,x0,y0,z0);
645  }
646  return ES_OK;
647  }
648 
649 }}}
650 
651 // STATISTICS: int-prop
652 
653 
654 
bool glover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phi[], OfflineMinItem sequence[], int vertices[])
Glover'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:109
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
void post(Home home, Term *t, int n, FloatRelType frt, FloatVal c)
Post propagator for linear constraint over floats.
Definition: post.cpp:228
static PropCost linear(PropCost::Mod m, unsigned int n)
Linear complexity for modifier pcm and size measure n.
Definition: core.hpp:4041
const FloatNum max
Largest allowed float value.
Definition: float.hh:831
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
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
Item used to construct the OfflineMin sequence.
Definition: sortsup.hpp:121
int ModEvent
Type for modification events.
Definition: core.hpp:146
Base-class for propagators.
Definition: core.hpp:755
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:61
Propagation has computed fixpoint.
Definition: core.hpp:528
Computation spaces.
Definition: core.hpp:1362
bool normalize(Space &home, ViewArray< View > &y, ViewArray< View > &x, bool &nofix)
Performing normalization on the views in y.
Definition: order.hpp:97
Base-class for both propagators and branchers.
Definition: core.hpp:666
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
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntConLevel)
Post propagator for .
Definition: sequence.cpp:51
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:84
void computesccs(Space &home, ViewArray< View > &x, ViewArray< View > &y, int phi[], SccComponent sinfo[], int scclist[])
Compute the sccs of the oriented intersection-graph.
Definition: narrowing.hpp:58
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:833
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:525
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
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:107
Offset integer view.
Definition: view.hpp:422
View arrays.
Definition: array.hpp:234
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:45
Representation of a strongly connected component.
Definition: sortsup.hpp:57
ViewArray< View > y
Views denoting the sorted version of x.
Definition: sorted.hh:68
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
ExecStatus subsumed(Space &home, Propagator &p, TaskArray< Task > &t)
Check tasks t for subsumption.
Definition: subsumption.hpp:42
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
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
int max
stores the mininmum of a variable
Definition: sortsup.hpp:48
#define forceinline
Definition: config.hpp:132
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
Execution is okay.
Definition: core.hpp:527
Propagation has not computed fixpoint.
Definition: core.hpp:526
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Bounds consistent distinct propagator.
Definition: distinct.hh:129
Gecode toplevel namespace
int ModEventDelta
Modification event deltas.
Definition: core.hpp:173
Home class for posting propagators
Definition: core.hpp:717
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58