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 reference documentation.
An actor is a branching (
Branching), a propagator (
Propagator), or an advisor (
Advisor). Actors provide common functionality such as member functions for copying during cloning, memory allocation, and so on. Actors are implemented by the class
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
Gecode::Branching. A common abstraction for defining branchings based on view and value selection is provided by the class
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
Gecode::BranchingDesc. An example for a branching description that works together with branchings based on view and value selection is
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
Gecode::Space. They provide functionality for
Setting up scripts,
Programming search engines, and
Space-memory management.
A modification event describes how a view (
View) or variable implementation (
Variable implementation) 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
Gecode::Propagator. Common abstractions for propagators are also available (see
Propagator patterns,
Reified propagator patterns, and
Patterns for set propagators).
An advisor supports a single propagator. An advisor is executed whenever the view it has subscribed to is modified. Execution of an advisor amounts to executing the advise member function of the advisor's propagator where the advisor and delta information (
Delta information) are passed as arguments. An advisor is implemented by inheriting from the class
Gecode::Advisor.
Delta information is implemented as an object which is a subclass of
Gecode::Delta. A Delta object describes how the domain of a variable has been changed by an operation on the variable. Delta objects are passed together with advisors to the advise member function of a propagator.
A propagator maintains a delta of modification events for all variable types. A modification event delta is available to the propagate and cost member functions of a propagator and describes the modification events that have occurred since the last execution of a propagator. A modification event delta is highly abstract: it does not reveal for which variable a particular modification event occurred, it only reveals that a certain modification event has occurred for any variable of a given variable type. Modification events for a particular variable type can be extracted from a modification event delta through the respective 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 variable implementation is implemented by inheriting from Gecode::Variable. It implements the variable domain and provides operations to access and modify the domain. Examples of variable implementations are
Gecode::Int::IntVarImp and
Gecode::Set::SetVarImp.
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.
