Generated on Wed Jan 4 17:49:11 2006 for Gecode by doxygen 1.4.6

narrowing.icc

Go to the documentation of this file.
00001 /*
00002  *  Main authors:
00003  *     Patrick Pekczynski <pekczynski@ps.uni-sb.de>
00004  *
00005  *  Copyright:
00006  *     Patrick Pekczynski, 2004
00007  *
00008  *  Last modified:
00009  *     $Date: 2005-12-02 11:48:39 +0100 (Fri, 02 Dec 2005) $ by $Author: pekczynski $
00010  *     $Revision: 2686 $
00011  *
00012  *  This file is part of Gecode, the generic constraint
00013  *  development environment:
00014  *     http://www.gecode.org
00015  *
00016  *  See the file "LICENSE" for information on usage and
00017  *  redistribution of this file, and for a
00018  *     DISCLAIMER OF ALL WARRANTIES.
00019  *
00020  */     
00021 
00022 #include "support/static-stack.hh"
00023 
00024 namespace Gecode { namespace Int { namespace Sortedness {
00025 
00032   class SccComponent {
00033   public:
00035     int leftmost;   
00037     int left;       
00039     int right;    
00041     int rightmost;  
00042   };
00043 
00044 
00045 
00062   template<class View, class Tuple>
00063   forceinline void 
00064   computesccs(Space* home, 
00065               ViewArray<Tuple>& xz,
00066               ViewArray<View>& y,
00067               int phi[], 
00068               SccComponent sinfo[], 
00069               int scclist[]) {
00070 
00071     // number of sccs is bounded by xs (number of x-nodes)
00072     int xs = xz.size(); 
00073     Support::StaticStack<int> cs(xs);
00074 
00075     //select an y node from the graph
00076     for (int j = 0; j < xs; j++) {
00077       
00078       int yjmin      = y[j].min();    // the processed min
00079       while (!cs.empty() && xz[phi[sinfo[cs.top()].rightmost]][0].max() < yjmin) {
00080         // the topmost scc cannot "reach" y_j or a node to the right of it
00081         cs.pop();
00082       }
00083 
00084       // a component has the form C(y-Node, matching x-Node)
00085       // C is a minimal scc in the oriented intersection graph
00086       // we only store y_j-Node, since \phi(j) gives the matching X-node
00087       int i     = phi[j];
00088       int ximin = xz[i][0].min();
00089       while (!cs.empty() && ximin <= y[sinfo[cs.top()].rightmost].max()) {
00090         // y_j can "reach" cs.top() ,
00091         // i.e. component c can reach component cs.top()
00092         // merge c and cs.top() into new component
00093         int top = cs.top();
00094         // connecting
00095         sinfo[sinfo[j].leftmost].left        = top;
00096         sinfo[top].right                     = sinfo[j].leftmost;
00097         // moving leftmost
00098         sinfo[j].leftmost                    = sinfo[top].leftmost;
00099         // moving rightmost
00100         sinfo[sinfo[top].leftmost].rightmost = j;
00101         cs.pop();
00102       }
00103       cs.push(j);
00104     }
00105     cs.reset();
00106 
00107     // now we mark all components with the respective scc-number
00108     // labeling is bound by O(k) which is bound by O(n) 
00109 
00110     for (int i = 0; i < xs; i++) {
00111       if (sinfo[i].left == i) { // only label variables in sccs
00112         int scc = sinfo[i].rightmost; 
00113         int z   = i;
00114         //bound by the size of the largest scc = k 
00115         while (sinfo[z].right != z) {
00116           sinfo[z].rightmost   = scc;
00117           scclist[phi[z]]      = scc;
00118           z                    = sinfo[z].right;
00119         }
00120         sinfo[z].rightmost     = scc;
00121         scclist[phi[z]]        = scc;
00122       }
00123     }
00124   }
00125 
00141   template<class View, class Tuple, bool Perm, bool shared>
00142   forceinline bool
00143   narrow_domx(Space* home, 
00144               ViewArray<Tuple>& xz, 
00145               ViewArray<View>& y,
00146               int tau[], 
00147               int phi[], 
00148               int scclist[], 
00149               SccComponent sinfo[], 
00150               bool& nofix) {
00151 
00152     int xs        = xz.size(); 
00153 
00154     // For every x node
00155     for (int i = 0; i < xs; i++) {
00156       
00157       int xmin = xz[i][0].min();
00158       /* 
00159        * take the scc-list for the current x node 
00160        * start from the leftmost reachable y node and check which 
00161        * Y node in the scc is the rightmost reachable node, i.e.
00162        * search for the greatest lower bound of x
00163        */
00164       int start = sinfo[scclist[i]].leftmost;
00165       while (y[start].max() < xmin) {
00166         start = sinfo[start].right;
00167       }
00168         
00169       sinfo[scclist[i]].leftmost = start; //remember iterator position
00170       if (Perm) {
00171         // start is the leftmost-position for x_i 
00172         // that denotes the lower bound on p_i
00173 
00174         ModEvent me_plb = xz[i][1].gq(home, start);
00175         if (me_failed(me_plb)) {
00176           return false;
00177         }
00178         nofix |= (me_modified(me_plb) && start != xz[i][1].min()); 
00179       }
00180 
00181       if (shared && xz[i][0].modified()) {
00182         nofix = true;
00183         return true;
00184       }
00185       ModEvent me_lb = xz[i][0].gq(home, y[start].min());
00186       if (me_failed(me_lb)) {
00187         return false;
00188       }
00189       nofix |= (me_modified(me_lb) && 
00190                 y[start].min() != xz[i][0].min());
00191         
00192       int ptau = tau[xs - 1 - i];
00193       int xmax = xz[ptau][0].max();
00194       /* 
00195        * take the scc-list for the current x node 
00196        * start from the rightmost reachable node and check which 
00197        * y node in the scc is the leftmost reachable node, i.e. 
00198        * search for the smallest upper bound of x
00199        */
00200       start = sinfo[scclist[ptau]].rightmost;
00201       while (y[start].min() > xmax) {
00202         start = sinfo[start].left;
00203       }
00204 
00205       sinfo[scclist[ptau]].rightmost = start; //remember iterator position
00206         
00207       if (Perm) {
00208         //start is the rightmost-position for x_i 
00209         //that denotes the upper bound on p_i
00210         ModEvent me_pub = xz[ptau][1].lq(home, start);
00211         if (me_failed(me_pub)) {
00212           return false;
00213         }
00214         nofix |= (me_modified(me_pub) && start != xz[ptau][1].max());
00215       }
00216 
00217       if (shared && xz[ptau][0].modified()) {
00218         nofix = true;
00219         return true;
00220       }
00221       
00222       ModEvent me_ub = xz[ptau][0].lq(home, y[start].max());
00223       if (me_failed(me_ub)) {
00224         return false;
00225       }
00226       nofix |= (me_modified(me_ub) && 
00227                 y[start].max() != xz[ptau][0].max());
00228     }
00229     return true;
00230   }
00231   
00242   template<class View, class Tuple, bool Perm, bool shared>
00243   forceinline bool
00244   narrow_domy(Space* home, 
00245               ViewArray<Tuple>& xz, 
00246               ViewArray<View>& y,
00247               int phi[], 
00248               int phiprime[], 
00249               bool& nofix) {
00250 
00251     int xs = xz.size();
00252     for (int i = xs; i--; ) {
00253       if (shared && y[i].modified()) {
00254         nofix = true;
00255         return true;
00256       }
00257       ModEvent me_lb = y[i].gq(home, xz[phiprime[i]][0].min()); 
00258       if (me_failed(me_lb)) {
00259         return false;
00260       }
00261       nofix |= (me_modified(me_lb) && 
00262                 xz[phiprime[i]][0].min() != y[i].min());
00263 
00264       if (shared && y[i].modified()) {
00265         nofix = true;
00266         return true;
00267       }
00268 
00269       ModEvent me_ub = y[i].lq(home, xz[phi[i]][0].max());
00270       if (me_failed(me_ub)) {
00271         return false;
00272       }
00273       nofix |= (me_modified(me_ub) &&
00274                 xz[phi[i]][0].max() != y[i].max());
00275     }
00276     return true;
00277   }
00278   
00279 }}}
00280 
00281 // STATISTICS: int-prop
00282