<> <> <<>> DIRECTORY Rope, IO, FS, Imager, RatNums, EuclideanGraphs; EuclideanGraphsImpl: CEDAR PROGRAM IMPORTS IO, FS, RatNums EXPORTS EuclideanGraphs = BEGIN OPEN RN: RatNums, EuclideanGraphs; vertexIndex: PUBLIC CARDINAL; -- count of vertices allocated <<**************** Point and Edge Manipulation ****************>> MakePointFromRatNums: PUBLIC PROC[x1, y1: RN.RatNum] RETURNS [p: Point] = { <> p _ [x: x1, y: y1 ]; RETURN[ p ]; }; MakePointFromReals: PUBLIC PROC[x1, y1: REAL] RETURNS [p: Point] = { <> p _ [x: RN.RatNumFromREAL[x1], y: RN.RatNumFromREAL[y1] ]; RETURN[ p ]; }; ImagerVecFromPoint: PUBLIC PROC[p: Point] RETURNS [q: Imager.VEC] = { q _ [ RN.RatNumToREAL[p.x], RN.RatNumToREAL[p.y] ]; RETURN[ q ]; }; PointEqual: PUBLIC PROC[p, q: Point] RETURNS [BOOLEAN] = { <> RETURN[ RN.RatNumEqual[p.x, q.x] AND RN.RatNumEqual[ p.y, q.y ] ]; }; VerticalEdge: PUBLIC PROC[ p, q: Point ] RETURNS[BOOLEAN] = { <> RETURN[ RN.RatNumEqual[p.x, q.x] ]; }; DistanceSquare: PUBLIC PROC[ p, q: Point ] RETURNS [d: RN.RatNum] = { <> deltax, deltay: RN.RatNum; deltax _ RN.RatNumSubtract[ q.x, p.x]; deltay _ RN.RatNumSubtract[ q.y, p.y]; RETURN[ RN.RatNumAdd[ RN.RatNumMultiply[ deltax, deltax ], RN.RatNumMultiply[ deltay, deltay ] ] ] }; PointLineTest: PUBLIC PROC [start, end, test: Point] RETURNS[PointLineRelation _ ONLINE ] = { <> relation: RN.RatNumRelation; IF PointEqual[start, end] THEN ERROR; relation _ RN.RatNumCompare[ RN.RatNumMultiply[ RN.RatNumSubtract[ end.x , start.x ], RN.RatNumSubtract[ test.y , start.y] ], RN.RatNumMultiply[ RN.RatNumSubtract[ test.x , start.x ], RN.RatNumSubtract[ end.y , start.y ] ] ]; SELECT relation FROM ratLess => RETURN[ RIGHTOFLINE ]; ratEqual => RETURN[ ONLINE ]; ratGreater => RETURN[ LEFTOFLINE ]; ENDCASE; }; PointDirectedEdgeTest: PUBLIC PROC [start, end, test: Point] RETURNS[PointDirectedEdgeRelation _ LEFTOFEDGE] = { <<*** Perhaps instead of DistanceSquare, can use the test IF ( (ytest - p1.y) * (p2.y - ytest) > 0 ) AND ( (xtest - p1.x) * (p2.x - xtest) > 0 ) THEN between (assuming nonvertical and nonhorizontal points).>> pointLineRelation: PointLineRelation; firstbool, secondbool: BOOL; pointLineRelation _ PointLineTest[start, end, test]; SELECT pointLineRelation FROM LEFTOFLINE => RETURN[ LEFTOFEDGE ]; RIGHTOFLINE => RETURN[ RIGHTOFEDGE ]; ONLINE => { IF PointEqual[start, test] THEN RETURN[ EQUALSTART ]; IF PointEqual[end, test] THEN RETURN[ EQUALEND ]; firstbool _ RN.RatNumGreater[ DistanceSquare[start, end], DistanceSquare[start, test] ]; secondbool _ RN.RatNumGreater[ DistanceSquare[end, start], DistanceSquare[end, test] ]; IF firstbool AND secondbool THEN RETURN[BETWEENSTARTEND]; IF RN.RatNumGreater[ DistanceSquare[test, start], DistanceSquare[test, end] ] THEN RETURN[AFTEREND] ELSE RETURN[BEFORESTART]; }; ENDCASE; }; IntersectLines: PUBLIC PROC [start1, end1, start2, end2: Point] RETURNS [intersection: Point] = { slope1, slope2, intercept1, intercept2, xIntersect, yIntersect: RN.RatNum; vertical1: BOOL _ VerticalEdge[start1, end1]; vertical2: BOOL _ VerticalEdge[start2, end2]; IF vertical1 AND vertical2 THEN ERROR; IF NOT vertical1 THEN slope1 _ RN.RatNumDivide[ RN.RatNumSubtract[ end1.y, start1.y ], RN.RatNumSubtract[ end1.x, start1.x ] ]; IF NOT vertical2 THEN slope2 _ RN.RatNumDivide[ RN.RatNumSubtract[ end2.y, start2.y ], RN.RatNumSubtract[ end2.x, start2.x ] ]; IF NOT vertical1 THEN intercept1 _ RN.RatNumSubtract[ start1.y, RN.RatNumMultiply[ slope1, start1.x ] ]; IF NOT vertical2 THEN intercept2 _ RN.RatNumSubtract[ start2.y, RN.RatNumMultiply[ slope2, start2.x ] ]; IF NOT vertical1 AND NOT vertical2 THEN { -- neither edge vertical xIntersect _ RN.RatNumDivide[ RN.RatNumSubtract[intercept2, intercept1 ], RN.RatNumSubtract[slope1, slope2 ] ]; yIntersect _ RN.RatNumAdd[ intercept1, RN.RatNumMultiply[ slope1, xIntersect] ]; } ELSE IF vertical1 THEN { -- 1st edge is vertical, 2nd edge not vertical xIntersect _ start1.x; yIntersect _ RN.RatNumAdd[ intercept2, RN.RatNumMultiply[ slope2, xIntersect] ] } ELSE { -- IF vertical2, i.e. 1st edge not vertical, 2nd edge is vertical xIntersect _ start2.x; yIntersect _ RN.RatNumAdd[ intercept1, RN.RatNumMultiply[ slope1, xIntersect] ] }; intersection _ MakePointFromRatNums[xIntersect, yIntersect]; }; BiasedEdgeCompare: PUBLIC PROC [outerStart, outerEnd, innerStart, innerEnd: Vertex] RETURNS [outcome: BiasedEdgeCompareStatus _ Disjoint] = { firstRelation, secondRelation: PointDirectedEdgeRelation; intersection: Point; firstRelation _ PointDirectedEdgeTest[innerStart.coordinates, innerEnd.coordinates, outerEnd.coordinates]; SELECT firstRelation FROM BEFORESTART, AFTEREND, RIGHTOFEDGE => RETURN[Disjoint]; EQUALSTART => RETURN[OuterEndEqInnerStart]; BETWEENSTARTEND => RETURN[OuterEndInInner]; EQUALEND => RETURN[OuterEndEqInnerEnd]; LEFTOFEDGE => { intersection _ IntersectLines[outerStart.coordinates, outerEnd.coordinates, innerStart.coordinates, innerEnd.coordinates]; secondRelation _ PointDirectedEdgeTest[innerStart.coordinates, innerEnd.coordinates, intersection]; SELECT secondRelation FROM BEFORESTART, AFTEREND => RETURN[Disjoint]; EQUALSTART => RETURN[InnerStartInOuter]; BETWEENSTARTEND => RETURN[ProperIntersection]; EQUALEND => RETURN[InnerEndInOuter]; ENDCASE => ERROR; -- intersection must be on the line [innerStart, innerEnd]. }; ENDCASE; }; <<>> <<**************** Structure Manipulation ****************>> FindAdjacency: PUBLIC PROC[v, w: Vertex] RETURNS [vTow, wTov: Adjacency]= { << v and w are adjacent vertices. Search and find the Adjacencys with each points to the other.>> ahlv, ahlw: AdjacencyList; ahlv _ v.adjacentVertices; ahlw _ w.adjacentVertices; WHILE ahlv.first.vertex # w DO ahlv _ ahlv.rest; ENDLOOP; WHILE ahlw.first.vertex # v DO ahlw _ ahlw.rest; ENDLOOP; RETURN[ ahlv.first, ahlw.first ]; }; CountAdjacencies: PUBLIC PROC[v: Vertex] RETURNS [number: CARDINAL] ~ { adjacencies: AdjacencyList _ v.adjacentVertices; adjHead: AdjacencyList _ v.adjacentVertices; IF adjacencies = NIL THEN RETURN[0]; number _ 1; adjacencies _ adjacencies.rest; WHILE adjacencies # adjHead DO number _ number + 1; adjacencies _ adjacencies.rest; ENDLOOP; }; <> <> <> <> <> <> <> <> <> <> <> <> <> <<};>> <<>> AdjacentVertices: PUBLIC PROC[v: Vertex] RETURNS [vertices: LIST OF Vertex] ~ { adjacencies: AdjacencyList _ v.adjacentVertices; adjHead: AdjacencyList _ v.adjacentVertices; verticesLast: LIST OF Vertex; IF adjacencies = NIL THEN RETURN[NIL]; verticesLast _ vertices _ LIST[adjacencies.first.vertex]; adjacencies _ adjacencies.rest; WHILE adjacencies # adjHead DO verticesLast.rest _ LIST[adjacencies.first.vertex]; verticesLast _ verticesLast.rest; adjacencies_ adjacencies.rest; ENDLOOP; }; Adjacent: PUBLIC PROC[v, w: Vertex] RETURNS [BOOL] ~ { adjacencies: AdjacencyList _ v.adjacentVertices; adjHead: AdjacencyList _ v.adjacentVertices; IF adjacencies = NIL THEN RETURN[FALSE]; IF adjacencies.first.vertex = w THEN RETURN[TRUE]; adjacencies _ adjacencies.rest; WHILE adjacencies # adjHead DO IF adjacencies.first.vertex = w THEN RETURN[TRUE]; adjacencies_ adjacencies.rest; ENDLOOP; RETURN[FALSE]; }; SetFigureVisitedValues: PUBLIC PROC[v: Vertex, visitedValue: BOOLEAN] = { <> IF v = NIL THEN RETURN; -- no vertices IF v.adjacentVertices = NIL THEN { v.visited _ visitedValue; RETURN }; -- one vertex SetFigureVisitedValuesSubr[v, visitedValue ]; -- two or more vertices RETURN; }; SetFigureVisitedValuesSubr: PROC[v: Vertex, visitedValue: BOOLEAN] = { <> vAdjList: AdjacencyList _ v.adjacentVertices; nextAdjacency: Adjacency; lastVertex, nextVertex: Vertex; done: BOOL _ FALSE; v.visited _ visitedValue; -- record that have visited this vertex <> lastVertex _ vAdjList.first.vertex; vAdjList _ vAdjList.rest; -- shift past marker vertex (i.e. first iteration of loop begins after it) done _ FALSE; WHILE NOT done DO nextAdjacency _ vAdjList.first; nextVertex _ nextAdjacency.vertex; IF nextVertex = lastVertex THEN done _ TRUE; -- test for last vertex to be processed IF (nextVertex.visited # visitedValue) THEN SetFigureVisitedValuesSubr[ nextVertex, visitedValue]; -- Recursive call for w vAdjList _ vAdjList.rest; ENDLOOP; RETURN; }; FindVertexForPoint: PUBLIC PROC [v: EuclideanGraph, test: Point] RETURNS [w: Vertex] ~ { <> visitedValue: BOOL; currentDist: RN.RatNum; IF v = NIL OR v.adjacentVertices = NIL THEN RETURN[v] -- no vertices ELSE { visitedValue _ v.adjacentVertices.first.vertex.visited; currentDist _ DistanceSquare[v.coordinates, test]; [w, currentDist] _ FindVertexForPointSubr[v, NOT visitedValue, test, v, currentDist]; -- specify toggling of visitedValue RETURN[w]; }; }; FindVertexForPointSubr: PROC[v: Vertex, visitedValue: BOOL, test: Point, currentBest: Vertex, currentBestDist: RN.RatNum] RETURNS [best: Vertex, bestDist: RN.RatNum] = { vAdjList: AdjacencyList _ v.adjacentVertices; lastVertex, nextVertex: Vertex; vDist: RN.RatNum; done: BOOL; <> v.visited _ visitedValue; -- record that we've visited this vertex <> vDist _ DistanceSquare[v.coordinates, test]; IF RN.RatNumLess[ vDist, currentBestDist] THEN { currentBest _ v; currentBestDist _ vDist }; <> best _ currentBest; bestDist _ currentBestDist; lastVertex _ vAdjList.first.vertex; vAdjList _ vAdjList.rest; -- shift past marker vertex (i.e. first iteration of loop begins after it) done _ FALSE; WHILE NOT done DO nextVertex _ vAdjList.first.vertex; IF nextVertex = lastVertex THEN done _ TRUE; -- test for last vertex to be processed IF (nextVertex.visited # visitedValue) THEN [best, bestDist] _ FindVertexForPointSubr[ nextVertex, visitedValue, test, best, bestDist]; vAdjList _ vAdjList.rest; ENDLOOP; RETURN; }; <<>> <<>> <<**************** New Basic Ops ****************>> <<>> TestEdgeOverlap: PUBLIC PROC [root, testEnd: Vertex] RETURNS [overlap: BOOL, overlappedVertex: Vertex _ NIL] ~ { status: BracketingAdjacenciesRelation; priorPosition, followingPosition: AdjacencyList; [status, priorPosition, followingPosition] _ BracketingAdjacencies[root, testEnd.coordinates]; IF status = Overlaps THEN RETURN[TRUE, priorPosition.first.vertex] ELSE RETURN[FALSE, NIL]; }; CreateVertex: PUBLIC PROC [point: Point, vertexData: REF _ NIL, visitedValue: BOOL _ FALSE] RETURNS [newVertex: Vertex] ~ { <> newVertex _ NEW[VertexRec _ [coordinates: point, index: vertexIndex, adjacentVertices: NIL, data: vertexData, visited: visitedValue] ]; vertexIndex _ vertexIndex + 1; }; <<>> CreateEdge: PUBLIC PROC [endVertex: Vertex, edgeData: REF _ NIL, visitedValue: BOOL _ FALSE] RETURNS [newAdjacency: Adjacency] ~ { newAdjacency _ NEW[AdjacencyRec _ [vertex: endVertex, data: edgeData, visited: visitedValue] ]; }; <<>> AddEdge: PUBLIC PROC [root, adjacentVertex: Vertex, data: REF _ NIL, visitedValue: BOOL _ FALSE] ~ { status: BracketingAdjacenciesRelation; priorPosition, followingPosition, aList: AdjacencyList; adjacency: Adjacency _ CreateEdge[adjacentVertex, data, visitedValue]; IF root.adjacentVertices = NIL THEN { aList _ LIST[adjacency]; aList.rest _ aList; --- Make circular root.adjacentVertices _ aList; } ELSE { [status, priorPosition, followingPosition] _ BracketingAdjacencies[root, adjacentVertex.coordinates]; IF status = EqualRoot THEN ERROR; priorPosition.rest _ LIST[adjacency]; priorPosition.rest.rest _ followingPosition; root.adjacentVertices _ priorPosition; -- this statement needed, but why?? }; }; <<>> DeleteEdge: PUBLIC PROC [root, adjacentVertex: Vertex] = { l, l1: AdjacencyList; l1 _ root.adjacentVertices; l _ l1.rest; WHILE l.first.vertex # adjacentVertex DO l1 _ l; l _ l.rest; ENDLOOP; IF l=l1 THEN root.adjacentVertices _ NIL ELSE { l1.rest _ l.rest; root.adjacentVertices _ l1; }; }; InsertVertexInEdges: PUBLIC PROC [v, w: Vertex, p: Point, vertexData: REF _ NIL] RETURNS [newVertex: Vertex] ~ { vTow, wTov: Adjacency; z: Vertex _ CreateVertex[p, vertexData, v.visited]; [vTow, wTov] _ FindAdjacency[v, w]; AddEdge[z, w, vTow.data, vTow.visited]; DeleteEdge[v, w]; AddEdge[v, z, vTow.data, vTow.visited]; AddEdge[z, v, wTov.data, wTov.visited]; DeleteEdge[w, v]; AddEdge[w, z, wTov.data, wTov.visited]; RETURN[z]; }; SplitVertex: PUBLIC PROC [v, distinguishedAdjacentVertex: Vertex] RETURNS [newVertex: Vertex] ~ { vAdj, vAdjHead: AdjacencyList; fromV, toV: Adjacency; newVertex _ CreateVertex[v.coordinates]; vAdj _ vAdjHead _ v.adjacentVertices; vAdj _ vAdj.rest; vAdjHead.rest _ NIL; -- break circularity v.adjacentVertices _ NIL; -- reinitialize list of v's adjacencies to NIL WHILE vAdj # NIL DO fromV _ vAdj.first; IF fromV.vertex = distinguishedAdjacentVertex THEN AddEdge[v, distinguishedAdjacentVertex, fromV.data, fromV.visited] -- restore edge ELSE { w: Vertex _ fromV.vertex; ahlw: AdjacencyList _ w.adjacentVertices; WHILE ahlw.first.vertex # v DO ahlw _ ahlw.rest; ENDLOOP; toV _ ahlw.first; -- edge from w to v toV.vertex _ newVertex; -- now it's an edge from w to newVertex AddEdge[newVertex, w, fromV.data, fromV.visited]; }; vAdj _ vAdj.rest ENDLOOP; }; MergeVertices: PUBLIC PROC [u, v: Vertex] ~ { vAdj, vAdjHead: AdjacencyList; fromV, toV: Adjacency; w: Vertex; ahlw: AdjacencyList; <> vAdj _ vAdjHead _ v.adjacentVertices; IF vAdj=NIL THEN RETURN; -- do nothing if v has no adjacencies vAdj _ vAdj.rest; vAdjHead.rest _ NIL; -- break circularity v.adjacentVertices _ NIL; -- complete isolation of v (so it can be garbage collected) WHILE vAdj # NIL DO fromV _ vAdj.first; w _ fromV.vertex; ahlw _ w.adjacentVertices; WHILE ahlw.first.vertex # v DO ahlw _ ahlw.rest; ENDLOOP; toV _ ahlw.first; -- edge from w to v toV.vertex _ u; -- now it's an edge from w to u AddEdge[u, w, fromV.data, fromV.visited]; vAdj _ vAdj.rest ENDLOOP; }; <<>> DeleteVertex: PUBLIC PROC [v: Vertex] ~ { vAdj, vAdjHead: AdjacencyList; w: Vertex; <> vAdj _ vAdjHead _ v.adjacentVertices; vAdj _ vAdj.rest; vAdjHead.rest _ NIL; -- break circularity v.adjacentVertices _ NIL; -- complete isolation of v (so it can be garbage collected) WHILE vAdj # NIL DO w _ vAdj.first.vertex; DeleteEdge[w, v]; vAdj _ vAdj.rest ENDLOOP; }; <<>> SeparateVertices: PUBLIC PROC [v, w: Vertex] ~ { <> DeleteEdge[v, w]; DeleteEdge[w, v]; }; <<>> BracketingAdjacencies: PUBLIC PROC[root: Vertex, test: Point] RETURNS [status: BracketingAdjacenciesRelation, priorPosition, followingPosition: AdjacencyList] ~ { AngleType: TYPE = {Zero, Acute, Flat, Obtuse}; successiveAdjacencyAngle: AngleType; getAdjacencyAngle, testOnPriorLine: PointDirectedEdgeRelation; testToPrior, testToFollowing: PointLineRelation; numAdjacencies: CARDINAL _ CountAdjacencies[root]; priorPosition _ root.adjacentVertices; IF priorPosition = NIL THEN ERROR; -- error if we're called with a vertex with no adjacencies followingPosition _ priorPosition.rest; FOR I:CARDINAL IN [1..numAdjacencies] DO getAdjacencyAngle _ PointDirectedEdgeTest[priorPosition.first.vertex.coordinates, root.coordinates, followingPosition.first.vertex.coordinates]; SELECT getAdjacencyAngle FROM BEFORESTART, EQUALSTART, BETWEENSTARTEND => successiveAdjacencyAngle _ Zero; -- one adjacency, or overlapping adjacencies present AFTEREND => successiveAdjacencyAngle _ Flat; LEFTOFEDGE => successiveAdjacencyAngle _ Acute; RIGHTOFEDGE => successiveAdjacencyAngle _ Obtuse; ENDCASE => ERROR; -- EQUALEND => following vertex = root testToPrior _ PointLineTest[root.coordinates, priorPosition.first.vertex.coordinates, test]; testToFollowing _ PointLineTest[root.coordinates, followingPosition.first.vertex.coordinates, test]; SELECT testToPrior FROM ONLINE => { testOnPriorLine _ PointDirectedEdgeTest[root.coordinates, priorPosition.first.vertex.coordinates, test]; SELECT testOnPriorLine FROM EQUALSTART => RETURN[EqualRoot, NIL, NIL]; BEFORESTART => SELECT successiveAdjacencyAngle FROM Zero, Acute => NULL; Flat => NULL; -- we'll pick up overlap with following vertex in next loop iteration. Obtuse => RETURN[Interior, priorPosition, followingPosition]; ENDCASE; BETWEENSTARTEND, EQUALEND, AFTEREND => RETURN[Overlaps, priorPosition, followingPosition]; ENDCASE => ERROR; -- we're supposed to be ONLINE }; RIGHTOFLINE => SELECT successiveAdjacencyAngle FROM Zero => NULL; Acute => SELECT testToFollowing FROM LEFTOFLINE => RETURN[Interior, priorPosition, followingPosition]; RIGHTOFLINE => NULL; ONLINE => NULL; -- ignore overlap with following vertex until next iteration when it has become prior ENDCASE; Flat, Obtuse => RETURN[Interior, priorPosition, followingPosition]; ENDCASE; LEFTOFLINE => SELECT successiveAdjacencyAngle FROM Zero => NULL; Acute, Flat => NULL; Obtuse => SELECT testToFollowing FROM LEFTOFLINE => RETURN[Interior, priorPosition, followingPosition]; RIGHTOFLINE => NULL; ONLINE => NULL; -- ignore overlap with following vertex until next iteration when it has become prior ENDCASE; ENDCASE; ENDCASE; priorPosition _ followingPosition; followingPosition _ followingPosition.rest; ENDLOOP; RETURN[Interior, priorPosition, followingPosition]; -- this statement should be reached if and only if the only adjacencies of root are one or more edges, which all overlap each other, and which do not overlap [root, test]. }; <<>> <<**************** Input and Output ****************>> <<>> DumpGraph: PUBLIC PROC [v: EuclideanGraph, ropeFromEdgeData: RopeFromEdgeData, filename: Rope.ROPE, clientProc1, clientProc2: RopeFromRefProc _ NIL] ~ { <> visitedValue: BOOL; out: IO.STREAM _ FS.StreamOpen[filename, $create]; IF v = NIL THEN { out.Close[]; RETURN }; -- no vertices IF v.adjacentVertices = NIL THEN { -- one vertex out.PutF["\n%g: ", IO.int[v. index]]; out.PutF[" ( %g , %g ) []", IO.rope[RN.RatNumToRatRope[v.coordinates.x, FALSE, TRUE]], IO.rope[RN.RatNumToRatRope[v.coordinates.y, FALSE, TRUE]] ]; } ELSE { -- two or more vertices visitedValue _ v.adjacentVertices.first.vertex.visited; DumpGraphSubr[v, ropeFromEdgeData, NOT visitedValue, out, clientProc1, clientProc2]; -- specify toggling of visitedValue }; out.PutChar['\n]; out.PutChar['.]; out.Close[]; RETURN; }; DumpGraphSubr: PROC[v: EuclideanGraph, ropeFromEdgeData: RopeFromEdgeData, visitedValue: BOOL, out: IO.STREAM, clientProc1, clientProc2: RopeFromRefProc _ NIL] = { <> vAdjList: AdjacencyList _ v.adjacentVertices; lastVertex, nextVertex: Vertex; nextAdj: Adjacency; dataRope: Rope.ROPE; done: BOOL; <> v.visited _ visitedValue; -- record that we've visited this vertex <> out.PutF["\n%g: ", IO.int[v.index]]; out.PutF[" ( %g , %g ) [", IO.rope[RN.RatNumToRatRope[v.coordinates.x, FALSE, TRUE]], IO.rope[RN.RatNumToRatRope[v.coordinates.y, FALSE, TRUE]] ]; <> lastVertex _ vAdjList.first.vertex; vAdjList _ vAdjList.rest; -- shift past marker vertex (i.e. first iteration of loop begins after it) done _ FALSE; WHILE NOT done DO nextAdj _ vAdjList.first; nextVertex _ nextAdj.vertex; IF nextVertex = lastVertex THEN done _ TRUE; -- test for last vertex to be processed dataRope _ ropeFromEdgeData[nextAdj.data, clientProc1, clientProc2]; out.PutF[" ( %g , %g ) ", IO.int[nextVertex.index], IO.rope[dataRope] ]; vAdjList _ vAdjList.rest; ENDLOOP; out.PutChar[']]; <> lastVertex _ vAdjList.first.vertex; vAdjList _ vAdjList.rest; -- shift past marker vertex (i.e. first iteration of loop begins after it) done _ FALSE; WHILE NOT done DO nextVertex _ vAdjList.first.vertex; IF nextVertex = lastVertex THEN done _ TRUE; -- test for last vertex to be processed IF (nextVertex.visited # visitedValue) THEN DumpGraphSubr[ nextVertex, ropeFromEdgeData, visitedValue, out, clientProc1]; vAdjList _ vAdjList.rest; ENDLOOP; RETURN; }; ClientDataProc: IO.BreakProc = {RETURN[SELECT char FROM ' => sepr, ENDCASE => other]}; -- get blank delimited rope ReadIOGraphFromFile: PUBLIC PROC [filename: Rope.ROPE, edgeDataFromRope: EdgeDataFromRope, MessageStream: IO.STREAM, clientProc1, clientProc2: RefFromRopeProc _ NIL] RETURNS [iOGraph: IOGraph] ~ { done: BOOL _ FALSE; ratNumOK, doneAdj: BOOL; dataRope: Rope.ROPE; charsSkipped: INT; -- dummy to satisfy GetTokenRope parameter list dataRead: REF; indexRead, adjIndexRead: INT; xRead, yRead: RN.RatNum; ioAList: IOAdjacencyList; ioVHandle: IOVertex; iOAdjacency: IOAdjacency; puncChar: CHAR; in: IO.STREAM _ FS.StreamOpen[filename, $read]; iOGraph _ NIL; []_ in.SkipWhitespace[]; IF in.PeekChar[] = '. THEN done _ TRUE; WHILE NOT done DO indexRead _ in.GetInt[ ]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # ': THEN MessageStream.PutF["Colon expected"]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # '( THEN MessageStream.PutF["Left paren expected"]; [ xRead, ratNumOK] _ RN.ReadRatNum[ in]; IF NOT ratNumOK THEN MessageStream.PutF["Error reading x coordinate"]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # ', THEN MessageStream.PutF["Comma expected"]; [ yRead, ratNumOK] _ RN.ReadRatNum[ in]; IF NOT ratNumOK THEN MessageStream.PutF["Error reading y coordinate"]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # ') THEN MessageStream.PutF["Right paren expected"]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # '[ THEN MessageStream.PutF["Left square bracket expected"]; doneAdj _ FALSE; ioAList _ NIL; []_ in.SkipWhitespace[]; IF in.PeekChar[] = '] THEN doneAdj _ TRUE; WHILE NOT doneAdj DO []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # '( THEN MessageStream.PutF["Left paren expected"]; adjIndexRead _ in.GetInt[]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # ', THEN MessageStream.PutF["Comma expected"]; []_ in.SkipWhitespace[]; [dataRope, charsSkipped ] _ in.GetTokenRope[ClientDataProc]; dataRead _ edgeDataFromRope[dataRope, clientProc1, clientProc2]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # ') THEN MessageStream.PutF["Right paren expected"]; iOAdjacency _ NEW[IOAdjacencyRec _ [ vertex: adjIndexRead, data: dataRead, visited: FALSE ] ]; ioAList _ CONS[iOAdjacency , ioAList]; -- adjacencies in ioAList are in backwards (counterclockwise) order; will be put back in right order by GraphFromIOGraph. []_ in.SkipWhitespace[]; IF in.PeekChar[] = '] THEN doneAdj _ TRUE; ENDLOOP; [ ] _ in.GetChar[ ]; -- toss right square bracket ioVHandle _ NEW[ IOVertexRec _ [coordinates: MakePointFromRatNums[xRead, yRead], index: indexRead, adjacentVertices: ioAList ] ]; iOGraph _ CONS[ ioVHandle, iOGraph ]; []_ in.SkipWhitespace[]; IF in.PeekChar[] = '. THEN done _ TRUE; ENDLOOP; }; VertexVerifyIOGraph: PUBLIC PROC [filename: Rope.ROPE, MessageStream: IO.STREAM] RETURNS [maxVertexIndex: CARDINAL _ 0] ~ { VERTEXDATA: TYPE = { PRESENT, ADJACENCY, NOTPRESENT }; MAXFIGUREVERTICES: CARDINAL = 2000; -- maximum number of vertices in figure for verifier. done: BOOL _ FALSE; ratNumOK, doneAdj: BOOL; dataRope: Rope.ROPE; charsSkipped: INT; -- dummy to satisfy GetTokenRope parameter list indexRead, adjIndexRead: INT; xRead, yRead: RN.RatNum; puncChar: CHAR; in: IO.STREAM _ FS.StreamOpen[filename, $read]; vertices: ARRAY [1..MAXFIGUREVERTICES] OF VERTEXDATA _ ALL[ NOTPRESENT ]; I: INT; minVertexIndex: CARDINAL _ MAXFIGUREVERTICES; -- minimum vertex index seen []_ in.SkipWhitespace[]; IF in.PeekChar[] = '. THEN done _ TRUE; WHILE NOT done DO indexRead _ in.GetInt[ ]; vertices[ indexRead ] _ PRESENT; IF indexRead < minVertexIndex THEN minVertexIndex _ indexRead; IF indexRead > maxVertexIndex THEN maxVertexIndex _ indexRead; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # ': THEN MessageStream.PutF["Colon expected"]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # '( THEN MessageStream.PutF["Left paren expected"]; [ xRead, ratNumOK] _ RN.ReadRatNum[ in]; IF NOT ratNumOK THEN MessageStream.PutF["Error reading x coordinate"]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # ', THEN MessageStream.PutF["Comma expected"]; [ yRead, ratNumOK] _ RN.ReadRatNum[ in]; IF NOT ratNumOK THEN MessageStream.PutF["Error reading y coordinate"]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # ') THEN MessageStream.PutF["Right paren expected"]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # '[ THEN MessageStream.PutF["Left square bracket expected"]; doneAdj _ FALSE; []_ in.SkipWhitespace[]; IF in.PeekChar[] = '] THEN doneAdj _ TRUE; WHILE NOT doneAdj DO []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # '( THEN MessageStream.PutF["Left paren expected"]; adjIndexRead _ in.GetInt[]; IF adjIndexRead < minVertexIndex THEN minVertexIndex _ adjIndexRead; IF adjIndexRead > maxVertexIndex THEN maxVertexIndex _ adjIndexRead; IF vertices[ adjIndexRead ] = NOTPRESENT THEN vertices[ adjIndexRead ] _ ADJACENCY; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # ', THEN MessageStream.PutF["Comma expected"]; [dataRope, charsSkipped ] _ in.GetTokenRope[ClientDataProc]; []_ in.SkipWhitespace[]; puncChar _ in.GetChar[ ]; IF puncChar # ') THEN MessageStream.PutF["Right paren expected"]; []_ in.SkipWhitespace[]; IF in.PeekChar[] = '] THEN doneAdj _ TRUE; ENDLOOP; [ ] _ in.GetChar[ ]; -- toss right square bracket []_ in.SkipWhitespace[]; IF in.PeekChar[] = '. THEN done _ TRUE; ENDLOOP; MessageStream.PutF["\nMinimum vertex index read is %g", IO.int[ minVertexIndex] ]; MessageStream.PutF["\nMaximum vertex index read is %g", IO.int[ maxVertexIndex] ]; I _ minVertexIndex - 1; WHILE I < maxVertexIndex DO I _ I + 1; IF vertices[ I ] # PRESENT THEN { IF vertices[ I ] = ADJACENCY THEN MessageStream.PutF["\nVertex No. %g is only referred to in an adjacency", IO.int[ I] ] ELSE MessageStream.PutF["\nVertex No. %g is not present", IO.int[ I] ] }; ENDLOOP; }; SearchVertexList: PUBLIC PROC [list: VertexList, key: INT] RETURNS [Vertex] ~ { <> WHILE list # NIL DO IF list.first.index = key THEN RETURN [list.first ]; list _ list.rest; ENDLOOP; RETURN [NIL]; }; <<>> END.