jpaul.Constraints
Class Constraint<V extends Var<Info>,Info>

java.lang.Object
  jpaul.Constraints.Constraint<V,Info>

Direct Known Subclasses:

CtConstraint, FilterConstraint, IntersectConstraint, LtConstraint

public abstract class Constraint<V extends Var<Info>,Info>
extends java.lang.Object

Constraint models a constraint between several variables. Mathematically, a constraint has the form:

f(<vi_1,vi_2,...,vi_m>) <= <vo_1,vo_2,...,vo_n>

where vi_1, vi_2, ..., vi_m are the input variables of the constraints, vo_1, vo_2, ..., vo_n are the output variables, and f is a computable function.

We solve a constraint system by repeatedly applying the constraints until we obtain a fixed point. Hence, we use an operational interpretation of a constraint: a constraint reads the values of the input variables (see method in()) and next computes and joins some deltas to the values of the output variables (see method out()); the sets of in- and out-variables are not necessarily disjoint. Notice that a constraint cannot decrease the value attached to any variable; hence, the values of all variables increase, and (if the domains have finite height), the fixed-point solver will terminate (Note: this is a solution according to our operational view of the constraints; hopefully, this is identical to your intended constrain meaning).

The cost of a constraint is supposed to be a very rough approximation of the constraint computation cost (see cost()). This measure is used by the constraint solver in order to increase its speed.

To define new constraints, you have to subclass this class and provide implementation for its abstract methods. Here is a sample new constraint: simplified SetConstraints.IntersectConstraint.

Version:

$Id: Constraint.java,v 1.14 2006/01/31 00:42:56 adam_kiezun Exp $

Author:

Alexandru Salcianu - salcianu@alum.mit.edu

See Also:

CtConstraint, LtConstraint

Field Summary

static int	AVG_COST Possible constraint cost; see cost()
static int	HIGH_COST Possible constraint cost; see cost()
static int	LOW_COST Possible constraint cost; see cost()
static int	VERY_LOW_COST Possible constraint cost; see cost()

Constructor Summary

Constraint()

Method Summary

abstract void	action(SolAccessor<V,Info> sa) Performs the action attached to this constraint.
int	cost() Returns a rough estimate of the evaluation cost of this constraint.
abstract java.util.Collection<V>	in()
abstract java.util.Collection<V>	out()
Constraint<V,Info>	rewrite(UnionFind<V> uf) Rewrites this constraint by replacing each variable with the representative of its equivalence class.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

VERY_LOW_COST

public static final int VERY_LOW_COST

Possible constraint cost; see cost()

See Also:

Constant Field Values

LOW_COST

public static final int LOW_COST

Possible constraint cost; see cost()

See Also:

Constant Field Values

AVG_COST

public static final int AVG_COST

Possible constraint cost; see cost()

See Also:

Constant Field Values

HIGH_COST

public static final int HIGH_COST

Possible constraint cost; see cost()

See Also:

Constant Field Values

Constructor Detail

Constraint

public Constraint()

Method Detail

in

public abstract java.util.Collection<V> in()

Returns:

List of variables whose values may be read in order to construct the values of the outputs.

out

public abstract java.util.Collection<V> out()

Returns:

List of variables whose values may be affected by this constraint.

action

public abstract void action(SolAccessor<V,Info> sa)

Performs the action attached to this constraint. The action should have the following form:

1. Read the values of several in-variables using sa.get.
2. Compute some values.
3. Use sa.join to join the computed values to several out-variables.

Note1: It is a serious mistake to write an action method that reads/modifies variables that are not listed in the collections returned by in()/out(). If you ever suspect such an error, please set ConstraintSystem.CHECK_IN_OUT to true.

Note2: The solver initializes each variable to null (null is considered equivalent to the bottom element of the correspoding lattice). The body of action should be prepared to receive a null result from sa.get.

Parameters:

sa - Provides access to the values of the variables that are read/modified.

rewrite

public Constraint<V,Info> rewrite(UnionFind<V> uf)

Rewrites this constraint by replacing each variable with the representative of its equivalence class. The real implementation of this method is optional: the default implementation returns this constraint, unmodified. This is safe: the constraint writer does not need to be aware of variable unification, as the SolAccessor passed by the constraint solver already deals with it.

Implementing rewrite may be useful when unification causes several constraints to become identical: e.g., consider v1 <= v2 and v3 <= v4, after we unify v1 with v3 and v2 with v4. Implementing rewrite, equals (and hashCode) allows the solver to avoid working with several identical constraints.

Parameters:

uf - Union-find structure; for each variable v, uf.find(v) is the representative of its equivalence class.

cost

public int cost()

Returns a rough estimate of the evaluation cost of this constraint. This cost has only a relative meaning: e.g., a constraint is more/less costly than another. A constraint solver may choose to iterate first over the cheap constraints, and only next iterate over the other, more expensive constraints. The cost should influence only the speed, not the correctness: the solution of a system of constraints should satisfy all constraints, regardless of their cost.

By default, it returns AVG_COST.