Generated on Fri Oct 19 11:25:09 2018 for Gecode by doxygen 1.6.3

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