An efficient implementation of solve_constraints

We use the following data structures and subroutines:

- Each node
*N*of the cluster tree contains pointers to its parents and children; a field*N*.label, holding the integer label; a field*N*.symbols, holding the list of symbols in the leaves of*N*; and a field*N*.mfsets, holding a list of the connected components of the symbols in*N*. As described below, each connected component is implemented as an merge-find set (MFSET). - An edge
*E*in the graph over symbols contains its two endpoints, each of which is a symbol; a field*E*.shorts, a list of the constraints in which*E*appears as a short; and a field*E*.longs, a list of the constraints in which*E*appears as a long. - A constraint
*C*has two fields,*C*.short and*C*.long, both of them edges. It also has pointers into the lists*C*.short.shorts and*C*.long.longs, enabling*C*to be removed in constant time from the constraint lists associated with the individual edges. - We will use the disjoint-set forest implementation of MFSETs
(Cormen, Leiserson, and Rivest, 1990, p. 448) with
merging smaller sets
into larger and path-compression. Thus, each MFSET is a upward-pointing
tree of symbols, each node of the tree being a symbol. The tree as a whole
is represented by the symbol at the root.
A symbol
*A*has then the following fields:*A*.parent is a pointer to the parent in the MFSET tree.*A*.cluster_leaf is a pointer to the leaf in the cluster tree containing*A*.- If
*A*is the root of the MFSET then*A*.size holds the size of the MFSET. - If
*A*is the root of the MFSET, then*A*.symbols holds all the elements of the MFSET. - If
*A*is the root of the MFSET then*A*.leaf_ptr holds a pointer to the pointer to*A in N*.mfsets where*N*=*A*.cluster_leaf.

We can now describe the algorithm.

proceduresolve_constraints1(inS: a system of constraints of the form od(a,b) << od(c,d)).returneithera cluster treeTsatisfyingSifSis consistent;or falseifSis inconsistent.

variables:mis an integer;a,bare symbols;Cis a constraint inS;His an undirected graph;E,Fare edges;Pis an MFSET;N,Mare nodes ofT;0.

beginifScontains any constraint of the form, ``od(a,b) << od(c,c)''then return false; 1.H:= emptyset; 2.foreach constraintC in Swith shortEand longFdo3. addEandFtoH; 4. addCtoE.shorts and toF.longsendfor; 5.m:= the number of variables inS; 6. initializeTto contain the rootN; 7.N.symbols := the variables inS;8.

repeatforeach leafNofT, INITIALIZE_MFSETS(N); 9.foreach edgeE=ab in Hdo10.ifE.shorts is non-empty and FIND(a) <> FIND(b)then11. MERGE(FIND(a), FIND(b))endifendfor12.ifeveryedgeE=ab in Hsatisfies FIND(a) = FIND(b) 13.then return(false) endif14.foreach current leafNofTdo 15.ifN.mfsets has more than one elementthen16.foreach mfsetP in N.mfsetsdo17. construct nodeMas a new child ofN in T; 18.M.symbols:=P.symbols; 19.endforendifendfor20.foreach edgeE=ab in Hdo21.ifFIND(a) <> FIND(b)then22.foreach constraintC in E.longsdo23. deleteCfromS; 24. deleteCfromE.longs; 25. deleteCfromC.short.shortsendfor26. deleteEfromHendifendfor27.m:=m-1; 28.untilSis empty;29.

foreach leafNofT30.N.label := 0; 31.ifN.symbols has more than one symbol 32.thencreate a leaf ofNwith label 0for each symbol inN.symbols; 33.endifendforendsolve_constraints1.

procedureINITIALIZE_MFSETS(N: node)varA: symbol;N.mfsets := emptyset;forA in N.symbolsdoA.parent := null;A.cluster_leaf :=N;A.symbols := {A};A.size := 1;N.mfsets := cons(A,N.mfsets);A.leaf_ptr :=N.mfsets;endforendINITIALIZE_MFSETS.

procedureMERGE(inA,B: symbol)ifA.size >B.sizethenswap(A,B);A.parent :=B;B.size :=B.size +A.size;B.symbols :=B.symbolsunionA.symbols; UsingA.leaf_ptr, deleteAfromA.cluster_leaf.mfsets;endMERGE.

procedureFIND(inA: symbol)returnsymbol;varR: symbol;ifA.parent = nullthenreturnAelseR:= FIND(A.parent);A.parent :=R; /* Path compression */return(R)endFIND.

Let *n* be the number of symbols in *S*; let *e* be the number of
edges; and let *s* be the number of constraints. Note that
*n/2* <= *e* <= *n*(*n-1)/2* and that
*e/2* <= *s* <= *e*(*e-1)/2*.
The running time of solve_constraints1 can be computed as follows.
As each iteration of the main loop 8-28 splits at least one of
the connected components of *H*, there can be at most *n-1* iterations.
The MERGE-FIND operations in the **for** loop 9-11 take together time at
most *O(*max
*(n a(n), e))* where *a*(*n*) is the inverse Ackermann's
function. Each iteration of the inner **for** loop lines 16-18 creates
one node *M* of the tree. Therefore, there are only *O*(*n*) iterations
of this loop over the entire algorithm. Lines 14,
15 of the outer **for** loop require at most *n* iterations in each iteration
of the main loop.
The **for** loop 22-26 is executed exactly once in the course of
the entire execution of the algorithm for each constraint *C*, and hence
takes at most time *O*(*s*) over the entire algorithm. Steps 20-21 require
time *O(e)* in each iteration of the main loop.
It is easily verified
that the remaining operations in the algorithm take no more time than
these. Hence the overall running time is *O(*max
*(n ^{2}a(n)*,