edge-finding.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Christian Schulte <schulte@gecode.org>
* Guido Tack <tack@gecode.org>
*
* Contributing authors:
* Joseph Scott <joseph.scott@it.uu.se>
*
* Copyright:
* Christian Schulte, 2009
* Guido Tack, 2010
* Joseph Scott, 2011
*
* This file is part of Gecode, the generic constraint
* development environment:
* http://www.gecode.org
*
* Permission is hereby granted, free of charge, to any person obtaining
* a copy of this software and associated documentation files (the
* "Software"), to deal in the Software without restriction, including
* without limitation the rights to use, copy, modify, merge, publish,
* distribute, sublicense, and/or sell copies of the Software, and to
* permit persons to whom the Software is furnished to do so, subject to
* the following conditions:
*
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
* LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
* OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
* WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*
*/
#include <algorithm>
namespace Gecode { namespace Int { namespace Cumulative {
template<class TaskView, bool inc>
class StoCap {
public:
bool operator ()(const TaskView& t1, const TaskView& t2) const {
return inc ? (t1.c() < t2.c()) : (t2.c() < t1.c());
}
};
class PrecOrder {
public:
int* prec;
PrecOrder(int* prec0) : prec(prec0) {}
bool operator ()(int i, int j) const {
return prec[i] > prec[j];
}
};
template<class TaskView>
forceinline ExecStatus
edgefinding(Space& home, int c, TaskViewArray<TaskView>& t) {
sort<TaskView,STO_LCT,false>(t);
Region r;
// Detection
int* prec = r.alloc<int>(t.size());
for (int i=0; i<t.size(); i++)
prec[i] = t[i].ect();
OmegaLambdaTree<TaskView> ol(r,c,t);
for (int j=0; j<t.size(); j++) {
while (!ol.lempty() &&
(ol.lenv() > static_cast<long long int>(c)*t[j].lct())) {
int i = ol.responsible();
prec[i] = std::max(prec[i], t[j].lct());
ol.lremove(i);
}
ol.shift(j);
}
// Propagation
// Compute array of unique capacities and a mapping
// from the task array to the corresponding entry in
// the capacity array
int* cap = r.alloc<int>(t.size());
for (int i=0; i<t.size(); i++)
cap[i] = i;
SortMap<TaskView,StoCap,true> o(t);
Support::quicksort(cap, t.size(), o);
int* capacities = r.alloc<int>(t.size());
int* capInv = r.alloc<int>(t.size());
for (int i=t.size(); i--;) {
capacities[cap[i]] = t[i].c();
capInv[cap[i]] = i;
}
int n_c = 0;
for (int i=0, cur_c=INT_MIN; i<t.size(); i++) {
if (capacities[i] != cur_c)
capacities[n_c++] = cur_c = capacities[i];
cap[capInv[i]] = n_c-1;
}
r.free<int>(capInv, t.size());
// Compute update values for each capacity and LCut
int* update = r.alloc<int>(t.size()*n_c);
for (int i=0; i<t.size()*n_c; i++)
update[i] = -Limits::infinity;
ExtOmegaTree<TaskView> eo(r,c,ol);
for (int i=0; i<n_c; i++) {
eo.init(capacities[i]);
int u = -Limits::infinity;
for (int j=t.size(); j--;) {
long long int lctj =
static_cast<long long int>(c-capacities[i])*t[j].lct();
long long int eml = plus(eo.env(j), -lctj);
long long int diff_l;
if (eml == -Limits::llinfinity)
diff_l = -Limits::llinfinity;
else
diff_l = ceil_div_xx(eml,
static_cast<long long int>(capacities[i]));
int diff = (diff_l <= -Limits::infinity) ?
-Limits::infinity : static_cast<int>(diff_l);
u = std::max(u,diff);
update[i*t.size()+j] = u;
}
}
// Update est by iterating in parallel over the prec array
// and the task array, both sorted by lct
int* precMap = r.alloc<int>(t.size());
for (int i=0; i<t.size(); i++)
precMap[i] = i;
PrecOrder po(prec);
Support::quicksort(precMap, t.size(), po);
int curJ = 0;
for (int i=0; i<t.size(); i++) {
// discard any curJ with lct > prec[i]:
while (curJ < t.size() && t[curJ].lct() > prec[precMap[i]])
curJ++;
if (curJ >= t.size())
break;
// if lct[curJ] == prec[i], then LCut(T,j) <= i, so update est[i]
int locJ = curJ;
do {
if (t[locJ].lct() != t[precMap[i]].lct()) {
GECODE_ME_CHECK(t[precMap[i]].est(home,update[cap[precMap[i]]*t.size()+locJ]));
break;
}
} while (t[locJ].lct() == prec[precMap[i]] && locJ++ < t.size() - 1);
}
return ES_OK;
}
template<class Task>
ExecStatus
edgefinding(Space& home, int c, TaskArray<Task>& t) {
TaskViewArray<typename TaskTraits<Task>::TaskViewFwd> f(t);
GECODE_ES_CHECK(edgefinding(home,c,f));
TaskViewArray<typename TaskTraits<Task>::TaskViewBwd> b(t);
GECODE_ES_CHECK(edgefinding(home,c,b));
return ES_OK;
}
}}}
// STATISTICS: int-prop
Gecode::Int::Cumulative::ExtOmegaTree
Omega trees for computing ect of task sets.
Definition cumulative.hh:594
Gecode::Int::Cumulative::ExtOmegaTree::env
long long int env(int i)
Compute update for task with index i.
Definition tree.hpp:120
Gecode::Int::Cumulative::ExtOmegaTree::init
void init(int ci)
Initialize tasks for current capacity ci.
Definition tree.hpp:104
Gecode::Int::Cumulative::OmegaLambdaTree
Omega-lambda trees for computing ect of task sets.
Definition cumulative.hh:645
Gecode::Int::Cumulative::OmegaLambdaTree::responsible
int responsible(void) const
Return responsible task.
Definition tree.hpp:254
Gecode::Int::Cumulative::OmegaLambdaTree::lenv
long long int lenv(void) const
Return energy envelope of all tasks excluding lambda tasks.
Definition tree.hpp:266
Gecode::Int::Cumulative::OmegaLambdaTree::shift
void shift(int i)
Shift task with index i from omega to lambda.
Definition tree.hpp:221
Gecode::Int::Cumulative::OmegaLambdaTree::lremove
void lremove(int i)
Remove task with index i from lambda.
Definition tree.hpp:235
Gecode::Int::Cumulative::OmegaLambdaTree::lempty
bool lempty(void) const
Whether has responsible task.
Definition tree.hpp:248
Gecode::Int::Cumulative::PrecOrder
Sort by prec array.
Definition edge-finding.hpp:55
Gecode::Int::Cumulative::PrecOrder::prec
int * prec
Definition edge-finding.hpp:57
Gecode::Int::Cumulative::PrecOrder::PrecOrder
PrecOrder(int *prec0)
Constructor.
Definition edge-finding.hpp:59
Gecode::Int::Cumulative::PrecOrder::operator()
bool operator()(int i, int j) const
Sort order.
Definition edge-finding.hpp:61
Gecode::Int::Cumulative::StoCap
Sort by capacity.
Definition edge-finding.hpp:46
Gecode::Int::Cumulative::StoCap::operator()
bool operator()(const TaskView &t1, const TaskView &t2) const
Sort order.
Definition edge-finding.hpp:49
Gecode::Int::SortMap
Sorting maps rather than tasks.
Definition sort.hpp:72
Gecode::Int::TaskArray
Task array.
Definition task.hh:165
Gecode::Int::TaskViewArray
Task view array.
Definition task.hh:233
Gecode::Int::TaskViewArray::size
int size(void) const
Return size of array (number of elements).
Definition array.hpp:142
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::Space
Computation spaces.
Definition core.hpp:1742
Gecode::Int::OffsetView::update
void update(const NoOffset &)
Integer-precision integer scale view.
Definition view.hpp:638
GECODE_ME_CHECK
#define GECODE_ME_CHECK(me)
Check whether modification event me is failed, and forward failure.
Definition macros.hpp:52
GECODE_ES_CHECK
#define GECODE_ES_CHECK(es)
Check whether execution status es is failed or subsumed, and forward failure or subsumption.
Definition macros.hpp:91
Gecode::Int::Cumulative
Scheduling for cumulative resources
Definition cumulative.cpp:40
Gecode::Int::Cumulative::edgefinding
ExecStatus edgefinding(Space &home, int c, TaskArray< Task > &t)
Propagate by edge-finding.
Definition edge-finding.hpp:178
Gecode::Int::Limits::infinity
const int infinity
Infinity for integers.
Definition int.hh:120
Gecode::Int::Limits::llinfinity
const long long int llinfinity
Infinity for long long integers.
Definition int.hh:126
Gecode::Int
Finite domain integers.
Gecode::Int::sort
void sort(TaskViewArray< TaskView > &t)
Sort task view array t according to sto and inc (increasing or decreasing).
Definition sort.hpp:133
Gecode::Int::plus
int plus(int x, int y)
Safe addition in case x is -Int::Limits::infinity.
Definition tree.hpp:39
Gecode::Int::ceil_div_xx
IntType ceil_div_xx(IntType x, IntType y)
Compute .
Definition div.hpp:82
Gecode::Support::quicksort
void quicksort(Type *l, Type *r, Less &less)
Standard quick sort.
Definition sort.hpp:130
Gecode
Gecode toplevel namespace
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
forceinline
#define forceinline
Definition config.hpp:187