Generated on Sat Feb 7 2015 02:01:25 for Gecode by doxygen 1.8.9.1
narrowing.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: 2012-09-07 17:31:22 +0200 (Fri, 07 Sep 2012) $ by $Author: schulte $
11  * $Revision: 13068 $
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 namespace Gecode { namespace Int { namespace Sorted {
39 
56  template<class View>
57  inline void
59  int phi[], SccComponent sinfo[], int scclist[]) {
60 
61  // number of sccs is bounded by xs (number of x-nodes)
62  int xs = x.size();
63  Region r(home);
65 
66  //select an y node from the graph
67  for (int j = 0; j < xs; j++) {
68  int yjmin = y[j].min(); // the processed min
69  while (!cs.empty() && x[phi[sinfo[cs.top()].rightmost]].max() < yjmin) {
70  // the topmost scc cannot "reach" y_j or a node to the right of it
71  cs.pop();
72  }
73 
74  // a component has the form C(y-Node, matching x-Node)
75  // C is a minimal scc in the oriented intersection graph
76  // we only store y_j-Node, since \phi(j) gives the matching X-node
77  int i = phi[j];
78  int ximin = x[i].min();
79  while (!cs.empty() && ximin <= y[sinfo[cs.top()].rightmost].max()) {
80  // y_j can "reach" cs.top() ,
81  // i.e. component c can reach component cs.top()
82  // merge c and cs.top() into new component
83  int top = cs.top();
84  // connecting
85  sinfo[sinfo[j].leftmost].left = top;
86  sinfo[top].right = sinfo[j].leftmost;
87  // moving leftmost
88  sinfo[j].leftmost = sinfo[top].leftmost;
89  // moving rightmost
90  sinfo[sinfo[top].leftmost].rightmost = j;
91  cs.pop();
92  }
93  cs.push(j);
94  }
95  cs.reset();
96 
97 
98  // now we mark all components with the respective scc-number
99  // labeling is bound by O(k) which is bound by O(n)
100 
101  for (int i = 0; i < xs; i++) {
102  if (sinfo[i].left == i) { // only label variables in sccs
103  int scc = sinfo[i].rightmost;
104  int z = i;
105  //bound by the size of the largest scc = k
106  while (sinfo[z].right != z) {
107  sinfo[z].rightmost = scc;
108  scclist[phi[z]] = scc;
109  z = sinfo[z].right;
110  }
111  sinfo[z].rightmost = scc;
112  scclist[phi[z]] = scc;
113  }
114  }
115  }
116 
132  template<class View, bool Perm>
133  inline bool
136  ViewArray<View>& y,
137  ViewArray<View>& z,
138  int tau[],
139  int[],
140  int scclist[],
141  SccComponent sinfo[],
142  bool& nofix) {
143 
144  int xs = x.size();
145 
146  // For every x node
147  for (int i = 0; i < xs; i++) {
148 
149  int xmin = x[i].min();
150  /*
151  * take the scc-list for the current x node
152  * start from the leftmost reachable y node of the scc
153  * and check which Y node in the scc is
154  * really the rightmost node intersecting x, i.e.
155  * search for the greatest lower bound of x
156  */
157  int start = sinfo[scclist[i]].leftmost;
158  while (y[start].max() < xmin) {
159  start = sinfo[start].right;
160  }
161 
162  if (Perm) {
163  // start is the leftmost-position for x_i
164  // that denotes the lower bound on p_i
165 
166  ModEvent me_plb = z[i].gq(home, start);
167  if (me_failed(me_plb)) {
168  return false;
169  }
170  nofix |= (me_modified(me_plb) && start != z[i].min());
171  }
172 
173  ModEvent me_lb = x[i].gq(home, y[start].min());
174  if (me_failed(me_lb)) {
175  return false;
176  }
177  nofix |= (me_modified(me_lb) &&
178  y[start].min() != x[i].min());
179 
180  int ptau = tau[xs - 1 - i];
181  int xmax = x[ptau].max();
182  /*
183  * take the scc-list for the current x node
184  * start from the rightmost reachable node and check which
185  * y node in the scc is
186  * really the rightmost node intersecting x, i.e.
187  * search for the smallest upper bound of x
188  */
189  start = sinfo[scclist[ptau]].rightmost;
190  while (y[start].min() > xmax) {
191  start = sinfo[start].left;
192  }
193 
194  if (Perm) {
195  //start is the rightmost-position for x_i
196  //that denotes the upper bound on p_i
197  ModEvent me_pub = z[ptau].lq(home, start);
198  if (me_failed(me_pub)) {
199  return false;
200  }
201  nofix |= (me_modified(me_pub) && start != z[ptau].max());
202  }
203 
204  ModEvent me_ub = x[ptau].lq(home, y[start].max());
205  if (me_failed(me_ub)) {
206  return false;
207  }
208  nofix |= (me_modified(me_ub) &&
209  y[start].max() != x[ptau].max());
210  }
211  return true;
212  }
213 
224  template<class View>
225  inline bool
228  int phi[], int phiprime[], bool& nofix) {
229  for (int i=x.size(); i--; ) {
230  ModEvent me_lb = y[i].gq(home, x[phiprime[i]].min());
231  if (me_failed(me_lb)) {
232  return false;
233  }
234  nofix |= (me_modified(me_lb) &&
235  x[phiprime[i]].min() != y[i].min());
236 
237  ModEvent me_ub = y[i].lq(home, x[phi[i]].max());
238  if (me_failed(me_ub)) {
239  return false;
240  }
241  nofix |= (me_modified(me_ub) &&
242  x[phi[i]].max() != y[i].max());
243  }
244  return true;
245  }
246 
247 }}}
248 
249 // STATISTICS: int-prop
250 
void push(const T &x)
Push element x on top of stack.
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
T & top(void) const
Return element on top of stack.
bool narrow_domx(Space &home, ViewArray< View > &x, ViewArray< View > &y, ViewArray< View > &z, int tau[], int[], int scclist[], SccComponent sinfo[], bool &nofix)
Narrowing the domains of the x variables.
Definition: narrowing.hpp:134
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
int ModEvent
Type for modification events.
Definition: core.hpp:146
Handle to region.
Definition: region.hpp:61
Computation spaces.
Definition: core.hpp:1362
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 empty(void) const
Test whether stack is empty.
Gecode::IntArgs i(4, 1, 2, 3, 4)
int left
Direct left neighbour of an y-node in a scc.
Definition: sortsup.hpp:62
NNF * r
Right subtree.
Definition: bool-expr.cpp:246
int rightmost
Rightmost reachable y-node in a scc.
Definition: sortsup.hpp:66
View arrays.
Definition: array.hpp:234
Representation of a strongly connected component.
Definition: sortsup.hpp:57
void reset(void)
Reset stack (pop all elements)
int right
Direct right neighbour of an y-node in a scc.
Definition: sortsup.hpp:64
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
int leftmost
Leftmost y-node in a scc.
Definition: sortsup.hpp:60
Stack with fixed number of elements.
bool me_modified(ModEvent me)
Check whether modification event me describes variable modification.
Definition: modevent.hpp:63
T pop(void)
Pop topmost element from stack and return it.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
bool me_failed(ModEvent me)
Check whether modification event me is failed.
Definition: modevent.hpp:58