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 * 00006 * Copyright: 00007 * Christian Schulte, 2009 00008 * 00009 * Last modified: 00010 * $Date: 2010-06-03 13:11:11 +0200 (Thu, 03 Jun 2010) $ by $Author: tack $ 00011 * $Revision: 11013 $ 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 #include <algorithm> 00039 00040 namespace Gecode { namespace Scheduling { namespace Cumulative { 00041 00043 template<class TaskView, bool inc> 00044 class StoCap { 00045 public: 00047 bool operator ()(const TaskView& t1, const TaskView& t2) const { 00048 return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c()); 00049 } 00050 }; 00051 00053 class PrecOrder { 00054 public: 00055 int* prec; 00057 PrecOrder(int* prec0) : prec(prec0) {} 00059 bool operator ()(int i, int j) const { 00060 return prec[i] > prec[j]; 00061 } 00062 }; 00063 00064 template<class TaskView> 00065 forceinline ExecStatus 00066 edgefinding(Space& home, int c, TaskViewArray<TaskView>& t) { 00067 sort<TaskView,STO_LCT,false>(t); 00068 00069 Region r(home); 00070 00072 // Detection 00073 00074 int* prec = r.alloc<int>(t.size()); 00075 for (int i=t.size(); i--; ) 00076 prec[i] = t[i].ect(); 00077 00078 OmegaLambdaTree<TaskView> ol(r,c,t); 00079 00080 for (int j=0; j<t.size(); j++) { 00081 while (!ol.lempty() && 00082 (ol.lenv() > static_cast<double>(c)*t[j].lct())) { 00083 int i = ol.responsible(); 00084 prec[i] = std::max(prec[i], t[j].lct()); 00085 ol.lremove(i); 00086 } 00087 ol.shift(j); 00088 } 00089 00091 // Propagation 00092 00093 // Compute array of unique capacities and a mapping 00094 // from the task array to the corresponding entry in 00095 // the capacity array 00096 00097 int* cap = r.alloc<int>(t.size()); 00098 for (int i=t.size(); i--;) 00099 cap[i] = i; 00100 SortMap<TaskView,StoCap,true> o(t); 00101 Support::quicksort(cap, t.size(), o); 00102 00103 int* capacities = r.alloc<int>(t.size()); 00104 int* capInv = r.alloc<int>(t.size()); 00105 for (int i=t.size(); i--;) { 00106 capacities[cap[i]] = t[i].c(); 00107 capInv[cap[i]] = i; 00108 } 00109 00110 int n_c = 0; 00111 for (int i=0, cur_c=INT_MIN; i<t.size(); i++) { 00112 if (capacities[i] != cur_c) 00113 capacities[n_c++] = cur_c = capacities[i]; 00114 cap[capInv[i]] = n_c-1; 00115 } 00116 r.free<int>(capInv, t.size()); 00117 00118 // Compute update values for each capacity and LCut 00119 00120 int* update = r.alloc<int>(t.size()*n_c); 00121 for (int i=t.size()*n_c; i--;) 00122 update[i] = -Int::Limits::infinity; 00123 00124 ExtOmegaTree<TaskView> eo(r,c,ol); 00125 for (int i=0; i<n_c; i++) { 00126 eo.init(capacities[i]); 00127 int u = -Int::Limits::infinity; 00128 for (int j=t.size(); j--;) { 00129 double lctj = static_cast<double>(c-capacities[i])*t[j].lct(); 00130 double diff_d = ceil(div(plus(eo.env(j), -lctj),capacities[i])); 00131 int diff = (diff_d == -Int::Limits::double_infinity) ? 00132 -Int::Limits::infinity : static_cast<int>(diff_d); 00133 u = std::max(u,diff); 00134 update[i*t.size()+j] = u; 00135 } 00136 } 00137 00138 // Update est by iterating in parallel over the prec array 00139 // and the task array, both sorted by lct 00140 00141 int* precMap = r.alloc<int>(t.size()); 00142 for (int i=t.size(); i--;) 00143 precMap[i] = i; 00144 PrecOrder po(prec); 00145 Support::quicksort(precMap, t.size(), po); 00146 00147 int curJ = 0; 00148 for (int i=0; i<t.size(); i++) { 00149 while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]]) 00150 curJ++; 00151 while (curJ < t.size() && t[curJ].lct() == prec[precMap[i]]) { 00152 if (t[curJ].lct() != t[precMap[i]].lct()) { 00153 GECODE_ME_CHECK( 00154 t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+curJ])); 00155 } 00156 curJ++; 00157 } 00158 } 00159 00160 return ES_OK; 00161 } 00162 00163 template<class Task> 00164 ExecStatus 00165 edgefinding(Space& home, int c, TaskArray<Task>& t) { 00166 TaskViewArray<typename TaskTraits<Task>::TaskViewFwd> f(t); 00167 GECODE_ES_CHECK(edgefinding(home,c,f)); 00168 TaskViewArray<typename TaskTraits<Task>::TaskViewBwd> b(t); 00169 GECODE_ES_CHECK(edgefinding(home,c,b)); 00170 return ES_OK; 00171 } 00172 00173 }}} 00174 00175 // STATISTICS: scheduling-prop