dom.hpp
Go to the documentation of this file.
/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
/*
* Main authors:
* Patrick Pekczynski <pekczynski@ps.uni-sb.de>
*
* Contributing authors:
* Christian Schulte <schulte@gecode.org>
* Guido Tack <tack@gecode.org>
*
* Copyright:
* Patrick Pekczynski, 2004
* Christian Schulte, 2009
* Guido Tack, 2009
*
* 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.
*
*/
namespace Gecode { namespace Int { namespace GCC {
/*
* Analogously to "gcc/bnd.hpp" we split the algorithm
* in two parts:
* 1) the UBC (Upper Bound Constraint) stating that there are
* at most k[i].max() occurences of the value v_i
* 2) the LBC (Lower Bound Constraint) stating that there are
* at least k[i].min() occurences of the value v_i
*
* The algorithm proceeds in 5 STEPS:
*
* STEP 1:
* Build the bipartite value-graph G=(<X,D>,E),
* with X = all variable nodes (each variable forms a node)
* D = all value nodes (union over all domains of the variables)
* and (x_i,v) is an edge in G iff value v is in the domain D_i of x_i
*
* STEP 2: Compute a matching in the value graph.
* STEP 3: Compute all even alternating paths from unmatched nodes
* STEP 4: Compute strongly connected components in the merged graph
* STEP 5: Update the Domains according to the computed edges
*
*/
template<class Card>
inline
Dom<Card>::Dom(Home home, ViewArray<IntView>& x0,
ViewArray<Card>& k0, bool cf)
: Propagator(home), x(x0), y(home, x0),
k(k0), vvg(NULL), card_fixed(cf){
// y is used for bounds propagation since prop_bnd needs all variables
// values within the domain bounds
x.subscribe(home, *this, PC_INT_DOM);
k.subscribe(home, *this, PC_INT_DOM);
}
template<class Card>
forceinline
Dom<Card>::Dom(Space& home, Dom<Card>& p)
: Propagator(home, p), vvg(NULL), card_fixed(p.card_fixed) {
x.update(home, p.x);
y.update(home, p.y);
k.update(home, p.k);
}
template<class Card>
forceinline size_t
Dom<Card>::dispose(Space& home) {
x.cancel(home,*this, PC_INT_DOM);
k.cancel(home,*this, PC_INT_DOM);
(void) Propagator::dispose(home);
return sizeof(*this);
}
template<class Card>
Actor*
Dom<Card>::copy(Space& home) {
return new (home) Dom<Card>(home, *this);
}
template<class Card>
PropCost
Dom<Card>::cost(const Space&, const ModEventDelta&) const {
return PropCost::cubic(PropCost::LO, x.size());
}
template<class Card>
void
Dom<Card>::reschedule(Space& home) {
x.reschedule(home, *this, PC_INT_DOM);
k.reschedule(home, *this, PC_INT_DOM);
}
template<class Card>
ExecStatus
Dom<Card>::propagate(Space& home, const ModEventDelta&) {
Region r;
int* count = r.alloc<int>(k.size());
for (int i = k.size(); i--; )
count[i] = 0;
// total number of assigned views
int noa = 0;
for (int i = y.size(); i--; )
if (y[i].assigned()) {
noa++;
int idx;
if (!lookupValue(k,y[i].val(),idx))
return ES_FAILED;
count[idx]++;
if (Card::propagate && (k[idx].max() == 0))
return ES_FAILED;
}
if (noa == y.size()) {
// All views are assigned
for (int i = k.size(); i--; ) {
if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
return ES_FAILED;
// the solution contains ci occurences of value k[i].card();
if (Card::propagate)
GECODE_ME_CHECK(k[i].eq(home, count[i]));
}
return home.ES_SUBSUMED(*this);
}
// before propagation performs inferences on cardinality variables:
if (Card::propagate) {
if (noa > 0)
for (int i = k.size(); i--; )
if (!k[i].assigned()) {
GECODE_ME_CHECK(k[i].lq(home, y.size() - (noa - count[i])));
GECODE_ME_CHECK(k[i].gq(home, count[i]));
}
GECODE_ES_CHECK(prop_card<Card>(home,y,k));
if (!card_consistent<Card>(y,k))
return ES_FAILED;
}
if (x.size() == 0) {
for (int j = k.size(); j--; )
if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
return ES_FAILED;
return home.ES_SUBSUMED(*this);
} else if ((x.size() == 1) && (x[0].assigned())) {
int idx;
if (!lookupValue(k,x[0].val(),idx))
return ES_FAILED;
GECODE_ME_CHECK(k[idx].inc());
for (int j = k.size(); j--; )
if ((k[j].min() > k[j].counter()) || (k[j].max() < k[j].counter()))
return ES_FAILED;
return home.ES_SUBSUMED(*this);
}
if (vvg == NULL) {
int smin = 0;
int smax = 0;
for (int i=k.size(); i--; )
if (k[i].counter() > k[i].max() ) {
return ES_FAILED;
} else {
smax += (k[i].max() - k[i].counter());
if (k[i].counter() < k[i].min())
smin += (k[i].min() - k[i].counter());
}
if ((x.size() < smin) || (smax < x.size()))
return ES_FAILED;
vvg = new (home) VarValGraph<Card>(home, x, k, smin, smax);
GECODE_ES_CHECK(vvg->min_require(home,x,k));
GECODE_ES_CHECK(vvg->template maximum_matching<UBC>());
if (!card_fixed)
GECODE_ES_CHECK(vvg->template maximum_matching<LBC>());
} else {
GECODE_ES_CHECK(vvg->sync(x,k));
}
vvg->template free_alternating_paths<UBC>();
vvg->template strongly_connected_components<UBC>();
GECODE_ES_CHECK(vvg->template narrow<UBC>(home,x,k));
if (!card_fixed) {
if (Card::propagate)
GECODE_ES_CHECK(vvg->sync(x,k));
vvg->template free_alternating_paths<LBC>();
vvg->template strongly_connected_components<LBC>();
GECODE_ES_CHECK(vvg->template narrow<LBC>(home,x,k));
}
{
bool card_assigned = true;
if (Card::propagate) {
GECODE_ES_CHECK(prop_card<Card>(home, y, k));
card_assigned = k.assigned();
}
if (card_assigned) {
if (x.size() == 0) {
for (int j=k.size(); j--; )
if ((k[j].min() > k[j].counter()) ||
(k[j].max() < k[j].counter()))
return ES_FAILED;
return home.ES_SUBSUMED(*this);
} else if ((x.size() == 1) && x[0].assigned()) {
int idx;
if (!lookupValue(k,x[0].val(),idx))
return ES_FAILED;
GECODE_ME_CHECK(k[idx].inc());
for (int j = k.size(); j--; )
if ((k[j].min() > k[j].counter()) ||
(k[j].max() < k[j].counter()))
return ES_FAILED;
return home.ES_SUBSUMED(*this);
}
}
}
for (int i = k.size(); i--; )
count[i] = 0;
bool all_assigned = true;
// total number of assigned views
for (int i = y.size(); i--; )
if (y[i].assigned()) {
int idx;
if (!lookupValue(k,y[i].val(),idx))
return ES_FAILED;
count[idx]++;
if (Card::propagate && (k[idx].max() == 0))
return ES_FAILED;
} else {
all_assigned = false;
}
if (Card::propagate)
GECODE_ES_CHECK(prop_card<Card>(home, y, k));
if (all_assigned) {
for (int i = k.size(); i--; ) {
if ((k[i].min() > count[i]) || (count[i] > k[i].max()))
return ES_FAILED;
// the solution contains count[i] occurences of value k[i].card();
if (Card::propagate)
GECODE_ME_CHECK(k[i].eq(home,count[i]));
}
return home.ES_SUBSUMED(*this);
}
if (Card::propagate) {
int ysmax = y.size();
for (int i=k.size(); i--; )
ysmax -= k[i].max();
int smax = 0;
bool card_ass = true;
for (int i = k.size(); i--; ) {
GECODE_ME_CHECK(k[i].gq(home, ysmax + k[i].max()));
smax += k[i].max();
GECODE_ME_CHECK(k[i].lq(home, y.size() + k[i].min()));
if (!k[i].assigned())
card_ass = false;
}
if (card_ass && (smax != y.size()))
return ES_FAILED;
}
return Card::propagate ? ES_NOFIX : ES_FIX;
}
template<class Card>
inline ExecStatus
Dom<Card>::post(Home home,
ViewArray<IntView>& x, ViewArray<Card>& k) {
GECODE_ES_CHECK((postSideConstraints<Card>(home,x,k)));
if (isDistinct<Card>(x,k))
return Distinct::Dom<IntView>::post(home,x);
bool cardfix = true;
for (int i = k.size(); i--; )
if (!k[i].assigned()) {
cardfix = false; break;
}
(void) new (home) Dom<Card>(home,x,k,cardfix);
return ES_OK;
}
}}}
// STATISTICS: int-prop
Gecode::Actor
Base-class for both propagators and branchers.
Definition core.hpp:628
Gecode::Actor::dispose
virtual size_t dispose(Space &home)
Delete actor and return its size.
Definition core.hpp:3252
Gecode::Home
Home class for posting propagators
Definition core.hpp:856
Gecode::Int::Distinct::Dom::post
static ExecStatus post(Home home, ViewArray< View > &x)
Post propagator for views x.
Definition dom.hpp:45
Gecode::Int::GCC::Dom::card_fixed
bool card_fixed
Stores whether cardinalities are all assigned.
Definition gcc.hh:238
Gecode::Int::GCC::Dom::dispose
virtual size_t dispose(Space &home)
Destructor.
Definition dom.hpp:88
Gecode::Int::GCC::Dom::propagate
virtual ExecStatus propagate(Space &home, const ModEventDelta &med)
Perform propagation.
Definition dom.hpp:116
Gecode::Int::GCC::Dom::vvg
VarValGraph< Card > * vvg
Propagation is performed on a variable-value graph (used as cache).
Definition gcc.hh:231
Gecode::Int::GCC::Dom::copy
virtual Actor * copy(Space &home)
Copy propagator during cloning.
Definition dom.hpp:97
Gecode::Int::GCC::Dom::y
ViewArray< IntView > y
Views used to channel information between x and k ( ).
Definition gcc.hh:227
Gecode::Int::GCC::Dom::x
ViewArray< IntView > x
Views on which to perform domain-propagation.
Definition gcc.hh:222
Gecode::Int::GCC::Dom::cost
virtual PropCost cost(const Space &home, const ModEventDelta &med) const
Cost function.
Definition dom.hpp:103
Gecode::Int::GCC::Dom::Dom
Dom(Space &home, Dom< Card > &p)
Constructor for cloning p.
Definition dom.hpp:79
Gecode::Int::GCC::Dom::k
ViewArray< Card > k
Array containing either fixed cardinalities or CardViews.
Definition gcc.hh:229
Gecode::Int::GCC::Dom::reschedule
virtual void reschedule(Space &home)
Schedule function.
Definition dom.hpp:109
Gecode::Int::GCC::Dom::post
static ExecStatus post(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post propagator for views x and cardinalities k.
Definition dom.hpp:299
Gecode::Int::GCC::VarValGraph
Variable-value-graph used during propagation.
Definition dom-sup.hpp:387
Gecode::PropCost
Propagation cost.
Definition core.hpp:486
Gecode::PropCost::cubic
static PropCost cubic(PropCost::Mod m, unsigned int n)
Cubic complexity for modifier m and size measure n.
Definition core.hpp:4778
Gecode::PropCost::LO
@ LO
Cheap.
Definition core.hpp:513
Gecode::Propagator::Space
friend class Space
Definition core.hpp:1066
Gecode::Propagator::Propagator
Propagator(Home home)
Constructor for posting.
Definition core.hpp:3498
Gecode::Region
Handle to region.
Definition region.hpp:55
Gecode::ViewArray
View arrays.
Definition array.hpp:253
Gecode::Int::GCC::card_consistent
bool card_consistent(ViewArray< IntView > &x, ViewArray< Card > &k)
Consistency check, whether the cardinality values are feasible.
Definition bnd-sup.hpp:139
Gecode::Int::GCC::prop_card
ExecStatus prop_card(Space &home, ViewArray< IntView > &x, ViewArray< Card > &k)
Bounds consistency check for cardinality variables.
Definition bnd-sup.hpp:74
Gecode::Space::ES_SUBSUMED
ExecStatus ES_SUBSUMED(Propagator &p)
Definition core.hpp:3563
Gecode::ModEventDelta
int ModEventDelta
Modification event deltas.
Definition core.hpp:89
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::GCC
Global cardinality propagators (Counting).
Gecode::Int::GCC::isDistinct
bool isDistinct(ViewArray< IntView > &x, ViewArray< Card > &k)
Check if GCC is equivalent to distinct.
Definition post.hpp:138
Gecode::Int::GCC::lookupValue
bool lookupValue(T &a, int v, int &i)
Return index of v in array a.
Definition view.hpp:45
Gecode::Int::GCC::postSideConstraints
ExecStatus postSideConstraints(Home home, ViewArray< IntView > &x, ViewArray< Card > &k)
Post side constraints for the GCC.
Definition post.hpp:60
Gecode::Int
Finite domain integers.
Gecode::Int::PC_INT_DOM
const Gecode::PropCond PC_INT_DOM
Propagate when domain changes.
Definition var-type.hpp:100
Gecode
Gecode toplevel namespace
Gecode::count
void count(Home home, const IntVarArgs &x, int n, IntRelType irt, int m, IntPropLevel ipl=IPL_DEF)
Post propagator for .
Definition count.cpp:40
Gecode::min
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:67
Gecode::ExecStatus
ExecStatus
Definition core.hpp:472
Gecode::ES_OK
@ ES_OK
Execution is okay.
Definition core.hpp:476
Gecode::ES_FIX
@ ES_FIX
Propagation has computed fixpoint.
Definition core.hpp:477
Gecode::ES_FAILED
@ ES_FAILED
Execution has resulted in failure.
Definition core.hpp:474
Gecode::ES_NOFIX
@ ES_NOFIX
Propagation has not computed fixpoint.
Definition core.hpp:475
Gecode::max
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition arithmetic.cpp:49
forceinline
#define forceinline
Definition config.hpp:187