narrowing.hpp
Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */ 00002 /* 00003 * Main authors: 00004 * Patrick Pekczynski <pekczynski@ps.uni-sb.de> 00005 * 00006 * Copyright: 00007 * Patrick Pekczynski, 2004 00008 * 00009 * Last modified: 00010 * $Date: 2009-01-20 23:44:27 +0100 (Tue, 20 Jan 2009) $ by $Author: schulte $ 00011 * $Revision: 8082 $ 00012 * 00013 * This file is part of Gecode, the generic constraint 00014 * development environment: 00015 * http://www.gecode.org 00016 * 00017 * Permission is hereby granted, free of charge, to any person obtaining 00018 * a copy of this software and associated documentation files (the 00019 * "Software"), to deal in the Software without restriction, including 00020 * without limitation the rights to use, copy, modify, merge, publish, 00021 * distribute, sublicense, and/or sell copies of the Software, and to 00022 * permit persons to whom the Software is furnished to do so, subject to 00023 * the following conditions: 00024 * 00025 * The above copyright notice and this permission notice shall be 00026 * included in all copies or substantial portions of the Software. 00027 * 00028 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 00029 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 00030 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND 00031 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE 00032 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION 00033 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION 00034 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 00035 * 00036 */ 00037 00038 namespace Gecode { namespace Int { namespace Sorted { 00039 00056 template<class View> 00057 inline void 00058 computesccs(Space& home, ViewArray<View>& x, ViewArray<View>& y, 00059 int phi[], SccComponent sinfo[], int scclist[]) { 00060 00061 // number of sccs is bounded by xs (number of x-nodes) 00062 int xs = x.size(); 00063 Region r(home); 00064 Support::StaticStack<int,Region> cs(r,xs); 00065 00066 //select an y node from the graph 00067 for (int j = 0; j < xs; j++) { 00068 int yjmin = y[j].min(); // the processed min 00069 while (!cs.empty() && x[phi[sinfo[cs.top()].rightmost]].max() < yjmin) { 00070 // the topmost scc cannot "reach" y_j or a node to the right of it 00071 cs.pop(); 00072 } 00073 00074 // a component has the form C(y-Node, matching x-Node) 00075 // C is a minimal scc in the oriented intersection graph 00076 // we only store y_j-Node, since \phi(j) gives the matching X-node 00077 int i = phi[j]; 00078 int ximin = x[i].min(); 00079 while (!cs.empty() && ximin <= y[sinfo[cs.top()].rightmost].max()) { 00080 // y_j can "reach" cs.top() , 00081 // i.e. component c can reach component cs.top() 00082 // merge c and cs.top() into new component 00083 int top = cs.top(); 00084 // connecting 00085 sinfo[sinfo[j].leftmost].left = top; 00086 sinfo[top].right = sinfo[j].leftmost; 00087 // moving leftmost 00088 sinfo[j].leftmost = sinfo[top].leftmost; 00089 // moving rightmost 00090 sinfo[sinfo[top].leftmost].rightmost = j; 00091 cs.pop(); 00092 } 00093 cs.push(j); 00094 } 00095 cs.reset(); 00096 00097 00098 // now we mark all components with the respective scc-number 00099 // labeling is bound by O(k) which is bound by O(n) 00100 00101 for (int i = 0; i < xs; i++) { 00102 if (sinfo[i].left == i) { // only label variables in sccs 00103 int scc = sinfo[i].rightmost; 00104 int z = i; 00105 //bound by the size of the largest scc = k 00106 while (sinfo[z].right != z) { 00107 sinfo[z].rightmost = scc; 00108 scclist[phi[z]] = scc; 00109 z = sinfo[z].right; 00110 } 00111 sinfo[z].rightmost = scc; 00112 scclist[phi[z]] = scc; 00113 } 00114 } 00115 } 00116 00132 template<class View, bool Perm> 00133 inline bool 00134 narrow_domx(Space& home, 00135 ViewArray<View>& x, 00136 ViewArray<View>& y, 00137 ViewArray<View>& z, 00138 int tau[], 00139 int[], 00140 int scclist[], 00141 SccComponent sinfo[], 00142 bool& nofix) { 00143 00144 int xs = x.size(); 00145 00146 // For every x node 00147 for (int i = 0; i < xs; i++) { 00148 00149 int xmin = x[i].min(); 00150 /* 00151 * take the scc-list for the current x node 00152 * start from the leftmost reachable y node of the scc 00153 * and check which Y node in the scc is 00154 * really the rightmost node intersecting x, i.e. 00155 * search for the greatest lower bound of x 00156 */ 00157 int start = sinfo[scclist[i]].leftmost; 00158 while (y[start].max() < xmin) { 00159 start = sinfo[start].right; 00160 } 00161 00162 if (Perm) { 00163 // start is the leftmost-position for x_i 00164 // that denotes the lower bound on p_i 00165 00166 ModEvent me_plb = z[i].gq(home, start); 00167 if (me_failed(me_plb)) { 00168 return false; 00169 } 00170 nofix |= (me_modified(me_plb) && start != z[i].min()); 00171 } 00172 00173 ModEvent me_lb = x[i].gq(home, y[start].min()); 00174 if (me_failed(me_lb)) { 00175 return false; 00176 } 00177 nofix |= (me_modified(me_lb) && 00178 y[start].min() != x[i].min()); 00179 00180 int ptau = tau[xs - 1 - i]; 00181 int xmax = x[ptau].max(); 00182 /* 00183 * take the scc-list for the current x node 00184 * start from the rightmost reachable node and check which 00185 * y node in the scc is 00186 * really the rightmost node intersecting x, i.e. 00187 * search for the smallest upper bound of x 00188 */ 00189 start = sinfo[scclist[ptau]].rightmost; 00190 while (y[start].min() > xmax) { 00191 start = sinfo[start].left; 00192 } 00193 00194 if (Perm) { 00195 //start is the rightmost-position for x_i 00196 //that denotes the upper bound on p_i 00197 ModEvent me_pub = z[ptau].lq(home, start); 00198 if (me_failed(me_pub)) { 00199 return false; 00200 } 00201 nofix |= (me_modified(me_pub) && start != z[ptau].max()); 00202 } 00203 00204 ModEvent me_ub = x[ptau].lq(home, y[start].max()); 00205 if (me_failed(me_ub)) { 00206 return false; 00207 } 00208 nofix |= (me_modified(me_ub) && 00209 y[start].max() != x[ptau].max()); 00210 } 00211 return true; 00212 } 00213 00224 template<class View> 00225 inline bool 00226 narrow_domy(Space& home, 00227 ViewArray<View>& x, ViewArray<View>& y, 00228 int phi[], int phiprime[], bool& nofix) { 00229 for (int i=x.size(); i--; ) { 00230 ModEvent me_lb = y[i].gq(home, x[phiprime[i]].min()); 00231 if (me_failed(me_lb)) { 00232 return false; 00233 } 00234 nofix |= (me_modified(me_lb) && 00235 x[phiprime[i]].min() != y[i].min()); 00236 00237 ModEvent me_ub = y[i].lq(home, x[phi[i]].max()); 00238 if (me_failed(me_ub)) { 00239 return false; 00240 } 00241 nofix |= (me_modified(me_ub) && 00242 x[phi[i]].max() != y[i].max()); 00243 } 00244 return true; 00245 } 00246 00247 }}} 00248 00249 // STATISTICS: int-prop 00250