Generated on Mon May 5 05:53:58 2008 for Gecode by doxygen 1.5.5

narrowing.icc

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: 2007-11-08 15:53:26 +0100 (Thu, 08 Nov 2007) $ by $Author: tack $
00011  *     $Revision: 5219 $
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, class Tuple>
00057   inline void
00058   computesccs(Space*,
00059               ViewArray<Tuple>& xz,
00060               ViewArray<View>& y,
00061               int phi[],
00062               SccComponent sinfo[],
00063               int scclist[]) {
00064 
00065     // number of sccs is bounded by xs (number of x-nodes)
00066     int xs = xz.size();
00067     Support::StaticStack<int> cs(xs);
00068 
00069     //select an y node from the graph
00070     for (int j = 0; j < xs; j++) {
00071       int yjmin      = y[j].min();    // the processed min
00072       while (!cs.empty() && xz[phi[sinfo[cs.top()].rightmost]][0].max() < yjmin) {
00073         // the topmost scc cannot "reach" y_j or a node to the right of it
00074         cs.pop();
00075       }
00076 
00077       // a component has the form C(y-Node, matching x-Node)
00078       // C is a minimal scc in the oriented intersection graph
00079       // we only store y_j-Node, since \phi(j) gives the matching X-node
00080       int i     = phi[j];
00081       int ximin = xz[i][0].min();
00082       while (!cs.empty() && ximin <= y[sinfo[cs.top()].rightmost].max()) {
00083         // y_j can "reach" cs.top() ,
00084         // i.e. component c can reach component cs.top()
00085         // merge c and cs.top() into new component
00086         int top = cs.top();
00087         // connecting
00088         sinfo[sinfo[j].leftmost].left        = top;
00089         sinfo[top].right                     = sinfo[j].leftmost;
00090         // moving leftmost
00091         sinfo[j].leftmost                    = sinfo[top].leftmost;
00092         // moving rightmost
00093         sinfo[sinfo[top].leftmost].rightmost = j;
00094         cs.pop();
00095       }
00096       cs.push(j);
00097     }
00098     cs.reset();
00099 
00100 
00101     // now we mark all components with the respective scc-number
00102     // labeling is bound by O(k) which is bound by O(n)
00103 
00104     for (int i = 0; i < xs; i++) {
00105       if (sinfo[i].left == i) { // only label variables in sccs
00106         int scc = sinfo[i].rightmost;
00107         int z   = i;
00108         //bound by the size of the largest scc = k
00109         while (sinfo[z].right != z) {
00110           sinfo[z].rightmost   = scc;
00111           scclist[phi[z]]      = scc;
00112           z                    = sinfo[z].right;
00113         }
00114         sinfo[z].rightmost     = scc;
00115         scclist[phi[z]]        = scc;
00116       }
00117     }
00118   }
00119 
00135   template<class View, class Tuple, bool Perm>
00136   inline bool
00137   narrow_domx(Space* home,
00138               ViewArray<Tuple>& xz,
00139               ViewArray<View>& y,
00140               int tau[],
00141               int[],
00142               int scclist[],
00143               SccComponent sinfo[],
00144               bool& nofix) {
00145 
00146     int xs        = xz.size();
00147 
00148     // For every x node
00149     for (int i = 0; i < xs; i++) {
00150 
00151       int xmin = xz[i][0].min();
00152       /*
00153        * take the scc-list for the current x node
00154        * start from the leftmost reachable y node of the scc
00155        * and check which Y node in the scc is
00156        * really the rightmost node intersecting x, i.e.
00157        * search for the greatest lower bound of x
00158        */
00159       int start = sinfo[scclist[i]].leftmost;
00160       while (y[start].max() < xmin) {
00161         start = sinfo[start].right;
00162       }
00163         
00164       if (Perm) {
00165         // start is the leftmost-position for x_i
00166         // that denotes the lower bound on p_i
00167 
00168         ModEvent me_plb = xz[i][1].gq(home, start);
00169         if (me_failed(me_plb)) {
00170           return false;
00171         }
00172         nofix |= (me_modified(me_plb) && start != xz[i][1].min());
00173       }
00174 
00175       ModEvent me_lb = xz[i][0].gq(home, y[start].min());
00176       if (me_failed(me_lb)) {
00177         return false;
00178       }
00179       nofix |= (me_modified(me_lb) &&
00180                 y[start].min() != xz[i][0].min());
00181         
00182       int ptau = tau[xs - 1 - i];
00183       int xmax = xz[ptau][0].max();
00184       /*
00185        * take the scc-list for the current x node
00186        * start from the rightmost reachable node and check which
00187        * y node in the scc is
00188        * really the rightmost node intersecting x, i.e.
00189        * search for the smallest upper bound of x
00190        */
00191       start = sinfo[scclist[ptau]].rightmost;
00192       while (y[start].min() > xmax) {
00193         start = sinfo[start].left;
00194       }
00195 
00196       if (Perm) {
00197         //start is the rightmost-position for x_i
00198         //that denotes the upper bound on p_i
00199         ModEvent me_pub = xz[ptau][1].lq(home, start);
00200         if (me_failed(me_pub)) {
00201           return false;
00202         }
00203         nofix |= (me_modified(me_pub) && start != xz[ptau][1].max());
00204       }
00205 
00206       ModEvent me_ub = xz[ptau][0].lq(home, y[start].max());
00207       if (me_failed(me_ub)) {
00208         return false;
00209       }
00210       nofix |= (me_modified(me_ub) &&
00211                 y[start].max() != xz[ptau][0].max());
00212     }
00213     return true;
00214   }
00215 
00226   template<class View, class Tuple, bool Perm>
00227   inline bool
00228   narrow_domy(Space* home,
00229               ViewArray<Tuple>& xz,
00230               ViewArray<View>& y,
00231               int phi[],
00232               int phiprime[],
00233               bool& nofix) {
00234 
00235     int xs = xz.size();
00236     for (int i = xs; i--; ) {
00237       ModEvent me_lb = y[i].gq(home, xz[phiprime[i]][0].min());
00238       if (me_failed(me_lb)) {
00239         return false;
00240       }
00241       nofix |= (me_modified(me_lb) &&
00242                 xz[phiprime[i]][0].min() != y[i].min());
00243 
00244       ModEvent me_ub = y[i].lq(home, xz[phi[i]][0].max());
00245       if (me_failed(me_ub)) {
00246         return false;
00247       }
00248       nofix |= (me_modified(me_ub) &&
00249                 xz[phi[i]][0].max() != y[i].max());
00250     }
00251     return true;
00252   }
00253 
00254 }}}
00255 
00256 // STATISTICS: int-prop
00257