16.2.4 A Generate and Test Algorithm

In the graph metaphor, solving a dominance constraint means to configure its the nodes of the constraint graph into a tree, such that all required dominance relations hold.

There exists a simple but naive `generate and test' algorithm doing this. The idea is that for any two nodes and in the graph there exists only a 4 relative positions into which they can be configured in the final tree.

1. , they become equal

2. , strictly dominates

3. , strictly dominates

4. , is to the side of (i. e. none of the above).

We can thus decide the satisfiablity of a domiance constraint as follows: First guess one of the above relationsships for each two nodes in a graph. Then test, whether the graph satisfies all relationships required by the constraint and whether the graph augmented with the guessed relationships becomes tree-like. If one guess is consistent then the constraint graph is satisfiable, otherwise not.

Denys Duchier, Claire Gardent and Joachim Niehren
Version 1.2.4 (20020829)