<< Prev | - Up - | Next >> |
There are situations when a propagator should be replaced by another one. The replacing propagator must have the same declarative semantics, but should provide a more efficient implementation for a particular situation.
Consider the following situation: First a propagator was imposed. At a later point in time the constraint
is told to the constraint store. The equality constraint allows to replace
by
. The rules below show how
can be replaced by another (equality) constraint, if two variables are set equal.
Rule 1:
Rule 2:
Rule 3:
Such simplifications can be implemented by replacing a propagator by another one. The CPI provides for that purpose in OZ_Propagator
a group of member functions replaceBy
. This section demonstrates how to realise the above simplifications using the example of the previous section.
The implementation of the simplification rule requires a propagator for the constraint
. The following code defines the class
TwiceProp
.
class TwiceProp : public OZ_Propagator {
private:
static OZ_PropagatorProfile profile;
OZ_Term _x, _z;
public:
TwiceProp(OZ_Term a, OZ_Term b)
: _x(a), _z(b) {}
virtual OZ_Return propagate(void);
virtual size_t sizeOf(void) {
return sizeof(TwiceProp);
}
virtual void gCollect(void) {
OZ_gCollectTerm(_x);
OZ_gCollectTerm(_z);
}
virtual void sClone(void) {
OZ_sCloneTerm(_x);
OZ_sCloneTerm(_z);
}
virtual OZ_Term getParameters(void) const {
return OZ_cons(_x,
OZ_cons(_z,
OZ_nil()));
}
virtual OZ_PropagatorProfile *getProfile(void) const {
return &profile;
}
};
OZ_PropagatorProfile TwiceProp::profile;
The member function propagate()
mainly consists of a for
-loop collecting in auxiliary variables the values and
satisfying the relation
.
OZ_Return TwiceProp::propagate(void)
{
OZ_FDIntVar x(_x), z(_z);
OZ_FiniteDomain x_aux(fd_empty), z_aux(fd_empty);
for (int i = x->getMinElem(); i != -1;
i = x->getNextLargerElem(i)) {
int i2 = 2 * i;
if (z->isIn(i2)) {
x_aux += i; z_aux += i2;
}
}
FailOnEmpty(*x &= x_aux);
FailOnEmpty(*z &= z_aux);
return (x.leave() | z.leave())
? OZ_SLEEP : OZ_ENTAILED;
failure:
x.fail(); z.fail();
return OZ_FAILED;
}
Imposing equality on variables is done by unification. A propagator is always resumed if at least one variable of its parameters is unified with another variable. The class OZ_Propagator
provides for a member function mayBeEqualVars()
, which returns 1 in case the propagator is resumed because at least one of its parameters was involved in a unification. Otherwise it returns 0.
To detect if the addition propagator is resumed because of a unification the following macro is defined. First, it checks if the propagator's parameters were involved in some unification. If that is the case, all possible combinations of equated variables are tested. The CPI function OZ_isEqualVars()
is provided for that purpose. It takes two heap references and returns 1 if they refer to the same variable. In case equal variables are detected the execution branches to a return
statement, which returns the value produced by executing the function passed as argument of the macro.
#define ReplaceOnUnify(EQ01, EQ02, EQ12) \
if (mayBeEqualVars()) { \
if (OZ_isEqualVars(_x, _y)) { \
return (EQ01); \
} \
if (OZ_isEqualVars(_x, _z)) { \
return (EQ02); \
} \
if (OZ_isEqualVars(_y, _z)) { \
return (EQ12); \
} \
}
The macro is inserted as first statement in the code of the addition propagator. The member functions replaceBy()
and replaceByInt()
provided by OZ_Propagator
replace the addition propagator according to their arguments by another propagator or a basic constraint.
OZ_Return AddProp::propagate(void)
{
ReplaceOnUnify(replaceBy(new TwiceProp(_x, _z)),
replaceByInt(_y, 0),
replaceByInt(_x, 0));
The first argument of the macro causes the addition propagator to be replaced by the twice propagator, which implements reduction rule 1 *. The member function replaceBy()
expects a pointer to a propagator which is generated by applying the new
operator to the constructor of the class TwiceProp
. The second and third macro argument realize the simplification rules 2 * and 3 * by imposing the constraint resp.
.
In most of the cases when propagators are replaced the execution becomes faster without obtaining a stronger propagation simply by the fact that redundant computation is avoided. The example of this section provides for even better propagation by imposing a stronger constraint. This can be observed when running the following Oz code. Of course, the updated module has to be loaded before.
declare X Y Z in
{Browse [X Y Z]} % [X Y Z]
X :: [1 3 5 7 9] % [X{1 3 5 7 9}
Y :: [1 3 5 7 9] % Y{1 3 5 7 9}
Z :: 0#10 % Z{0#10}]
{FD_PROP.add X Y Z} % [X{1 3 5 7 9} Y{1 3 5 7 9}
% Z{2 4 6 8 10}]
X = Y % [Y{1 3 5} Y{1 3 5} Z{2 6 10}]
Note that the constraint causes
to be replaced by
, so that the domain of
and
is further constrained to
, which is not the case for the propagator implemented in Section 1.2.
<< Prev | - Up - | Next >> |