This page gives brief explanations about some of the most frequently occurring terms (currently limited to important entities manifest in the implementation) used in the Gecode/J reference documentation.
An actor is either a branching (
Branching) or a propagator (
Propagator). Actors provide the functionality that is common for propagators and branchings such as member functions for copying during cloning, memory allocation, and so on. Actors are implemented by the class org.gecode.Actor. More on programming actors can be found in the module
Programming actors.
A branching defines the shape of the search tree. Branchings are also known as labelings or distributors, and a branching creates a series of choice points. Branchings are implemented by the class
org.gecode.Branching. A common abstraction for defining branchings based on view and value selection is provided by the class org.gecode.ViewValBranching.
A branching description speeds up recomputation by providing batch recomputation. It is created by a branching (
Branching) and allows to replay the effect of that branching without the need to first perform constraint propagation. The base-class for branching descriptions is
org.gecode.BranchingDesc. An example for a branching description that works together with branchings based on view and value selection is org.gecode.PosValDesc.
A computation space (space for short) comprises all entities for a constraint problem to be solved, including all actors (
Actor) and variables (
Variable). A space can be seen as corresponding to a node in the search tree. It organizes constraint propagation, the branching process, exploration, and memory management. Spaces are implemented by the class
org.gecode.Space. They provide functionality for
Setting up scripts,
Programming search engines, and FuncMemSpace.
A modification event describes how a view (
View) or variable implementation (GlossaryVarImp) is changed by an update operation performed on the view or variable. Each variable domain defines its own modification events (see TaskActorIntMEPC and TaskActorSetMEPC). However modification events that describe generic events such as failure, no modification, or assignment to a single value are predefined (see
Generic modification events and propagation conditions).
A propagation condition defines when a propagator requires to be re-executed. Re-execution is controlled by the modification events that occur on the variables the propagator depends on (see
Propagator). Propagation conditions and the relation between propagation conditions and modification events depends on the variable domain (see TaskActorIntMEPC and TaskActorSetMEPC). However, the propagation conditions that states re-execution when a variable becomes assigned is generic (see
Generic modification events and propagation conditions).
A propagator implements a constraint (actually, a constraint can be implemented by a collection of propagators). Execution by a propagator is defined by its dependencies: the views (referring to some variables) together with their propagation conditions. A propagator is implemented by inheriting from the class
org.gecode.Propagator. Common abstractions for propagators are also available (see TaskPropPat, TaskPropRePat, and TaskPropSetPat).
A propagator maintains as propagator modification event for each variable domain a modification event. These modification events describe which modification events occurred on all views (variables) the propagator depends on (see
Propagator). A propagator modification event is available through a view or variable implementation (see for example
Integer views or
Set views).
A variable is used for modeling problems, be it for direct modeling or for modeling through some interface. A variable provides only those operations useful for modeling and excludes in particular operations that can modify the variable domain directly. A variable is implemented by a variable implementation (see below).
A view offers essentially the same interface as a variable implementation and allows both domain access and modification. Typically, several views exist for the same variable implementation to obtain several constraints from the same propagator. Examples of views are
Integer views and
Set views.
