EuclideanGraphsImpl.mesa
Last Edited by: Arnon, June 20, 1985 4:37:28 pm PDT
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] = {
Bundle up two real numbers as an point
p ← [x: x1, y: y1 ];
RETURN[ p ];
};
MakePointFromReals: PUBLIC PROC[x1, y1: REAL] RETURNS [p: Point] = {
Bundle up two real numbers as an 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] = {
Test whether points p and q are the same.
RETURN[ RN.RatNumEqual[p.x, q.x] AND RN.RatNumEqual[ p.y, q.y ] ];
};
VerticalEdge: PUBLIC PROC[ p, q: Point ] RETURNS[BOOLEAN] = {
Test whether points p and q are the same.
RETURN[ RN.RatNumEqual[p.x, q.x] ];
};
DistanceSquare: PUBLIC PROC[ p, q: Point ] RETURNS [d: RN.RatNum] = {
Compute square of distance between two points.
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 ] = {
Determine the relation of the point test to the line [start, end].
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;
};
CountAdjacencies: PUBLIC PROC[v: Vertex] RETURNS [number: CARDINAL] ~ {
vAdjList: AdjacencyList ← v.adjacentVertices;
lastVertex: Vertex ← vAdjList.first.vertex;
nextVertex: Vertex;
done: BOOL ← FALSE;
IF vAdjList = NIL THEN RETURN[0];
number ← 0; vAdjList ← vAdjList.rest;
WHILE NOT done DO
nextVertex ← vAdjList.first.vertex;
IF nextVertex = lastVertex THEN done ← TRUE; -- test for last vertex to be processed
number ← number + 1;
vAdjList ← vAdjList.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] = {
Set visited field of all vertices in figure to visitedValue. Does Depth First Search. Flag fields (visited, intersectionPolygonEdge) left unchanged.
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] = {
Assumes two or more vertices
vAdjList: AdjacencyList ← v.adjacentVertices;
nextAdjacency: Adjacency;
lastVertex, nextVertex: Vertex;
done: BOOL ← FALSE;
v.visited ← visitedValue; -- record that have visited this vertex
Process adjacent vertices. Set all flag fields of edges to these vertices to visitedValue. Recursive call on the vertex if and only if we haven't been there yet.
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] ~ {
Find vertex closest to test point
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;
Record that we've visited v
v.visited ← visitedValue; -- record that we've visited this vertex
Compute distance to test point
vDist ← DistanceSquare[v.coordinates, test];
IF RN.RatNumLess[ vDist, currentBestDist] THEN {
currentBest ← v;
currentBestDist ← vDist
};
Recursive calls for adjacencies of v
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] ~ {
No adjacencies.
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;
Go through adjacencies between v and vertices w, changeing edge from w to point to u instead of v, and setting up a new edge from u to w.
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;
Set v's adjacency list to NIL, then go through adjacencies between v and vertices w, deleting edge from w to v.
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] ~ {
No error checks implemented.
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] ~ {
Dump a Vertex to a file. Does Depth First Search. Doesn't write vertex data.
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] = {
Assumes two or more vertices
vAdjList: AdjacencyList ← v.adjacentVertices;
lastVertex, nextVertex: Vertex;
nextAdj: Adjacency;
dataRope: Rope.ROPE;
done: BOOL;
Record that we've visited v
v.visited ← visitedValue; -- record that we've visited this vertex
Write v
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]] ];
Write adjacencies of v
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[']];
Recursive calls for adjacencies of v
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] ~ {
Search vertexList for the element whose index is key;
WHILE list # NIL DO
IF list.first.index = key THEN RETURN [list.first ];
list ← list.rest;
ENDLOOP;
RETURN [NIL];
};
END.