[ Please note: The project has been discontinued as of May 31, 2005 and is superseded by the projects of the ii Labs. There won't be further updates to these pages. ]

(Related publications: [PUBLink] [PUBLink] [PUBLink])

A variable of the CSP is represented by a vertex with the label Variable. It is graphically depicted by a circular vertex (see figure below).

Constraints could be represented by edges, but there are constraint types that allow a variable number of variables to be included. These constraint types will be called extensible constraints (C_e) in contrast to nonextensible constraints (C_n), such that C_e C_n = C. As the number of variables incorporated for extensible constraints may vary throughout the search, there must be a simple mechanism to include/exclude variables for constraints. Hence, a constraint is also represented by a vertex, new edges to variables being added in order to incorporate them. A constraint vertex's label corresponds to the type of the constraint. A constraint is graphically depicted by a rectangular vertex.

An SCSP allows the existence of so-called object constraints. These constraints do not restrict the variables' values, but provide structural context information. For example, for the job-shop scheduling example of the chapter's introduction, it must be known which two Start and Duration variables together form a SubTask object. Otherwise, a Machine constraint designed to check if the included SubTasks overlap might combine Start and Duration variables of different SubTasks for the check (see figure below). Object constraints act as a kind of structural broker between variables and conventional constraints. They are represented by a rectangular vertex with a dashed outline. Object constraints can be nonextensible as well as extensible, O_e O_n = O,   C O = Ø. Constraints of C can be connected to variables and object constraints, whereas object constraints can be connected to constraints of C as well.

Edges are used to connect vertex elements. The role/position of a variable (or constraint when speaking about objects) within a constraint is often very important. Thus, an edge's label and direction can be used to express its role/position. An edge's direction is indicated by an arrow and the label is displayed in the edge's middle (NoLabel if omitted).

For questions, comments or suggestions, please contact us.

Last update:
May 20, 2001 by Alexander Nareyek