Generated on Sat Jan 12 2019 20:58:51 for Gecode by doxygen 1.8.13
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  * This file is part of Gecode, the generic constraint
16  * development environment:
17  * http://www.gecode.org
18  *
19  * Permission is hereby granted, free of charge, to any person obtaining
20  * a copy of this software and associated documentation files (the
21  * "Software"), to deal in the Software without restriction, including
22  * without limitation the rights to use, copy, modify, merge, publish,
23  * distribute, sublicense, and/or sell copies of the Software, and to
24  * permit persons to whom the Software is furnished to do so, subject to
25  * the following conditions:
26  *
27  * The above copyright notice and this permission notice shall be
28  * included in all copies or substantial portions of the Software.
29  *
30  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
31  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
32  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
33  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
34  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
35  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
36  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
37  *
38  */
39 
40 #include <algorithm>
41 
42 namespace Gecode { namespace Int { namespace Cumulative {
43 
45  template<class TaskView, bool inc>
46  class StoCap {
47  public:
49  bool operator ()(const TaskView& t1, const TaskView& t2) const {
50  return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c());
51  }
52  };
53 
55  class PrecOrder {
56  public:
57  int* prec;
59  PrecOrder(int* prec0) : prec(prec0) {}
61  bool operator ()(int i, int j) const {
62  return prec[i] > prec[j];
63  }
64  };
65 
66  template<class TaskView>
69  sort<TaskView,STO_LCT,false>(t);
70 
71  Region r;
72 
74  // Detection
75 
76  int* prec = r.alloc<int>(t.size());
77  for (int i=0; i<t.size(); i++)
78  prec[i] = t[i].ect();
79 
80  OmegaLambdaTree<TaskView> ol(r,c,t);
81 
82  for (int j=0; j<t.size(); j++) {
83  while (!ol.lempty() &&
84  (ol.lenv() > static_cast<long long int>(c)*t[j].lct())) {
85  int i = ol.responsible();
86  prec[i] = std::max(prec[i], t[j].lct());
87  ol.lremove(i);
88  }
89  ol.shift(j);
90  }
91 
93  // Propagation
94 
95  // Compute array of unique capacities and a mapping
96  // from the task array to the corresponding entry in
97  // the capacity array
98 
99  int* cap = r.alloc<int>(t.size());
100  for (int i=0; i<t.size(); i++)
101  cap[i] = i;
103  Support::quicksort(cap, t.size(), o);
104 
105  int* capacities = r.alloc<int>(t.size());
106  int* capInv = r.alloc<int>(t.size());
107  for (int i=t.size(); i--;) {
108  capacities[cap[i]] = t[i].c();
109  capInv[cap[i]] = i;
110  }
111 
112  int n_c = 0;
113  for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
114  if (capacities[i] != cur_c)
115  capacities[n_c++] = cur_c = capacities[i];
116  cap[capInv[i]] = n_c-1;
117  }
118  r.free<int>(capInv, t.size());
119 
120  // Compute update values for each capacity and LCut
121 
122  int* update = r.alloc<int>(t.size()*n_c);
123  for (int i=0; i<t.size()*n_c; i++)
124  update[i] = -Limits::infinity;
125 
126  ExtOmegaTree<TaskView> eo(r,c,ol);
127  for (int i=0; i<n_c; i++) {
128  eo.init(capacities[i]);
129  int u = -Limits::infinity;
130  for (int j=t.size(); j--;) {
131  long long int lctj =
132  static_cast<long long int>(c-capacities[i])*t[j].lct();
133  long long int eml = plus(eo.env(j), -lctj);
134  long long int diff_l;
135  if (eml == -Limits::llinfinity)
136  diff_l = -Limits::llinfinity;
137  else
138  diff_l = ceil_div_xx(eml,
139  static_cast<long long int>(capacities[i]));
140  int diff = (diff_l <= -Limits::infinity) ?
141  -Limits::infinity : static_cast<int>(diff_l);
142  u = std::max(u,diff);
143  update[i*t.size()+j] = u;
144  }
145  }
146 
147  // Update est by iterating in parallel over the prec array
148  // and the task array, both sorted by lct
149 
150  int* precMap = r.alloc<int>(t.size());
151  for (int i=0; i<t.size(); i++)
152  precMap[i] = i;
153  PrecOrder po(prec);
154  Support::quicksort(precMap, t.size(), po);
155 
156  int curJ = 0;
157  for (int i=0; i<t.size(); i++) {
158  // discard any curJ with lct > prec[i]:
159  while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
160  curJ++;
161  if (curJ >= t.size())
162  break;
163  // if lct[curJ] == prec[i], then LCut(T,j) <= i, so update est[i]
164  int locJ = curJ;
165  do {
166  if (t[locJ].lct() != t[precMap[i]].lct()) {
167  GECODE_ME_CHECK(t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+locJ]));
168  break;
169  }
170  } while (t[locJ].lct() == prec[precMap[i]] && locJ++ < t.size() - 1);
171  }
172 
173  return ES_OK;
174  }
175 
176  template<class Task>
177  ExecStatus
180  GECODE_ES_CHECK(edgefinding(home,c,f));
182  GECODE_ES_CHECK(edgefinding(home,c,b));
183  return ES_OK;
184  }
185 
186 }}}
187 
188 // STATISTICS: int-prop
long long int env(int i)
Compute update for task with index i.
Definition: tree.hpp:120
NodeType t
Type of node.
Definition: bool-expr.cpp:230
Task view array.
Definition: task.hh:233
Omega-lambda trees for computing ect of task sets.
Definition: cumulative.hh:645
const FloatNum max
Largest allowed float value.
Definition: float.hh:844
bool lempty(void) const
Whether has responsible task.
Definition: tree.hpp:248
void shift(int i)
Shift task with index i from omega to lambda.
Definition: tree.hpp:221
PrecOrder(int *prec0)
Constructor.
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:142
Omega trees for computing ect of task sets.
Definition: cumulative.hh:594
Task array.
Definition: task.hh:165
Handle to region.
Definition: region.hpp:55
#define forceinline
Definition: config.hpp:185
Computation spaces.
Definition: core.hpp:1701
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition: macros.hpp:91
Gecode::FloatVal c(-8, 8)
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition: sort.hpp:130
Gecode::IntArgs i({1, 2, 3, 4})
Sorting maps rather than tasks.
Definition: sort.hpp:72
struct Gecode::@593::NNF::@62::@63 b
For binary nodes (and, or, eqv)
int plus(int x, int y)
Safe addition in case x is -IntLimits::infinity.
Definition: tree.hpp:39
void init(int ci)
Initialize tasks for current capacity ci.
Definition: tree.hpp:104
IntType ceil_div_xx(IntType x, IntType y)
Compute .
Definition: div.hpp:82
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition: macros.hpp:52
union Gecode::@593::NNF::@62 u
Union depending on nodetype t.
Post propagator for SetVar SetOpType SetVar SetRelType r
Definition: set.hh:767
int responsible(void) const
Return responsible task.
Definition: tree.hpp:254
Post propagator for f(x \diamond_{\mathit{op}} y) \sim_r z \f$ void rel(Home home
const int infinity
Infinity for integers.
Definition: int.hh:120
long long int lenv(void) const
Return energy envelope of all tasks excluding lambda tasks.
Definition: tree.hpp:266
ExecStatus
Definition: core.hpp:471
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Execution is okay.
Definition: core.hpp:475
Gecode toplevel namespace
const long long int llinfinity
Infinity for long long integers.
Definition: int.hh:126
void update(IntSet &y, Space &home, IntSet &py)
Definition: rel.hpp:103
ExecStatus edgefinding(Space &home, int c, TaskViewArray< TaskView > &t)
void lremove(int i)
Remove task with index i from lambda.
Definition: tree.hpp:235