Adding order constraints

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*).

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(inN: a node in a cluster tree;O: an om-space;d_{1}...d_{k}: orders of magnitude;in outG : array of points indexed on the nodes ofT)ifNis not a leafthenletC_{1}...C_{p}be the children ofNin topologically sorted order;x_{0}:=G[N];q:=N.label; pick pointsx_{1}...x_{p}in increasing order such that for alli,jin 0 ...p, ifi<>jthen od(x_{i},x_{j}) =d_{q}; /* Such points can be chosen by virtue of axiom A.8 */fori= 1 ...pdoG[C_{i}]:=x_{i}; instantiate1(C_{i},O,d_{1}...d_{k},G)endforendifendinstantiate1.

Algorithm solve_constraints is modified as follows:

proceduresolve_constraints2(inS: a system of constraints of the form od(a,b) << od(c,d) ; {NEW}O: a system of constraints of the forma<b)returneitheran ordered cluster treeTsatisfyingSifSis consistent;or falseifSis inconsistent.

variables:mis an integer;Cis a constraint inS;H,Iare undirected graphs;M,N,Pare nodes ofT;a,b,c,dare symbols;

beginifScontains any constraint of the form, ``od(a,b) << od(c,c)''then return false; {NEW}ifOis internally inconsistent (contains a cycle)then return false;m:= the number of variables inS; initializeTto consist of a single nodeN;N.symbols:= the variables inS;

repeatH:= the connected component of the shorts ofS; {NEW}H:= incorporate_order(H,O);ifHcontains all the edges inSthen return false

foreach leafNofTdoif notall vertices ofNare connected inHthenN.label :=m;foreach connected componentIofN.symbols inHdoconstruct nodeMas a new child ofN in T;M.symbols:= the vertices ofI;endforendif{NEW}foreach constrainta<b in O{NEW}ifais inM.symbols andbis inP.symbols {NEW} whereMandPare different children ofN{NEW}thenadd an ordering arc fromMtoP; {NEW}endif endforendfor

S:= the subset of constraints inSwhose long is inH;m:=m-1;untilSis empty;

foreach leafNofTN.label := 0;ifN.symbols has more than one symbolthencreate a leaf ofNfor each symbol inN.symbols; label each such leaf 0;endifendforendsolve_constraints2.

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{NEW}functionincorporate_order(inH: undirected graph;O: a system of constraints of the forma<b)returnundirected graph;

variables:G: directed graph;a,b: vertices inH;A,B: connected components ofH;V[A]:arrayof vertices ofGindexed on connected components ofH;I: subset of vertices ofG;

for eachconnected componentAofHcreate a vertexV[A]inG;for eachconstrainta<b in OletAandBbe the connected components ofHcontainingaandbrespectively;ifA<>Bthenadd an arc inGfromV[A]toV[B]endif endfor;for eachstrongly connected componentIofGdofor eachpair of distinct verticesV[A],V[B]inIdofor eacha in Aandb in Badd the edgeabtoHendfor endforendforendincorporate_order.

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*^{2}*a*(*n*), *ne*, *no*, *s*)), where *o* is the number of constraints
in *O*.