| - Up - | Next >> |
This section describes how to implement constraint systems from scratch. First we will explain the underlying concepts in an informal way and try to draw a big picture of the implementation.
Constraint propagation takes place in a computation space which consists of the constraint store and propagators associated with the constraint store. The constraint store holds variables that either refer to values (i. e., are bound resp. determined) or are unbound. But there may already be some information about the value an unbound variable will later refer to. For example, it might be already known that a variable refers to an integer. We say the variable is constrained, here by a finite domain constraint. This information is stored right at the variable. To provide a generic scheme to associate self-defined constraints with a variable in the constraint store, such a variable has a pointer of type (OZ_Ct *), pointing to a constraint instance of the self-defined constraint system. That is done by defining new constraints as subclasses of OZ_Ct.
The main part of a propagator is its propagation routine. This routine fulfills mainly three tasks. First it retrieves the constraint from the constraint store. The class OZ_CtVar provides a generic interface for that task. Then the propagation algorithm generates new projections on the retrieved constraints. Finally the new constraints are written back to the constraint store. Usually a propagator parameter is shared between more than one propagator. Modifying a constraint in the constraint store may enable another propagators to generate new projections, hence when writing constraints to the store, propagators sharing parameters have to be notified. This is done by the appropriate member functions of OZ_CtVar but to decide what propagators to notify, the propagator has to memorize the constraints present in the constraint store before the propagation algorithm modified the store. The class OZ_CtProfile serves that purpose by providing a generic interface (used in OZ_CtVar) to store characteristic information of a constraint sufficient to derive which propagators have to be notified.
The notification of propagators is realized by wake-up lists associated with the constrained variable. Depending on the kind of constraint system there will be different events a propagator may want to be notified upon. For each event there is a wake-up list. The wake-up events of a constraint system are determined by an object of a subclass of OZ_CtDefinition. Hence, upon creation of a new constrained variable a reference of type OZ_CtDefinition * has to be passed to OZ_mkCtVariable() which takes care of creating variables with generic constraints.
The following sections explain in detail how a constraint system can be implemented using the provided abstractions briefly mentioned in this section.
| - Up - | Next >> |