
## 6.2 Adding Non-Strict Comparisons

The algorithm solve_constraints can be modified to deal with non-strict comparisons of the form od( a, b ) ≤ od( c, d ) by, intuitively, marking the edge ab as "short" on each iteration if the edge cd has been found to be short.

Specifically, in algorithm solve constraints, we make the following two anges. First, the revised algorithm takes two parameters: S, the set of strict constraints, and W, the set of non-strict constraints. Second, we replace the line H := the connected components of the shorts of S
with the following code:
1.

2.

3.

4.

s H := the shorts of S :
repeat H := the connected components of H ;
for each weak constraint od(a, b) ≪ od(c, d)
if cd is in H then add ab to H endif endfor until no change has been made to H in the last iteration The proof that the revised algorithm is correct is only a slight extension of the proof of theorem 1 and is given in the appendix.

Optimizing this algorithm for efficiency is a little involved, not only because of the new operations that must be included, but also because there are now four parameters - n, the nmber of symbols; e, the number of edges mentioned; s, the number of strict comparison; and w, the number of non-strict comparisons - and the optimal implementation varies depending on their relative sizes. In particular, either s or w, though not both, may be much smaller than n, and each of these cases requires special treatment for optimal efficiency.

The best implementation we have found for the case where both s and w are Ω( n ) has a running time of O(max( n 3 , nw, s )). The details of the implementation are straightforward and not of sufficient interest to be worth elaborating here.

An immediate consequence of this result is that a couple of problems of inference are esily computed:
- To determine whether a constraint C is the consequence of a set of constraints S i form the set S ∪¬C and check for consistency. If S ∪¬C is inconsistent then S¬C.

Note that the negation of the constraint od( a, b ) ≪ od( c, d ) is the constraint od(c, d) ≪ od(a, b).

- To determine whether two sets of constraints are logically equivalent, check that each constraint in the first is a consequence of the second, and vice versa.

## 6.3 Adding Order Constraints

Example 3 of Section 2 involves a combination of order-of-magnitude constraints on distances together with simple ordering on points, where the points lie on a one-dimensional line. We next show how to extend algorithm solve constraints to deal with this more com­ plex situation.