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 N_1 and N_2 in the graph there exists only a 4 relative positions into which they can be configured in the final tree.

  1. N_1 \gleich N_2, they become equal

  2. N_1 \domplus N_2, N_1 strictly dominates N_2

  3. N_2 \domplus N_1, N_2 strictly dominates N_1

  4. N_1 \bot N_2, N_1 is to the side of N_2 (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)