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 complex situation.

In terms of the axiomatics, adding an ordering on points involves positing that the relation p < q is a total ordering and that the ordering of points is related to order of magnitude comparisons of distances through the following axiom.

A.9

For points a,b,c in P, if a < b < c then od(a,b) <<= od(a,c).

The following rule is easily deduced: If C and D are disjoint clusters, then either every point in C is less than all the points in D, or vice versa.

In extending our algorithm, we begin by defining an ordered cluster tree to be a cluster tree where, for every internal node N, there is a partial order on the children of N. If A and B are children of N and A is ordered before B, then in an instantiation of the tree, every leaf of A must precede every leaf of B. Procedure instantiate1 can then be modified to deal with ordered cluster trees as follows:

instantiate1(in N : a node in a cluster tree; O : an om-space; 
                         d1 ... dk : orders of magnitude; 
 	     in out G : array of points indexed on the nodes of T)
if N is not a leaf then
     let C1 ... Cp be the children of N in topologically sorted order; 
     x0 := G[N]; 
     q := N.label;
     pick points x1 ... xp in increasing order such that 
          for all i,j in 0 ... p, if i <> j then od(xi, xj) = dq; 
	  /* Such points can be chosen by virtue of axiom A.8 */ 
     for i = 1 ... p do 
	  G[Ci] := xi;
          instantiate1(Ci, O, d1 ... dk, G) 
     endfor 
endif end instantiate1.

Algorithm solve_constraints is modified as follows:

procedure solve_constraints2(
                   in S: a system of constraints of the form od(a,b) << od(c,d) ; 
{NEW}                 O : a system of constraints of the form a < b) 
                   return either an ordered cluster tree T satisfying S 
                                             if S is consistent; 
		          or false if S is inconsistent. 

variables: m is an integer; 
  	   C is a constraint in S; 
	   H,I are undirected graphs; 
	   M,N,P are nodes of T; 
	   a,b,c,d are symbols; 

begin if S contains any constraint of the form, ``od(a,b) << od(c,c)''
	then return false; 
{NEW}if O is internally inconsistent (contains a cycle) then return false; 
     m := the number of variables in S; 
     initialize T to consist of a single node N; 
     N.symbols:= the variables in S;

     repeat H := the connected component of the shorts of S; 
{NEW}	    H := incorporate_order(H, O); 
	    if H contains all the edges in S then return false

	    for each leaf N of T do
	        if not all vertices of N are connected in H then
 		       N.label := m;
	 	       for each connected component I of N.symbols in H do 
		           construct node M as a new child of N in T;
			   M.symbols:= the vertices of I;
		       endfor endif 
{NEW}		for each constraint a < b in O 
{NEW}       	       if a is in M.symbols and b is in P.symbols 
{NEW} 		              where M and P are different children of N 
{NEW}	 		 then add an ordering arc from M to P; 
{NEW}	 	       endif endfor 
 	    endfor

	    S := the subset of constraints in S whose long is in H;
	    m := m-1;
	    until S is empty;

     for each leaf N of T 
	    N.label := 0; 
 	    if N.symbols has more than one symbol 
   	        then create a leaf of N for each symbol in N.symbols;
                     label each such leaf 0;
	        endif endfor 
end solve_constraints2.

{NEW} 
function incorporate_order(in H : undirected graph; 
	  	              O : a system of constraints of the form a < b) 
		           return undirected graph;

variables: G : directed graph;
	   a,b : vertices in H; 
	   A,B : connected components of H; 
	   V[A] : array of vertices of G indexed on connected components of H;
	   I : subset of vertices of G; 

for each connected component A of H create a vertex V[A] in G; 
for each constraint a < b in O 
        let A and B be the connected components of H containing a and b respectively; 
	if A <> B then add an arc in G from V[A] to V[B] endif endfor; 
for each strongly connected component I of G do 
	for each pair of distinct vertices V[A], V[B] in I do
	        for each a in A and b in B add the edge ab to H endfor endfor 
endfor 
end incorporate_order.

Function incorporate_order serves the following purpose. Suppose that we are in the midst of the main loop of solve_constraints2, we have a partially constructed cluster tree, and we are currently working on finding the sub-clusters of a node N. As in the original form of solve_constraints, we find the connected components of the shorts of the order-of-magnitude constraints. Let these be C₁ ... C_q; then we know that the diameter of each C_i is much smaller than the diameter of N. Now, suppose, for example, that we have in O the constraints a₁ < a₅, b₅ < b₂, c₂ < c₁, where a₁, c₁ in C₁; b₂, c₂ in C₂; and a₅, b₅ in C₅. Then it follows from axiom A.9 that C₁, C₂, and C₅ must all be merged into a single cluster, whose diameter will be less than the diameter of N. Procedure incorporate_order finds all such loops by constructing a graph G whose vertices are the connected components of H and whose arcs are the ordering relations in O and then computing the strongly connected components of G. (Recall that two vertices u,v in a directed graph are in the same strongly connected component if there is a cycle from u to v to u.) It then merges together all of the connected components of H that lie in a single strongly connected component of G.

The proof of the correctness of algorithm solve_constraints2 is again analogous in structure to the proof of theorem 1, and is given in the appendix.

By implementing this in the manner of section 6.1, the algorithm can be made to run in time O(max (n²a(n), ne, no, s)), where o is the number of constraints in O.