Generated on Thu Feb 21 2013 23:11:42 for Gecode by doxygen 1.8.3.1
edge-finding.hpp
Go to the documentation of this file.
1 /* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2 /*
3  * Main authors:
4  * Christian Schulte <schulte@gecode.org>
5  * Guido Tack <tack@gecode.org>
6  *
7  * Contributing authors:
8  * Joseph Scott <joseph.scott@it.uu.se>
9  *
10  * Copyright:
11  * Christian Schulte, 2009
12  * Guido Tack, 2010
13  * Joseph Scott, 2011
14  *
15  * Last modified:
16  * $Date: 2012-02-22 16:04:20 +1100 (Wed, 22 Feb 2012) $ by $Author: tack $
17  * $Revision: 12537 $
18  *
19  * This file is part of Gecode, the generic constraint
20  * development environment:
21  * http://www.gecode.org
22  *
23  * Permission is hereby granted, free of charge, to any person obtaining
24  * a copy of this software and associated documentation files (the
25  * "Software"), to deal in the Software without restriction, including
26  * without limitation the rights to use, copy, modify, merge, publish,
27  * distribute, sublicense, and/or sell copies of the Software, and to
28  * permit persons to whom the Software is furnished to do so, subject to
29  * the following conditions:
30  *
31  * The above copyright notice and this permission notice shall be
32  * included in all copies or substantial portions of the Software.
33  *
34  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
35  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
36  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
37  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
38  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
39  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
40  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
41  *
42  */
43 
44 #include <algorithm>
45 
46 namespace Gecode { namespace Int { namespace Cumulative {
47 
49  template<class TaskView, bool inc>
50  class StoCap {
51  public:
53  bool operator ()(const TaskView& t1, const TaskView& t2) const {
54  return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c());
55  }
56  };
57 
59  class PrecOrder {
60  public:
61  int* prec;
63  PrecOrder(int* prec0) : prec(prec0) {}
65  bool operator ()(int i, int j) const {
66  return prec[i] > prec[j];
67  }
68  };
69 
70  template<class TaskView>
73  sort<TaskView,STO_LCT,false>(t);
74 
75  Region r(home);
76 
78  // Detection
79 
80  int* prec = r.alloc<int>(t.size());
81  for (int i=t.size(); i--; )
82  prec[i] = t[i].ect();
83 
84  OmegaLambdaTree<TaskView> ol(r,c,t);
85 
86  for (int j=0; j<t.size(); j++) {
87  while (!ol.lempty() &&
88  (ol.lenv() > static_cast<double>(c)*t[j].lct())) {
89  int i = ol.responsible();
90  prec[i] = std::max(prec[i], t[j].lct());
91  ol.lremove(i);
92  }
93  ol.shift(j);
94  }
95 
97  // Propagation
98 
99  // Compute array of unique capacities and a mapping
100  // from the task array to the corresponding entry in
101  // the capacity array
102 
103  int* cap = r.alloc<int>(t.size());
104  for (int i=t.size(); i--;)
105  cap[i] = i;
107  Support::quicksort(cap, t.size(), o);
108 
109  int* capacities = r.alloc<int>(t.size());
110  int* capInv = r.alloc<int>(t.size());
111  for (int i=t.size(); i--;) {
112  capacities[cap[i]] = t[i].c();
113  capInv[cap[i]] = i;
114  }
115 
116  int n_c = 0;
117  for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
118  if (capacities[i] != cur_c)
119  capacities[n_c++] = cur_c = capacities[i];
120  cap[capInv[i]] = n_c-1;
121  }
122  r.free<int>(capInv, t.size());
123 
124  // Compute update values for each capacity and LCut
125 
126  int* update = r.alloc<int>(t.size()*n_c);
127  for (int i=t.size()*n_c; i--;)
128  update[i] = -Int::Limits::infinity;
129 
130  ExtOmegaTree<TaskView> eo(r,c,ol);
131  for (int i=0; i<n_c; i++) {
132  eo.init(capacities[i]);
133  int u = -Int::Limits::infinity;
134  for (int j=t.size(); j--;) {
135  double lctj = static_cast<double>(c-capacities[i])*t[j].lct();
136  double diff_d = ceil(div(plus(eo.env(j), -lctj),capacities[i]));
137  int diff = (diff_d == -Int::Limits::double_infinity) ?
138  -Int::Limits::infinity : static_cast<int>(diff_d);
139  u = std::max(u,diff);
140  update[i*t.size()+j] = u;
141  }
142  }
143 
144  // Update est by iterating in parallel over the prec array
145  // and the task array, both sorted by lct
146 
147  int* precMap = r.alloc<int>(t.size());
148  for (int i=t.size(); i--;)
149  precMap[i] = i;
150  PrecOrder po(prec);
151  Support::quicksort(precMap, t.size(), po);
152 
153  int curJ = 0;
154  for (int i=0; i<t.size(); i++) {
155  // discard any curJ with lct > prec[i]:
156  while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
157  curJ++;
158  if (curJ >= t.size())
159  break;
160  // if lct[curJ] == prec[i], then LCut(T,j) <= i, so update est[i]
161  int locJ = curJ;
162  do {
163  if (t[locJ].lct() != t[precMap[i]].lct()) {
164  GECODE_ME_CHECK(t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+locJ]));
165  break;
166  }
167  } while (t[locJ].lct() == prec[precMap[i]] && locJ++ < t.size() - 1);
168  }
169 
170  return ES_OK;
171  }
172 
173  template<class Task>
174  ExecStatus
175  edgefinding(Space& home, int c, TaskArray<Task>& t) {
177  GECODE_ES_CHECK(edgefinding(home,c,f));
179  GECODE_ES_CHECK(edgefinding(home,c,b));
180  return ES_OK;
181  }
182 
183 }}}
184 
185 // STATISTICS: int-prop