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