RouteDiGraphImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Last Edited by: Preas, July 17, 1985 11:44:46 am PDT
run IOConvertImpl ListImpl RopeImpl TerminalIOPackage RouteDiGraphImpl
DIRECTORY
Convert,
List,
Rope,
RouteDiGraph,
TerminalIO;
RouteDiGraphImpl: CEDAR PROGRAM
IMPORTS Convert, List, Rope, RouteDiGraph, TerminalIO
EXPORTS RouteDiGraph =
BEGIN
Common Types
types
Errors
Error: PUBLIC SIGNAL [errorType: RouteDiGraph.ErrorType ← callingError, explanation: Rope.ROPE ← NIL] = CODE;
Graph
CreateGraph: PUBLIC PROC [graphInfo: REF ANY ← NIL] RETURNS [graph: RouteDiGraph.Graph] =
Create a directed Graph.
BEGIN
graph ← NEW[RouteDiGraph.GraphRec ← [graphInfo: graphInfo]];
END;
DestroyGraph: PUBLIC PROC [graph: RouteDiGraph.Graph, enumGraph: RouteDiGraph.EnumGraphProc, enumNode: RouteDiGraph.EnumNodeProc, enumArc: RouteDiGraph.EnumArcProc] =
There may be circular references. enumGraph, enumNode and enumArc allow client to NIL any circular references in graphInfo, nodeInfo and arcInfo if necessary
BEGIN
UnlinkNode: RouteDiGraph.EnumNodeProc =
{DeleteArcs: RouteDiGraph.EnumArcsFromNodeProc =
{RemoveArc[graph, arc]};
graph.nodeList ← List.Remove[node, graph.nodeList];
[] ← RouteDiGraph.EnumArcsFromNode[graph, node, both, DeleteArcs];
};
first do the client data
[] ← EnumNodes[graph, enumNode];
[] ← EnumArcs[graph, enumArc];
[] ← enumGraph[graph];
next unlink the arcs from the nodes
[] ← EnumNodes[graph, UnlinkNode];
END;
Nodes
CreateNode: PUBLIC PROC [nodeInfo: REF ANY ← NIL, superiorArcs, inferiorArcs: RouteDiGraph.ArcList ← NIL] RETURNS [node: RouteDiGraph.Node] =
BEGIN
node ← NEW[RouteDiGraph.NodeRec ← [nodeInfo: nodeInfo, superiorArcs: superiorArcs, inferiorArcs: inferiorArcs]];
END;
RemoveNode: PUBLIC PROC [graph: RouteDiGraph.Graph, node: RouteDiGraph.Node] RETURNS [removedArcs: RouteDiGraph.ArcList] =
BEGIN
DeleteArcs: RouteDiGraph.EnumArcsFromNodeProc =
{RemoveArc[graph, arc]};
IF graph # NIL THEN
{graph.nodeList ← List.Remove[node, graph.nodeList];
removedArcs ← List.Append[node.superiorArcs, node.inferiorArcs];
[] ← RouteDiGraph.EnumArcsFromNode[graph, node, both, DeleteArcs]};
END;
IncludeNode: PUBLIC PROC [graph: RouteDiGraph.Graph, node: RouteDiGraph.Node] =
BEGIN
AddArcs: RouteDiGraph.EnumArcsFromNodeProc =
{IncludeArc[graph, arc]; RETURN[FALSE]};
IF graph # NIL THEN
{graph.nodeList ← List.Union[graph.nodeList, LIST[node]];
[] ← RouteDiGraph.EnumArcsFromNode[graph, node, both, AddArcs]};
END;
AddNewNode: PUBLIC PROC [graph: RouteDiGraph.Graph, nodeInfo: REF ANY ← NIL, superiorArcs, inferiorArcs: RouteDiGraph.ArcList ← NIL] RETURNS [node: RouteDiGraph.Node] =
BEGIN
IF graph # NIL THEN
{node ← RouteDiGraph.CreateNode[nodeInfo, superiorArcs, inferiorArcs];
RouteDiGraph.IncludeNode[graph, node]};
END;
Arcs
CreateArc: PUBLIC PROC [arcInfo: REF ANY ← NIL, superiorNode, inferiorNode: RouteDiGraph.Node, weight: REF ANY ← NIL] RETURNS [arc: RouteDiGraph.Arc] =
BEGIN
arc ← NEW[RouteDiGraph.ArcRec ← [arcInfo: arcInfo, superiorNode: superiorNode, inferiorNode: inferiorNode, weight: weight]];
END;
RemoveArc: PUBLIC PROC [graph: RouteDiGraph.Graph, arc: RouteDiGraph.Arc] =
BEGIN
IF graph # NIL AND arc # NIL THEN
{sNode: RouteDiGraph.Node ← arc.superiorNode;
iNode: RouteDiGraph.Node ← arc.inferiorNode;
sNode.inferiorArcs ← List.Remove[arc, sNode.inferiorArcs];
iNode.superiorArcs ← List.Remove[arc, iNode.superiorArcs];
graph.arcList ← List.Remove[arc, graph.arcList]};
END;
IncludeArc: PUBLIC PROC [graph: RouteDiGraph.Graph, arc: RouteDiGraph.Arc] =
BEGIN
IF graph # NIL AND arc # NIL THEN
{sNode: RouteDiGraph.Node ← arc.superiorNode;
iNode: RouteDiGraph.Node ← arc.inferiorNode;
sNode.inferiorArcs ← List.Union[sNode.inferiorArcs, LIST[arc]];
iNode.superiorArcs ← List.Union[iNode.superiorArcs, LIST[arc]];
need to include only if not already in the list
graph.arcList ← List.Union[graph.arcList, LIST[arc]]};
END;
AddNewArc: PUBLIC PROC [graph: RouteDiGraph.Graph, arcInfo: REF ANY ← NIL, superiorNode, inferiorNode: RouteDiGraph.Node, weight: REF ANY ← NIL] RETURNS [arc: RouteDiGraph.Arc] =
BEGIN
arc ← RouteDiGraph.CreateArc[arcInfo, superiorNode, inferiorNode, weight];
RouteDiGraph.IncludeArc[graph, arc];
END;
Predicates
InCycle: PUBLIC PROC [graph: RouteDiGraph.Graph, node: RouteDiGraph.Node] RETURNS [BOOLEAN] =
BEGIN
RETURN[TRUE]
END;
OnLongestPath: PUBLIC PROC [graph: RouteDiGraph.Graph, node: RouteDiGraph.Node] RETURNS [BOOLEAN] =
BEGIN
RETURN[TRUE]
END;
PathExists: PUBLIC PROC [graph: RouteDiGraph.Graph, upperNode, lowerNode: RouteDiGraph.Node]RETURNS [quit: BOOLEAN ← FALSE] = {
recursively go through the constraints
ArcProc: RouteDiGraph.EnumArcsFromNodeProc = {
IF arc.superiorNode = upperNode THEN quit ← TRUE
ELSE quit ← RouteDiGraph.EnumArcsFromNode[graph, arc.superiorNode, out, ArcProc]};
quit ← RouteDiGraph.EnumArcsFromNode[graph, lowerNode, out, ArcProc]};
Graph Operations
TopoSort: PUBLIC PROC [graph: RouteDiGraph.Graph] RETURNS [sortedNodes: RouteDiGraph.NodeList] =
BEGIN
END;
EnumNodes: PUBLIC PROC [graph: RouteDiGraph.Graph, enumNode: RouteDiGraph.EnumNodeProc] RETURNS [quit: BOOLEAN ← FALSE] =
BEGIN
IF graph # NIL THEN
FOR nList: RouteDiGraph.NodeList ← graph.nodeList, nList.rest WHILE ~quit AND nList # NIL DO
quit ← enumNode[graph, NARROW[nList.first]];
ENDLOOP;
END;
EnumArcs: PUBLIC PROC [graph: RouteDiGraph.Graph, enumArc: RouteDiGraph.EnumArcProc] RETURNS [quit: BOOLEAN ← FALSE] =
BEGIN
IF graph # NIL THEN
FOR aList: RouteDiGraph.ArcList ← graph.arcList, aList.rest WHILE ~quit AND aList # NIL DO
quit ← enumArc[graph, NARROW[aList.first]];
ENDLOOP;
END;
EnumArcsFromNode: PUBLIC PROC [graph: RouteDiGraph.Graph, node: RouteDiGraph.Node, direction: RouteDiGraph.DirectionOrBoth, enumArc: RouteDiGraph.EnumArcsFromNodeProc] RETURNS [quit: BOOLEAN ← FALSE] =
BEGIN
IF node # NIL AND graph # NIL THEN
{IF direction = in OR direction = both THEN
FOR aList: RouteDiGraph.ArcList ← node.inferiorArcs, aList.rest WHILE ~quit AND aList # NIL DO
quit ← enumArc[graph, NARROW[aList.first], node, in];
ENDLOOP;
IF direction = out OR direction = both THEN
FOR aList: RouteDiGraph.ArcList ← node.superiorArcs, aList.rest WHILE ~quit AND aList # NIL DO
quit ← enumArc[graph, NARROW[aList.first], node, out];
ENDLOOP;
};
END;
Utility Operations
CheckGraph: PUBLIC PROC [graph: RouteDiGraph.Graph] RETURNS [ok: BOOLEAN] =
BEGIN
END;
WriteNodes: PUBLIC PROC [graph: RouteDiGraph.Graph, writeNode: RouteDiGraph.EnumNodeProc, writeArc: RouteDiGraph.EnumArcsFromNodeProc] =
BEGIN
ListNode: RouteDiGraph.EnumNodeProc =
{quit ← writeNode[graph, node];
IF ~quit THEN
{TerminalIO.WriteRope[Rope.Cat["\n", " superior arcs: "]];
quit ← EnumArcsFromNode[graph, node, out, writeArc]};
IF ~quit THEN
{TerminalIO.WriteRope[Rope.Cat["\n", " inferior arcs: "]];
quit ← EnumArcsFromNode[graph, node, in, writeArc]};
};
TerminalIO.WriteRope[Rope.Cat["\n", "graph: ", SimpleRefAny[graph.graphInfo]]];
TerminalIO.WriteRope["\n nodes: "];
[] ← EnumNodes[graph, ListNode];
END;
SimpleListNodeProc: PUBLIC RouteDiGraph.EnumNodeProc =
BEGIN
TerminalIO.WriteRope[Rope.Cat["\n", " name: ", SimpleRefAny[node.nodeInfo]]];
RETURN[FALSE];
END;
SimpleListArcNodeProc: PUBLIC RouteDiGraph.EnumArcsFromNodeProc =
BEGIN
TerminalIO.WriteRope[Rope.Cat["\n", " name: ", SimpleRefAny[arc.arcInfo], ", weight: ", SimpleRefAny[arc.weight]]];
RETURN[FALSE];
END;
WriteArcs: PUBLIC PROC [graph: RouteDiGraph.Graph, writeArc: RouteDiGraph.EnumArcProc, writeNode: RouteDiGraph.EnumNodeProc] =
BEGIN
ListArc: RouteDiGraph.EnumArcProc =
{quit ← writeArc[graph, arc];
IF ~quit THEN
{TerminalIO.WriteRope[Rope.Cat["\n", " superior node: "]];
quit ← writeNode[graph, arc.superiorNode]};
IF ~quit THEN
{TerminalIO.WriteRope[Rope.Cat["\n", " inferior node: "]];
quit ← writeNode[graph, arc.inferiorNode]};
};
TerminalIO.WriteRope[Rope.Cat["\n", "graph: ", SimpleRefAny[graph.graphInfo]]];
TerminalIO.WriteRope["\n arcs: "];
[] ← EnumArcs[graph, ListArc];
END;
SimpleListArcProc: PUBLIC RouteDiGraph.EnumArcProc =
BEGIN
TerminalIO.WriteRope[Rope.Cat["\n", " name: ", SimpleRefAny[arc.arcInfo], ", weight: ", SimpleRefAny[arc.weight]]];
RETURN[FALSE];
END;
SimpleRefAny: PUBLIC PROC [in: REF ANY] RETURNS [out: Rope.ROPE ← NIL] =
BEGIN
IF in # NIL THEN
WITH in SELECT FROM
rr: REF Rope.ROPE => out ← rr^;
r: Rope.ROPE => out ← r;
ri: REF INT => out ← Convert.RopeFromInt[ri^];
rre: REF REAL => out ← Convert.RopeFromReal[rre^];
ENDCASE => Error [callingError, "Invalid Ref Any type."];
RETURN[out];
END;
END.