[Cyan]<PreISLCedar>Stolfi>COG>COGDiagram.mesa!1

-- COGDiagram.mesa: 2-D diagrams - data structure and primitives

-- last modified by Stolfi - October 15, 1982 2:00 pm

-- To do: SplitEdge and other handy operations defined in terms of MakeSphere and ConnectVertices.

-- To do: add Use: PROC[e: DEdge] RETURN [BOOL] parameter to Traverse and TopSort

-- To do: Let the client worry about maintaining edge numbers.

-- To do: add depthFirst: BOOL ← TRUE parameter to Traverse and TopSort

-- To do: add faces option to traverse?

-- To do: Check what happens to CloseFace for general edges ep, ef (not necessarily with same left face)

DIRECTORY;

COGDiagram: CEDAR DEFINITIONS =
BEGIN

-- PLANAR MAP DATA STRUCTURE - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

-- This interface allows the creation and manipulation of 2-D diagrams (i.e. undirected graphs embedded in orientable 2-D manifolds) and provides facilites to display them on a Drawing viewer.

-- A diagram is a combinatorial beast consisting of a set of vertices, a set of faces, and a set of edges, which are related by the incidence and ordering relationships described below:

1. every edge is incident to a pair of (eventually identical) vertices and to a pair of (eventually identical) faces;
2. every face is incident to at least one vertex, and every vertex to at least one face;
3. the edges incident to a given vertex v (or to a given face f) are cyclically ordered, in what will be called the "ccw order as seen from v (or from f)";
4. If the edges e1, e2 are incident to a common vertex v and are ccw consecutive as seen from v, then v, e1, and e2 are incident to a common face f, and e2, e1 (in that order) are ccw consecutive as seen from f; and the same is true if we exchange vertices with faces;

Note that if an edge is incident twice to the same vertex, it will appear twice in the ccw order around that vertex. A similar remark applies to faces.

If a vertex is incident to k edges, the faces incident to it can be arranged in a cyclical list (where each face appears one or more times) in such a way that the i-th edge is incident to the i-th and (i+1)th face in this list. The statement holds true also if we exchange vertices and faces.

-- A diagram is said to be connected if it has at least one vertex (or, equivalently, at least one face) and every vertex (resp. face) can be reached from any other by a chain of adjacent edges. In general, a diagram is the union of zero or more connected components.

-- Every edge in the diagram has four distinct "directions of traversal": two from vertex to vertex and two from face to face. These four directions are all distinct, even if the edge is a loop (identical endpoints) or a bridge (same face on both sides). An edge plus a specific direction of traversal is called a directed edge (DEdge).

-- To each directed edge e is associated an origin vertex, a destination vertex, a left face and a right face (Org[e], Dest[e], Left[e], Right[e]). These labels are assigned in such a way that e is crossed from origin to destination when going c.c.w. around its left face, and from the right face to the left face when going c.c.w. around its origin.

-- The functions LNext[e] and ONext[e] give the directed edge that follows e in the c.c.w. ordering around Left[e] and Org[e], respectively; the functions LPrev[e] and OPrev[e] are their inverses. The function Sym[e] gives the same undirected edge as e, but taken in the opposite direction (so that Org[e] = Dest[Sym[e]], Left[e] = Right[Sym[e]], etc.).

-- The dual of a diagram is obtained by exchanging vertices with faces, while preserving the c.c.w. orderings of both. To every directed edge e of the original diagram there corresponds an edge e' = Dual[e] in the dual, such that Org[e'] = Right[e], Right[e'] = Dest[e], Dest[e'] = Left[e], Left[e'] = Org[e]. The representation of diagrams is such that the dual is maintained in parallel with the original diagram at no extra cost, so that Dual[] is a constant-time operation.

-- The Dual[] operation is not quite "dual", since Dual[Dual[e]] is Sym[e] rather than e. For this reason, the inverse operation Prim[e] = Dual^3[e] = Sym[Dual[e]] is also provided.

-- A connected diagram with only one vertex, one face, and zero edges (topologically equivalent to a sphere) is represented by a single "dummy" edge e, with ONext[e] = LNext[e] = e (this condition holds only for dummy edges). Also, for a dummy directed edge (in case you are interested) we have also Org=Dest and Left=Right.

-- Every undirected edge (including dummy ones) is assigned a unique "serial number" No[e] when created, starting from zero. This number is used for debugging and traversing.

-- The edge representation is private to the implementation module, but vertices and faces are represented by client-defined data records.

DEdge: TYPE = RECORD
[rec: REF EdgeRec,
ix: INTEGER[0..4)]; -- one edge (or dual edge) taken in a specific direction

Vertex: TYPE = REF ANY; -- client-defined vertex data

Face: TYPE = REF ANY; -- client-defined face data

-- PRIMITIVES FOR TRAVERSING THE EDGE STRUCTURE - - - - - - - - - - - - - - - - - - - -

ONext: PROC [e: DEdge] RETURNS [ne: DEdge] = INLINE

-- Directed edge with same Org as e and following e ccw around Org[e].

{RETURN [ e.rec.next[e.ix] ]};

Dual: PROC [e: DEdge] RETURNS [ne: DEdge] = INLINE

-- Dual of the directed edge e, going from Right[e] to Left[e].

{RETURN [ [e.rec, (e.ix + 1) MOD 4] ]};

Sym: PROC [e: DEdge] RETURNS [ne: DEdge] = INLINE

-- Directed edge corresponding to e taken in opposite direction.

{RETURN [ [e.rec, (e.ix + 2) MOD 4] ]};

Prim: PROC [e: DEdge] RETURNS [ne: DEdge] = INLINE

-- Directed edge whose Dual is e.

{RETURN [ [e.rec, (e.ix + 3) MOD 4] ]};

LNext: PROC [e: DEdge] RETURNS [ne: DEdge];

-- Directed edge with same Left as e and following e c.c.w. around Left[e].

RNext: PROC [e: DEdge] RETURNS [ne: DEdge];

-- Directed edge with same Right as e and following e c.c.w. around Right[e].

DNext: PROC [e: DEdge] RETURNS [ne: DEdge];

-- Directed edge with same Dest as e and following e c.c.w. around Dest[e].

OPrev: PROC [e: DEdge] RETURNS [ne: DEdge];

-- Directed edge whose ONext is e.

LPrev: PROC [e: DEdge] RETURNS [ne: DEdge];

-- Directed edge whose LNext is e.

RPrev: PROC [e: DEdge] RETURNS [ne: DEdge];

-- Directed edge whose RNext is e.

DPrev: PROC [e: DEdge] RETURNS [ne: DEdge];

-- Directed edge whose DNext is e.

-- MISCELLANEOUS EDGE PRIMITIVES - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

IsDummy: PROC [e: DEdge] RETURNS [BOOL] = INLINE

-- TRUE if e is a dummy edge (a diagram with one face, one vertex, and no edges).

{RETURN [ONext[e] = e AND LNext[e] = e]};

No: PROC [e: DEdge] RETURNS [NAT] = INLINE

-- Serial creation number of the edge.

{RETURN [e.rec.no]};

-- PRIMITIVES FOR MAINTAINING VERTEX AND FACE DATA RECORDS - - - - - - - - - - - -

Org: PROC [e: DEdge] RETURNS [v: Vertex] = INLINE

-- Origin vertex of e.

{RETURN [e.rec.org[e.ix]]};

Dest: PROC [e: DEdge] RETURNS [v: Vertex] = INLINE

-- Destination vertex of e.

{RETURN [Org[Sym[e]]]};

Left: PROC [e: DEdge] RETURNS [f: Face] = INLINE

-- Face at left of e.

{RETURN [Org[Prim[e]]]};

Right: PROC [e: DEdge] RETURNS [f: Face] = INLINE

-- Face at right of e.

{RETURN [Org[Dual[e]]]};

-- The procedures below can be used to replace the vertex and face data records of an edge e. The client should worry about maintaining the consistency of those links, so that, for example, all edges with common origin have indeed the same Org[], and so forth. (The client should consider using SetOrg, SetLeft, etc., which guarantee this condition automatically)

-- Note that changing the Org, Dest, Left and Right fields does not afect in any way the structure of the diagram, which is defined exclusively by ONext, Dual, and its derivatives.

FixOrg: PROC [e: DEdge, v: Vertex] = INLINE

{e.rec.org [e.ix] ← v};

FixDest: PROC [e: DEdge, v: Vertex] = INLINE

{FixOrg [Sym[e], v]};

FixLeft: PROC [e: DEdge, f: Face] = INLINE

{FixOrg [Prim[e], f]};

FixRight: PROC [e: DEdge, f: Face] = INLINE

{FixOrg [Dual[e], f]};

-- The procedures below replace the origin (resp. destination, left face, right face) data record of an edge e, and also of all edges which can be reached from e by following the ONext (resp DNext, LNext, RNext) links. They take time proportional to the number of such edges.

-- Note that changing the Org, Dest, Left and Right fields does not afect in any way the structure of the diagram, which is defined exclusively by ONext, Dual, and its derivatives.

SetOrg: PROC [e: DEdge, v: Vertex];

SetLeft: PROC [e: DEdge, f: Face] = INLINE

{SetOrg[Prim[e], f]};

SetDest: PROC [e: DEdge, v: Vertex] = INLINE

{SetOrg[Sym[e], v]};

SetRight: PROC [e: DEdge, f: Face] = INLINE

{SetOrg[Dual[e], f]};

-- DIAGRAM CONSTRUCTION AND MANIPULATION - - - - - - - - - - - - - - - - - - - - - - -

-- The procedures in this section allow the client to build arbitrary diagrams, without having to fiddle with the edge links.

MakeSphere: PROC [v: Vertex, f: Face] RETURNS [dg: DEdge];

-- Creates a diagram with one vertex v, one face f and no real edges. The diagram will have a dummy edge dg, whose function is only to hold the vertex and face together.

MakeBridge: PROC [org, dest: Vertex, f: Face] RETURNS [dg: DEdge];

-- Creates a diagram with one face f and two distinct vertices, org and dest, connecterd by a single edge dg.

MakeLoop: PROC [v: Vertex, left, right: Face] RETURNS [dg: DEdge] = INLINE

-- Creates a diagram with one vertex v and two distinct faces, left and right, separated by a single edge dg.

{RETURN [Prim[MakeBridge[right, left, v]]]};

MergeOrSplitVertices: PROC [x, y: DEdge];

-- Will merge Org[x] and Org[y] in a single vertex if they are distinct, or will split them if they are the same. In the first case the edges y, ONext[y], ... will be inserted just before x; in the second case, after the split we will have y, ONext[y], ..., OPrev[x] in one vertex, and x, ONext[x], ..., OPrev[y] in the other.

-- x and y must be real, distinct edges. Will not fix the org links.

-- Applying MergeOrSplitVertices[x, y] twice will reproduce the original diagram.

-- The two procedures below allow the client to build an arbitrary connected diagram with ne edges in ne steps.

-- Each procedure adds a new edge to the diagram(s), while at the same time adding or deleting a vertex or face, and possibly adding an handle to the underlying manifold or joining two separate diagrams in a single connected component.

-- Each procedure takes two edge parameters a and b, which may be in the same or in distinct diagrams: depending on the operator, the new edge will connect Org[a] to Org[b], or Right[a] to Right[b]. Either (or both) a and b may be dummy.

-- The two operations are dual of each other: Dual[ConnectFaces [a, b]] is equivalent in effect and result to ConnectVertices[Dual[a], Dual[b]].

ConnectVertices: PROC [a, b: DEdge] RETURNS [e: DEdge];

-- This operator will add a new edge e (and its symmetrical), going from Org[a] to Org[b], in such a way as to make Left[e]=Left[b].

-- If a and b have the same left face, the latter will be split in two: Right[e] and Left[e] (=Left[b]). In particular, if a=b the new edge will be a loop (oriented clockwise) attached to Org[a], with Right[e] being the interior of the loop. If a#b, we will have Right[e]=Left[a] after the operation.

-- If a and b have different left faces fa and fb, the effect will be to replace those two faces with a single "tube", and run the new edge e lenghthwise across it. The tube will be split by e into a single disk-like face, so we will have Left[e]=Left[b]=Right[e]=Left[a]. In particular, if a and b are in two distinct diagrams, this operator will merge the two in a single connected component; otherwise, it will add an extra handle to the underlying manifold.

-- An interesting special case is when b is dummy, and a is not: the effect will be to add a new vertex interior to the face Left[a] and connected to Org[a] by the new edge e. The symmetrical case (a dummy, b normal) is analogous. If both a and b are dummy, the result will be a diagram with a single edge e, and either two vertices and one face (if a#b) or two faces and one vertex (if a=b).

-- In order to keep the run time for this operator constant, only the edge links (ONext, Dual, and its derivatives) are updated; the values of Left[x], for all directed edges x c.c.w. around the original faces Left[a] and Left[b], are not updated to reflect the splitting or merging of those faces. Therefore, the client should call SetLeft[e, f] or SetRight[e, f], as appropriate, after using this operator.

ConnectFaces: PROC [a, b: DEdge] RETURNS [e: DEdge] = INLINE

-- This operator will make the faces Right[a] and Right[b] adjacent across a new edge e (and its symmetrical), in such a way as to make Org[e]=Org[b], Left[e]=Right[b], Right[e]=Right[a].

-- If a and b have the same origin v, the latter will be split in two: Org[e] (=Org[b]) and Dest[e]. Out of Dest[e] will come all edges whose origin was v and were clockwise between a (inclusive) and b (exclusive) as seen from v. In particular, if a=b the destination of the new edge will be a vertex of degree one interior to Right[b]=Right[a]. If a#b, we will have Dest[e]=Org[a] after the operation.

-- If a and b have different origins va and vb, the effect will be to attach a counterclockwise loop to va interior to Right[a], attach a clockwise one to vb interior to Right[b], an then pull together the two vertices va and vb, identifying the two loops with the new edge e. In particular, if a and b are in two distinct diagrams, this operator will merge the two in a single connected component; otherwise, it will add an extra handle to the underlying manifold.

-- An interesting special case is when b is dummy, and a is not: the effect will be to add a new loop interior to the face Right[a] and oriented counterclockwise. The symmetrical case (a dummy, b normal) is analogous. If both a and b are dummy, the result will be a diagram with a single edge e, and either two vertices and one face (if a#b) or two faces and one vertex (if a=b).

-- In order to keep the run time for this operator constant, only the edge links (ONext, Dual, and its derivatives) are updated; the values of Org[x], for all directed edges x out of the original vertices Org[a] and Org[b], are not updated to reflect the splitting or merging of those vertices. Therefore, the client should call SetOrg[e, v] or SetDest[e, v], as appropriate, after using this operator.

{RETURN [Prim [ConnectVertices[Dual[a], Dual[b]]]]};

-- The procedures below are the inverse of the ConnectVertices and ConnectFaces; in ne steps, they will reduce an arbirtary component with ne+1 edges to an isolated sphere.

DeleteEdge: PROC [e: DEdge] RETURNS [a, b: DEdge];

-- Deletes the directed edge e (with its symmetrical and duals), merging Left[e] and Right[e] into a single face if they are distinct, and splitting them in two if they are the same.

-- In the second case, the split will occur at the two occurrences of e in the boundary of the face. As a consequence, the diagram may be broken in two disconnected pieces, or may just lose one of its handles.

-- The edge e may not be a dummy edge. If e is a loop, then either LNext[e] must be distinct from e, or e must be the only edge in the diagram.

-- If ConnectVertices [a, b] returns e, then applying DeleteEdge [e] to the resulting diagram returns [a, b] and results in a diagram isomorphic to the original one.

ContractEdge: PROC [e: DEdge] RETURNS [a, b: DEdge] = INLINE

-- Deletes the directed edge e and its symmetrical, merging Org[e] and Dest[e] into a single vertex if they are distinct, and splitting them if they are the same.

-- In the second case, the split will occur at the two occurrences of e in the ccw order around the vertex. As a consequence, the diagram may be broken in two disconnected pieces, or may just lose one of its handles.

-- The edge e may not be a dummy edge. If e is a bridge (an edge whose left and right faces are the same), then either ONext[e] must be distinct from e, or e must be the only edge in the diagram.

-- If ConnectFaces [a, b] returns e, then applying ContractEdge [e] to the resulting diagram returns [a, b] and results in a diagram isomorphic to the original one.

{[a, b] ← DeleteEdge[Dual[e]];
a ← Prim[a]; b ← Prim[b]};

-- The two procedures below are useful in building polyhedrons by adding faces one at a time. Suppose complf is the complement (exterior face) of the faces added so far, and let ef, ep be two edges (eventually the same) whith complf at their left. The sequence

-- FOR i IN [1..n] DO ep ← AddVertex [v[i], ep, left] ENDLOOP;

-- ep ← CloseFace [ep, ef, newf, left]

-- will cut out from complf a new face newf with new vertices v[1], v[2], ..., v[n], and sharing with the previous faces the path from ea up to (and including) eb.

EdgeSide: TYPE = {left, right};

AddVertex: PROC [v: Vertex, ep: DEdge, side: EdgeSide] RETURNS [e: DEdge];

-- If side = left, adds a new vertex v inside the face Left[ep], and connects Dest[ep] to it by means of a new edge e. Also sets Left[e] and Right[e] to Left[ep].

-- If side = right, does the same thing using Right[ep] instead of Left[ep].

CloseFace: PROC [ep, ef: DEdge, newFace: Face, side: EdgeSide] RETURNS [e: DEdge];

-- If side = left, connects Dest[ep] to Org[ef] across the face Left[ef] (which should be the same as Left[ep]), by means of a new edge e. Also setsthe face record Left[e] (and of all edges on Left[e] between ef and ep) to the newFace record, and sets and Right[e] to the original Left[ef].

-- If side = right, does the same thing using Right[ef] (which should be the same as Right[ep]) instead of Left[ef]. Also sets Right[e] to the newFace, instead of setting Left[e].

-- Neither of ep and ef should be dummy edges.

-- DIAGRAM TRAVERSAL - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

VisitProc: TYPE = PROC [e: DEdge, arg: REF ← NIL] RETURNS [res: REF ← NIL];

EdgeSet: TYPE = {all, oneWay, vertices};

Traverse: PROC [dg: DEdge, Visit: VisitProc, arg: REF ← NIL, choice: EdgeSet ← all]
RETURNS [res: REF ← NIL];

-- Traverses a diagram (given by one of its edges, dg) and performs arg ← Visit [e, arg] for every edge e in it. The final value of arg is returned as res.

-- If choice=all (default), Traverse will visit every directed edge once (i.e., every undirected edge twice, once in each orientation). If choice=oneWay, it will visit only one member in each pair e, Sym[e]. Finally, if choice=vertices, Traverse will visit exactly one edge out of each vertex.

-- If dg has a single dummy edge and choice is vertices, Visit will be called exactly once, with e=dg. Otherwise, Visit will not be called at all.

-- TOPOLOGICAL SORT OF VERTICES - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

EdgePredicate: TYPE = PROC [e: DEdge] RETURNS [BOOL];

TopSort: PROC
[dg: DEdge, Visit: VisitProc, arg: REF ← NIL, Ordered: EdgePredicate, clockWise: BOOL ← FALSE]
RETURNS [res: REF ← NIL];

-- Enumerates the vertices of the diagram in an order compatible with a partial order specified by a subset of the directed edges.

-- The predicate Ordered should be true for a directed edge e iff Org[e] is to precede Dest[e] in the output ordering. (It is O.K. if Ordered[e] and Ordered[Sym[e]] are both FALSE, but they should not be both TRUE, or an error will result).

-- The statement arg ← Visit[e, arg] is performed for exactly one edge e out of each vertex, in the final order. The final value of arg is returned in res. If dg has a single dummy edge, Visit will be called exactly once, with e=dg.

-- If the relative ordering of two vertices is not specified by the Ordered predicate or its transitive closure, normally the first of them to be visited will be the one whose "reference count" most recently became zero. If both vertices are "sources" (i.e., both had zero reference counts to begin with), they will be visited in arbitrary order.

-- When a vertex v is visited, it is either because it was a source in the first place, or because the reference count of v dropped to zero when TopSort visited some neighbor u of v. In this second case, after visiting v, the reference counts of its neighbors will be decremented in ccw order, starting at u. (the direction of scan can be reversed by setting clockWise to TRUE).

-- On the other hand, if v is a source, the starting point for the neighbor scan will be somewhat arbitrary. However, if dg is an edge out of v, then the scan will begin at that edge.

-- If Org[dg] and Dest[dg] are the only source and sink in the diagram, and the genus of the latter is zero, it turns out that ties will be disambiguated by their counterclockwise order as seen from Dest[dg] (given the above conditions, this counterclockwise ordering can be unambiguously defined for all vertices, even if they are not neighbors of Dest[dg]).

-- For example, if the diagram is embedded in the plane in such a way that all vertices are above the edge dg, and Ordered[e] is true iff e points strictly to the right, then in case of a tie the vertex with highest y coordinate (or lowest, of clockWise=TRUE) will be output first.

-- DEBUGGING - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

PutE: PROC [e: DEdge];

-- Prints out (in the debugging viewer) the edge number as "n:x ", where n is the .no field of e.rec, and x is the index of the specific quarter edge.

PutORing: PROC [e: DEdge];

-- Prints out all edges in the ONext ring of e. Prints a "#" between any two consecutive edges with different Org pointers.

PutLRing: PROC [e: DEdge];

-- Prints out all edges in the LNext ring of e. Prints a "#" between any two consecutive edges with different Left pointers.

PutDRing: PROC [e: DEdge];

-- Prints out all edges in the ONext ring of e. Prints a "#" between any two consecutive edges with different Dest pointers.

PutRRing: PROC [e: DEdge];

-- Prints out all edges in the LNext ring of e. Prints a "#" between any two consecutive edges with different Right pointers.

PutDiagram: PROC [e: DEdge];

-- Prints out (using PutORing) all vertex rings in the diagram e.

-- EDGE REPRESENTATION - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

-- FOR DARING EYES ONLY --

-- An undirected edge e is represented by four "quarter edges", each corresponding to one sense of traversal of e. These quarter edges are stored in a single record, so a DEdge is a pair [REF to edge record, index to a specific quarter]. We have therefore Dual[ [rec, ix] ] = [rec, (ix+1) mod 4], Sym[ [rec, ix] ] = [rec, (ix+2) mod 4], and so forth.

EdgeRec: TYPE = RECORD -- One half of an undirected edge
[org: ARRAY [0..4) OF REF ANY, -- Org[e] is e.rec.org[e.ix]
next: ARRAY [0..4) OF DEdge, -- directed edge following e in ccw order around Org[e]
no: EdgeNo -- edge serial number (for debugging & traversal)
];

EdgeNo: TYPE = NAT;

EdgeCount: READONLY EdgeNo; -- number of EdgeRecs allocated so far

END.