<> <> <<>> DIRECTORY Rope, IO, RatNums USING [RatNum], Imager; EuclideanGraphs: CEDAR DEFINITIONS = BEGIN OPEN RN: RatNums; <> <<>> <<(1) A EuclideanGraph is assumed to be connected. Hence a client who wishes to work with potentially unconnected graphs must maintain a EuclideanGraph for each component.>> <<>> <<(2) Regions are not stored explicitly in the graph, but are implicitly determined by it (2/86 - unresolved whether a unique set of regions is determined by a graph; e.g. this may be equivalent to the (fallacious?) notion that a graph uniquely determines a subdivision).>> <<>> <<(3) (Client) data stored with (directed) edges can be thought of as being associated with the edge itself, or with the region (in some subdivision for which this is the graph) to the left of the edge. >> <<>> <<(4) This package does no manipulation of client data. It is up to the client to fill in the data fields of new vertices and edges.>> <<>> <<(5) Procedures for merging Euclidean graphs are left to the client, since although the geometrical semantics of such a merge is client-independent, the desired manipulation of client data probably varies from client to client. This interface does attempt to provide useful geometrical primitives from which merge operators can be constructed. >> <<>> <<(6) It is the client's responsibility to maintain vertexIndex. This interface will simply increment it by one each time a new vertex is allocated.>> EuclideanGraph: TYPE = Vertex; -- since EuclideanGraphs assumed connected, a pointer to any vertex is sufficient entree to the graph. Vertex: TYPE = REF VertexRec; VertexRec: TYPE = RECORD[ coordinates: Point, index: INTEGER, -- negative index intended for temp vertices, zero index for point at infinity adjacentVertices: AdjacencyList, -- circular list of adjacent vertices in clockwise order data: REF ANY _ NIL, visited: BOOL _ FALSE -- for searching ]; VertexList: TYPE = LIST OF Vertex; Adjacency: TYPE = REF AdjacencyRec; AdjacencyRec: TYPE = RECORD[ vertex: Vertex, data: REF ANY _ NIL, visited: BOOLEAN _ FALSE -- for searching ]; AdjacencyList: TYPE = LIST OF Adjacency; Point: TYPE = RECORD[ x , y : RN.RatNum ]; PointList: TYPE = LIST OF Point; vertexIndex: CARDINAL; -- count of vertices allocated <<**************** Point and Edge Manipulation ****************>> MakePointFromRatNums: PROC[x1, y1: RN.RatNum] RETURNS [p: Point]; <> <<>> MakePointFromReals: PROC[x1, y1: REAL] RETURNS [p: Point]; <> <<>> ImagerVecFromPoint: PROC[p: Point] RETURNS [q: Imager.VEC]; PointEqual: PROC[ p, q: Point ] RETURNS[BOOLEAN]; <> <<>> VerticalEdge: PROC[ p, q: Point ] RETURNS[BOOLEAN]; <> <<>> DistanceSquare: PROC[ p, q: Point ] RETURNS[d: RN.RatNum]; <> <<>> PointLineRelation: TYPE = {ONLINE, LEFTOFLINE, RIGHTOFLINE}; <<>> PointLineTest: PROC [start, end, test: Point] RETURNS[PointLineRelation]; <> <<>> PointDirectedEdgeRelation: TYPE = {BEFORESTART, EQUALSTART, BETWEENSTARTEND, EQUALEND, AFTEREND, LEFTOFEDGE, RIGHTOFEDGE}; PointDirectedEdgeTest: PROC [start, end, test: Point] RETURNS[PointDirectedEdgeRelation]; IntersectLines: PROC [start1, end1, start2, end2: Point] RETURNS [intersection: Point]; <> <<>> BiasedEdgeCompareStatus: TYPE = { OuterEndEqInnerStart, OuterEndInInner, OuterEndEqInnerEnd, InnerStartInOuter, ProperIntersection, InnerEndInOuter, Disjoint}; <<>> BiasedEdgeCompare: PROC [outerStart, outerEnd, innerStart, innerEnd: Vertex] RETURNS [outcome: BiasedEdgeCompareStatus]; <> <<>> <<**************** Structure Manipulation ****************>> <<>> FindAdjacency: PROC[v, w: Vertex] RETURNS [vTow, wTov: Adjacency]; CountAdjacencies: PROC[v: Vertex] RETURNS [number: CARDINAL]; <> AdjacentVertices: PROC[v: Vertex] RETURNS [vertices: LIST OF Vertex]; <> Adjacent: PROC[v, w: Vertex] RETURNS [BOOL]; <> SetFigureVisitedValues: PROC[v: Vertex, visitedValue: BOOLEAN]; <<>> FindVertexForPoint: PROC [v: Vertex, test: Point] RETURNS [w: Vertex]; <> <<>> <<>> <<**************** New Basic Ops ****************>> <<>> TestEdgeOverlap: PROC [root, testEnd: Vertex] RETURNS [overlap: BOOL, overlappedVertex: Vertex _ NIL]; <> <<>> CreateVertex: PROC [point: Point, vertexData: REF _ NIL, visitedValue: BOOL _ FALSE] RETURNS [newVertex: Vertex]; <> <<>> CreateEdge: PROC [endVertex: Vertex, edgeData: REF _ NIL, visitedValue: BOOL _ FALSE] RETURNS [newAdjacency: Adjacency]; <<>> AddEdge: PROC [root, adjacentVertex: Vertex, data: REF _ NIL, visitedValue: BOOL _ FALSE]; <> <<>> DeleteEdge: PROC [root, adjacentVertex: Vertex]; <<>> InsertVertexInEdges: PROC [v, w: Vertex, p: Point, vertexData: REF _ NIL] RETURNS [newVertex: Vertex]; <> <<>> SplitVertex: PROC [v, distinguishedAdjacentVertex: Vertex] RETURNS [newVertex: Vertex]; <> <<>> MergeVertices: PROC [u, v: Vertex]; <> <<>> DeleteVertex: PROC [v: Vertex]; <> <<>> SeparateVertices: PROC [v, w: Vertex]; <> <<>> SetEdgeData: PROC [vTow: Adjacency, newData: REF]; BracketingAdjacenciesRelation: TYPE = {Interior, Overlaps, EqualRoot}; BracketingAdjacencies: PROC[root: Vertex, test: Point] RETURNS [status: BracketingAdjacenciesRelation, priorPosition, followingPosition: AdjacencyList]; <> <<>> <<**************** Input and Output ****************>> <<>> RopeFromRefProc: TYPE ~ PROC[ref: REF] RETURNS [Rope.ROPE]; RefFromRopeProc: TYPE ~ PROC[rope: Rope.ROPE] RETURNS [REF]; <<>> RopeFromEdgeData: TYPE = PROC [edgeData: REF, clientProc1, clientProc2: RopeFromRefProc _ NIL] RETURNS [out: Rope.ROPE]; <> <> <<>> EdgeDataFromRope: TYPE = PROC [in: Rope.ROPE, clientProc1, clientProc2: RefFromRopeProc _ NIL] RETURNS [edgeData: REF]; <> <> <<>> RopeFromVertexData: TYPE = PROC [vertexData: REF, clientProc1, clientProc2: RopeFromRefProc _ NIL] RETURNS [Rope.ROPE]; <> <> <<>> VertexDataFromRope: TYPE = PROC [in: Rope.ROPE, clientProc1, clientProc2: RefFromRopeProc _ NIL] RETURNS [vertexData: REF]; <> <> <<>> DumpGraph: PROC [v: EuclideanGraph, ropeFromEdgeData: RopeFromEdgeData, filename: Rope.ROPE, clientProc1, clientProc2: RopeFromRefProc _ NIL]; <> <<>> IOGraph: TYPE = LIST OF IOVertex; IOVertex: TYPE = REF IOVertexRec; IOVertexRec: TYPE = RECORD[ coordinates: Point, index: INTEGER, adjacentVertices: IOAdjacencyList, -- circular list, vertices in clockwise order <> visited: BOOL _ FALSE -- for searching ]; IOAdjacency: TYPE = REF IOAdjacencyRec; IOAdjacencyRec: TYPE = RECORD[ vertex: INTEGER, -- use of INT here rather than Vertex distinguishes IO* structures data: REF ANY _ NIL, visited: BOOLEAN _ FALSE -- for searching ]; IOAdjacencyList: TYPE = LIST OF IOAdjacency; <<>> ReadIOGraphFromFile: PROC [filename: Rope.ROPE, edgeDataFromRope: EdgeDataFromRope, MessageStream: IO.STREAM, clientProc1, clientProc2: RefFromRopeProc _ NIL] RETURNS [iOGraph: IOGraph]; VertexVerifyIOGraph: PROC [filename: Rope.ROPE, MessageStream: IO.STREAM] RETURNS [ maxVertexIndex: CARDINAL]; <> <<>> SearchVertexList: PROC [list: VertexList, key: INT] RETURNS [Vertex]; <> <<>> END. <<>>