Constraints are a common approach to solve layout problems. In this section, we will give an overview of their application in the DesignComposer.

In DCL, constraints are defined like functions, and are referenced by design patterns. When a design command (and thus a design pattern) is executed, a container object is created which serves as scope for all constraints referred by the pattern. Thus each object inserted into such a container has to meet all constraints of the pattern which has produced the container.

Since the result's structure is typically a hierarchy of encapsulated containers, the related constraint web is hierarchical as well. This is quite useful for many formatting problems: a layout structure typically follows some kind of an hierarchy (document - chapter - line - word), which is now reflected by the constraint web. Another advantage of the hierarchical web is a more efficient constraint evaluation, since local problems do not necessarily affect the whole constraint web.

To improve the organization of constraints within the DesignComposer, constraints may be parameterized. The idea is to add parameters to a constraint, which may modify its behavior. This enables the declaration of constraint classes, what results in smaller and easier to maintain knowledge bases. An instance of such a class is the spacing constraint. Spacing may be done by a simple topological constraint. But typically, spacing depends on the current context, and therefore it is not unique for all objects in a given document. Therefore one has to specify an individual spacing constraint for each context - or a single constraint class with a spacing parameter.

Beside these aspects, which are shared by all constraints in the DesignComposer, different types of constraints are used for maximum efficiency; the currently implemented types are discussed below.

Validation and assignment constraints (VA Constraints) enable the validation of the current result and the assignment of new locations to layout objects. For instance, a VA constraint may be used to express the following requirement.

VA constraints are realized as binary, Boolean constraints. Their foundation is the Single Value Solver (SiVaS, [Maass92]) for placement problems: objects containing constraint variables are connected by connectors, which are used for constraint propagation. Constraint variables are bounds of the maximum coordinates covered by the object.

Compared to SiVaS' constraint model, the DesignComposer's layout constraints are similar to dynamic constraints: they are always defined for dynamic object sets. The idea of aggregating constraints has been replaced by the hierarchical constraint scope structure represented by the container model. The following example demonstrates how this works.

One could solve this task using an aggregated layout constraint, which creates a complex network between each related object. But it could be done more elegantly using the implicit hierarchy hidden in the task. If it is splited up into two subtasks like

one may specify for each subtask a design command with own layout constraints. The advantages are obviously: the constraint network is typically smaller (fewer edges), and the representation is nearer to the original tasks semantic.

An example how to define and to use a layout constraint can be found here.

Post-Processing Constraints

Layout constraints maybe marked as post-processing constraints. Constraints marked this way are not evaluated during main layout generation; this is done when a solution has been generated in a post-processing step. If the evaluation fails, the constraint is ignored. So you have the following properties for post-processing constraints:

• Since they do not affect the search process, their impact on the overall layout generation time is low: they are cheap in a certain way.
• They may (and must currently) be used for conditions which are allowed to be relaxed.

These properties qualify this kind of constraint to be a good means for beautifying or optimizing a layout.

Ordering Constraints

To enable the generation of a layout compatible to HTML, so-called ordering constraints are used. These constraints provide in the first place non-overlapping, but also often a simple kind of alignment. When a new constraint is specified, a user may mark it as ordering constraint.

Note that in a constraint set, at least one ordering constraint should be included. If multiple ordering constraints are specified, all of them will be evaluated.

Common VA Constraints

The following constraints are included in the DesignComposer demonstration package and are often referred by our examples:

• hOrdering: objects are aligned horizontally (ordering constraint)
• vOrdering: objects are aligned vertically (ordering constraint)
• hSpacing: objects are aligned horizontally with a fixed spacing (ordering constraint)
• vSpacing: objects are aligned vertically with a fixed spacing (ordering constraint)
• hCenter: objects are horizontally centered (post-processing constraint)
• vCenter: objects are vertically centered (post-processing constraint)
• hBlockSetting: objects are aligned horizontally justified (post-processing constraint)
• vBlockSetting: objects are aligned vertically justified (post-processing constraint)

To modify an object's appearance depending on its current context, one may use format constraints. A typical task would be:

What is called here informally an object's appearance is defined by the design pattern which has been chosen to create the object, and the object's format attributes (such as its color). To perform our sample task, the choice of the design pattern has to be modified.

Format constraints are evaluated before the pattern selection is done, which is a part of a design command's execution. Format constraints are implemented similar to the propagator constraints known from YPPS: they are binary and do modify a finite domain set to realize some kind of forward checking. Typical domain sets are the set of possible design patterns or font styles. Advantages of this kind of constraint are:

• The increasing restriction of the domain sets speeds up the whole layout generation.
• Since a format constraint is processed only once during pattern selection and not for value propagation during search, it is fast compared to common layout constraints, which have to be checked each time when a descendant object is changing.

A simple example how to define and to use a format constraint can be found here.