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

edge-finding.hpp

Go to the documentation of this file.
00001 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
00002 /*
00003  *  Main authors:
00004  *     Christian Schulte <schulte@gecode.org>
00005  *     Guido Tack <tack@gecode.org>
00006  *
00007  *  Contributing authors:
00008  *     Joseph Scott <joseph.scott@it.uu.se>
00009  *
00010  *  Copyright:
00011  *     Christian Schulte, 2009
00012  *     Guido Tack, 2010
00013  *     Joseph Scott, 2011
00014  *
00015  *  This file is part of Gecode, the generic constraint
00016  *  development environment:
00017  *     http://www.gecode.org
00018  *
00019  *  Permission is hereby granted, free of charge, to any person obtaining
00020  *  a copy of this software and associated documentation files (the
00021  *  "Software"), to deal in the Software without restriction, including
00022  *  without limitation the rights to use, copy, modify, merge, publish,
00023  *  distribute, sublicense, and/or sell copies of the Software, and to
00024  *  permit persons to whom the Software is furnished to do so, subject to
00025  *  the following conditions:
00026  *
00027  *  The above copyright notice and this permission notice shall be
00028  *  included in all copies or substantial portions of the Software.
00029  *
00030  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
00031  *  EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
00032  *  MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
00033  *  NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
00034  *  LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
00035  *  OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
00036  *  WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
00037  *
00038  */
00039 
00040 #include <algorithm>
00041 
00042 namespace Gecode { namespace Int { namespace Cumulative {
00043 
00045   template<class TaskView, bool inc>
00046   class StoCap {
00047   public:
00049     bool operator ()(const TaskView& t1, const TaskView& t2) const {
00050       return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c());
00051     }
00052   };
00053 
00055   class PrecOrder {
00056   public:
00057     int* prec;
00059     PrecOrder(int* prec0) : prec(prec0) {}
00061     bool operator ()(int i, int j) const {
00062       return prec[i] > prec[j];
00063     }
00064   };
00065 
00066   template<class TaskView>
00067   forceinline ExecStatus
00068   edgefinding(Space& home, int c, TaskViewArray<TaskView>& t) {
00069     sort<TaskView,STO_LCT,false>(t);
00070 
00071     Region r;
00072 
00074     // Detection
00075 
00076     int* prec = r.alloc<int>(t.size());
00077     for (int i=0; i<t.size(); i++)
00078       prec[i] = t[i].ect();
00079 
00080     OmegaLambdaTree<TaskView> ol(r,c,t);
00081 
00082     for (int j=0; j<t.size(); j++) {
00083       while (!ol.lempty() &&
00084              (ol.lenv() > static_cast<long long int>(c)*t[j].lct())) {
00085         int i = ol.responsible();
00086         prec[i] = std::max(prec[i], t[j].lct());
00087         ol.lremove(i);
00088       }
00089       ol.shift(j);
00090     }
00091 
00093     // Propagation
00094 
00095     // Compute array of unique capacities and a mapping
00096     // from the task array to the corresponding entry in
00097     // the capacity array
00098 
00099     int* cap = r.alloc<int>(t.size());
00100     for (int i=0; i<t.size(); i++)
00101       cap[i] = i;
00102     SortMap<TaskView,StoCap,true> o(t);
00103     Support::quicksort(cap, t.size(), o);
00104 
00105     int* capacities = r.alloc<int>(t.size());
00106     int* capInv = r.alloc<int>(t.size());
00107     for (int i=t.size(); i--;) {
00108       capacities[cap[i]] = t[i].c();
00109       capInv[cap[i]] = i;
00110     }
00111 
00112     int n_c = 0;
00113     for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
00114       if (capacities[i] != cur_c)
00115         capacities[n_c++] = cur_c = capacities[i];
00116       cap[capInv[i]] = n_c-1;
00117     }
00118     r.free<int>(capInv, t.size());
00119 
00120     // Compute update values for each capacity and LCut
00121 
00122     int* update = r.alloc<int>(t.size()*n_c);
00123     for (int i=0; i<t.size()*n_c; i++)
00124       update[i] = -Limits::infinity;
00125 
00126     ExtOmegaTree<TaskView> eo(r,c,ol);
00127     for (int i=0; i<n_c; i++) {
00128       eo.init(capacities[i]);
00129       int u = -Limits::infinity;
00130       for (int j=t.size(); j--;) {
00131         long long int lctj =
00132           static_cast<long long int>(c-capacities[i])*t[j].lct();
00133         long long int eml = plus(eo.env(j), -lctj);
00134         long long int diff_l;
00135         if (eml == -Limits::llinfinity)
00136           diff_l = -Limits::llinfinity;
00137         else
00138           diff_l = ceil_div_xx(eml,
00139                                static_cast<long long int>(capacities[i]));
00140         int diff = (diff_l <= -Limits::infinity) ?
00141           -Limits::infinity : static_cast<int>(diff_l);
00142         u = std::max(u,diff);
00143         update[i*t.size()+j] = u;
00144       }
00145     }
00146 
00147     // Update est by iterating in parallel over the prec array
00148     // and the task array, both sorted by lct
00149 
00150     int* precMap = r.alloc<int>(t.size());
00151     for (int i=0; i<t.size(); i++)
00152       precMap[i] = i;
00153     PrecOrder po(prec);
00154     Support::quicksort(precMap, t.size(), po);
00155 
00156     int curJ = 0;
00157     for (int i=0; i<t.size(); i++) {
00158       // discard any curJ with lct > prec[i]:
00159       while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
00160         curJ++;
00161       if (curJ >= t.size())
00162         break;
00163       // if lct[curJ] == prec[i], then LCut(T,j) <= i, so update est[i]
00164       int locJ = curJ;
00165       do {
00166         if (t[locJ].lct() != t[precMap[i]].lct()) {
00167           GECODE_ME_CHECK(t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+locJ]));
00168           break;
00169         }
00170       } while (t[locJ].lct() == prec[precMap[i]] && locJ++ < t.size() - 1);
00171     }
00172 
00173     return ES_OK;
00174   }
00175 
00176   template<class Task>
00177   ExecStatus
00178   edgefinding(Space& home, int c, TaskArray<Task>& t) {
00179     TaskViewArray<typename TaskTraits<Task>::TaskViewFwd> f(t);
00180     GECODE_ES_CHECK(edgefinding(home,c,f));
00181     TaskViewArray<typename TaskTraits<Task>::TaskViewBwd> b(t);
00182     GECODE_ES_CHECK(edgefinding(home,c,b));
00183     return ES_OK;
00184   }
00185 
00186 }}}
00187 
00188 // STATISTICS: int-prop