16.3.1 Sets of Nodes

Suppose, we are given a dominance constraint and one of its solutions. With each node of the constraint graph N (i.e. each of its variables), we associate 4 mutually exclusive 4 finite sets of nodes:

1. N.eq, the set of graph nodes of whose interpretation is equal N,

2. N.up, the set of graph nodes whose interpretations are strictly above N,

3. N.down, the set of graph nodes whose interpretations are strictly below N,

4. N.side, the set of graph nodes whose interpretations are to the side of N.

The whole idea of our approach resides here: we encode a dominance constraints into set constraints such that each node in the constraint graph is modelled by the 4 set variables that we constrain to the sets above (in each solution).

The first constraint we require is the following: For all nodes N, the 4 sets for N are disjoint and form a partition of the set V of all nodes of the constraint graph: