Generated on Sat Feb 12 2011 17:41:01 for Gecode by doxygen 1.7.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  *  Copyright:
00008  *     Christian Schulte, 2009
00009  *     Guido Tack, 2010
00010  *
00011  *  Last modified:
00012  *     $Date: 2011-01-18 23:37:08 +0100 (Tue, 18 Jan 2011) $ by $Author: tack $
00013  *     $Revision: 11551 $
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 Scheduling { 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(home);
00072 
00074     // Detection
00075 
00076     int* prec = r.alloc<int>(t.size());
00077     for (int 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<double>(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=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=t.size()*n_c; i--;)
00124       update[i] = -Int::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 = -Int::Limits::infinity;
00130       for (int j=t.size(); j--;) {
00131         double lctj = static_cast<double>(c-capacities[i])*t[j].lct();
00132         double diff_d = ceil(div(plus(eo.env(j), -lctj),capacities[i]));
00133         int diff = (diff_d == -Int::Limits::double_infinity) ? 
00134           -Int::Limits::infinity : static_cast<int>(diff_d);
00135         u = std::max(u,diff);
00136         update[i*t.size()+j] = u;
00137       }
00138     }
00139 
00140     // Update est by iterating in parallel over the prec array
00141     // and the task array, both sorted by lct
00142 
00143     int* precMap = r.alloc<int>(t.size());
00144     for (int i=t.size(); i--;)
00145       precMap[i] = i;
00146     PrecOrder po(prec);
00147     Support::quicksort(precMap, t.size(), po);
00148     
00149     int curJ = 0;
00150     for (int i=0; i<t.size(); i++) {
00151       while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
00152         curJ++;
00153       while (curJ < t.size() && t[curJ].lct() == prec[precMap[i]]) {
00154         if (t[curJ].lct() != t[precMap[i]].lct()) {
00155           GECODE_ME_CHECK(
00156             t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+curJ]));
00157         }
00158         curJ++;
00159       }
00160     }
00161 
00162     return ES_OK;
00163   }
00164 
00165   template<class Task>
00166   ExecStatus
00167   edgefinding(Space& home, int c, TaskArray<Task>& t) {
00168     TaskViewArray<typename TaskTraits<Task>::TaskViewFwd> f(t);
00169     GECODE_ES_CHECK(edgefinding(home,c,f));
00170     TaskViewArray<typename TaskTraits<Task>::TaskViewBwd> b(t);
00171     GECODE_ES_CHECK(edgefinding(home,c,b));
00172     return ES_OK;
00173   }
00174     
00175 }}}
00176 
00177 // STATISTICS: scheduling-prop