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

-- To do: DeleteEdge, ContractEdge: can they be made to work also when the diagram falls apart?.

-- A (simple, orientable, two-dimensional) diagram is a topological 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 above 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.

I hope it is true that any undirected graph for which such orderings can be defined can be embedded in some two-dimensional manifold in such a way that the orderings are preserved, no edges intersect, every vertex is contractible to a point, and every face is isomorphic to a disk. And vice-versa.

I also hope that the necessary and sufficient condition for that manifold to be isomorphic to a sphere (or to the plane plus the infinity point) is that the diagram be conneted and that the Euler relation for the sphere be satisfied, namely v-e+f=2. In general, a diagram with c components and v-e+f=2c-2h can be embedded in some 2-D manifold consisting of c disjoint spheres with a total of h handles.

-- The data structure below can be used to represent each component. An edge e of the undirected graph is represented by two antiparallel directed edges, each corresponding to one sense of traversal of the undirected edge e. We say that the face f is to the left of the directed edge e iff the destination vertex of e is the origin of the edge following e in the ccw order as seen from f. The directed edges out of each vertex v are linked in a circular list, in ccw order as seen from v, by their vNext field. Similarly, the edges with same left face f are linked in ccw order as seen from f by their fNext fields. Anoter pointer (sym) links the record of every directed edge with the record for the same edge taken in the opposite sense. Following at most two of those pointers, one can compute VPrev[e] (the edge whose vNext is e), FPrev[e] (the one whose fNext is e).

-- For this module, a vertex is just a circular list of its outgoing edges, connected by their vNext fields in counterclockwise order. Similarly, a face is a circular list of the edges around it, pointing counterclockwise as seen from the face and linked in that order by their fNext fields.

-- A directed edge e also contains pointers to a record describing the origin vertex (orgVD) and to one describing the face at its left (leftFD). These records are client-defined and client-maintained, although this module contains some procedures that he may found helpful for that purpose. This module worries only about maintaining the edge structure of the diagram, i.e. the sym, vNext and fNext pointers; in particular, it neither assumes nor ensures that distinct vertices or faces point to distict data records, or that two edges with same origin (resp. left face)will have the same orgVD (resp. leftFD)

-- The dual of a diagram is obtained by exchanging vertices with faces, and reversing the ccw orderings. This is the same to say that the FNext[e] in the dual diagram will be the same as VPrev[e] in the original, the origin of e in the dual will be its left face, and so forth.

-- A diagram (or rather, a connected component of it) is referred to by giving a pointer to one of its edges. NIL represents a diagram with no edges; such a diagram will have only one vertex and one face, whose data records should be kept by the client in some way of his choice.

{RETURN [(e.vNext).sym]};

{RETURN [e.fNext]};

{RETURN [(e.sym).fNext]};

{RETURN [e.vNext]};

{RETURN [e.sym]};

{RETURN [(e.sym).orgVD]};

{RETURN [e.orgVD]};

{RETURN [e.leftFD]};

{RETURN [(e.sym).leftFD]};

-- Sets to v the client data for the origin of e, and of all edges with same origin. This operation takes time proportional to the degree of that vertex.

-- Sets to f the client data for the face at left of e, and of all edges with the same left face. This operation takes time proportional to the number of edges bounding that face.

-- The procedures below ("constructive" Euler operators) allow the client to build an arbitrary connected diagram with ne edges in ne+1 steps, without having to fiddle with the edge links.

-- These operators do not allocate new vertex or.

-- Each construction operator (except MakeSphere) adds a new edge to the diagram(s), while at the same time adding or deleting a vertex or face. They take two edge parameters a and b: the endpoints of the new edge will be Org[a] and Dest[b], and the adjacent faces will be LeftF[a] and RightF[b]. Those vertices and faces may be merged or split as a result of the operation. The edges a and b may be NIL only if the diagram has no edges. In that case the diagram will have a single vertex and single face, so the location of the new edge will be obvious.

-- Creates a new diagram containing only one vertex and one face.

-- The directed edges a and b should belong to the diagram Dab and should have the same left face f=LeftF[a]=LeftF[b].

-- This operator will add a new edge e (and its symmetrical) from Org[a] to Dest[b] across the face f. This will split the latter in two: RightF[e]=LeftF[a]=LeftF[b] and LeftF[e].

-- In particular, if Org[a]=Dest[b] the new edge will be a loop attached to the vertex, with LeftF[e] as its interior.

-- If a=b=NIL,

-- In either case, the FaceRec for RightF[e] will be brand new, whereas the FaceRec of LeftF[e] will that of f, with its pointers duly modified.

-- The ne and nf counts in Dab will be incremented by one each. The time taken by this operation is proportional to the number of edges of the new face RightF[e], that is, to the original ccw distance between a and b as seen from f.

-- The directed edges a and b should belong to the diagram Dab and should have the same origin u=Org[a]=Org[b].

-- If a#b, this operator will split the vertex u in two, so that the faces RightF[a] and RightF[b] become adjacent to a new edge e connecting them. After the operation we will have Org[a]=Org[e], Org[b]=Dest[e], RightF[e]=RightF[b], LeftF[e]=RightF[a].

-- If a=b, this operator will insert a new vertex w in the face RightF[a]=RightF[b], and run a new edge e from Org[a] to it. We will have then RightF[e]=RightF[b]=LeftF[e]=RightF[a].

-- In either case, the VertexRec for Dest[e] will be brand new, whereas the VertexRec of Org[e] will that of u, with its pointers duly modified.

-- The ne and nv counts in Dab will be incremented by one each. The time taken by this operation is proportional to the degree of the new vertex Dest[e], that is, to the original ccw distance between a and b as seen from u.

-- The next two operators will either add an handle (i.e., increase the genus) of a connected diagram, or join two separate components into a single diagram.

-- The directed edges a and b should belong respectively to the diagrams Da and Db (which may be the same), and should have different left faces fa=LeftF[a] and fb=LeftF[b].

-- This operator will replace the faces fa and fb by a single tube-like face, and then run along it a new edge e (and its symmetrical) from Dest[a] to Dest[b]. This will transform the tube into a single disk-like face LeftF[a]=LeftF[e]=LeftF[b]=RightF[e].

-- If Da#Db, one of the consequences will be to join the two diagrams into a single component. The ne, nf and nv counts of Db will be added to those of Da (and Db^ will be set to the empty diagram, to avoid confusion). If Da=Db, an handle will be added to the diagram Da=Db. In either case, the operation will finally set Da.ne ← Da.ne + 1, Da.nf ← Da.nf-1 and return Dab=Da.

-- The FaceRec for the consolidated face RightF[e]=LeftF[e]=... will be that of fa, with its pointers duly modified. The FaceRec of fb will be discarded. The time taken by this operation is proportional to the number of edges of the original face fb=LeftF[b].

-- The directed edges a and b should belong respectively to the diagrams Da and Db (which may be the same), and should have different origins ua=Org[a] and ub=Org[b].

-- This operator will attach to the vertices ua and ub two loops respectively interior to the faces RightF[a] and RightF[b]. Then it will join ua and ub in a single vertex, and identify the two loops as a new edge e incident to LeftF[a] and LeftF[b]. After the operation we will have Org[a]=Org[e]=Dest[e]=Org[b], LeftF[e]=LeftF[b], RightF[e]=LeftF[a].

-- If Da#Db, one of the consequences will be to join the two diagrams into a single component. The ne, nf and nv counts of Db will be added to those of Da (and Db^ will be set to the empty diagram, to avoid confusion). If Da=Db, an handle will be added to the diagram Da=Db. In either case, the operation will finally set Da.ne ← Da.ne + 1, Da.nv ← Da.nv-1 and return Dab=Da.

-- The VertexRec for the consolidated vertex Org[e]=Dest[e]=... will be that of ua, with its contents duly modified. The VertexRec of ub will be discarded. The time taken by this operation is proportional to the degree of the original vertex ub=Org[b].

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

-- The other two operators have inverses too, but they are not implemented yet due to some representation difficulties. For example, when computing the inverse of JoinAndConnectVertices, fixing the edge/vertex/face pointers is not much harder than a simple edge deletion; the hard part is detecting whether the diagram has been disconnected as a result of this operation, and building the descripors for each piece.

-- Deletes the directed edge e and its symmetrical, merging LeftF[e] and RightF[e] into a single face. Those two faces should be distinct. Will decrement De.ne and De.nf by one each.

-- The FaceRec for the consolidated edge will be that of LeftF[e], duly updated; that of RightF[e] will be lost. The time will be proportional to the number of edges in RightF[e].

-- Deletes the directed edge e and its symmetrical, merging Org[e] and Dest[e] into a single vertex. Those two vertices should be distinct. Will decrement De.ne and De.nv by one each.

-- The VertexRec for the consolidated edge will be that of Org[e], duly updated; that of Dest[e] will be lost. The time will be proportional to the number of edges in Dest[e].

{RETURN [Draw.Make
[DiagramPainter,
[data: diag, color: color, style: IF dual THEN 1 ELSE 0]]]};

-- Mekes a given Diagram into a Drawing object that will paint itself either in dual or in primal form, depending on the dual flag. The objData will be a REF to the DiagramRec

{RETURN [Draw.Make
[VertexAndFacePainter,
[data: v, color: color, style: IF dual THEN 1 ELSE 0]]]};

-- Makes an isolated Vertex (pointed to by the objData) into a Drawing object that will paint itself as a square with given side (in pixels) . If dual is TRUE, paints the corresponding dual face instead.

{RETURN [Draw.Make
[VertexAndFacePainter,
[data: f, color: color, style: IF dual THEN 0 ELSE 1]]]};

-- Makes an isolated Face (pointed to by the objData) into a Drawing object that will paint itself as a polygon of the given color. If dual is TRUE, paints the corresponding dual vertex instead, as square with the given side.

{RETURN [Draw.Make
[EdgePainter,
[data: diag, color: color, style: IF dual THEN 1 ELSE 0]]]};

-- Makes an isolated Delaunay edge (pointed to by the objData) into a Drawing object that will paint itself in dual or primal form, depending on the dual flag. The width is in pixels (0 or 1 gives the "thin" line of CedarGraphics).

-- This procedure will add to the menu of dr a new "Dual" entry that, when activated, modifies all Diagram, Edge, and Vertex objects of dr so that their duals will be shown in the instead. Clicking "Dual" will not affect other objects.