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 = {
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.
graph ← NEW[RouteDiGraph.GraphRec ← [graphInfo: graphInfo]];
};
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
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
IF enumNode # NIL THEN [] ← EnumNodes[graph, enumNode];
IF enumArc # NIL THEN [] ← EnumArcs[graph, enumArc];
IF enumGraph # NIL THEN [] ← enumGraph[graph];
next unlink the arcs from the nodes
[] ← EnumNodes[graph, UnlinkNode];
};
Nodes
CreateNode: PUBLIC PROC [nodeInfo: REF ANY ← NIL, superiorArcs, inferiorArcs: RouteDiGraph.ArcList ← NIL] RETURNS [node: RouteDiGraph.Node] = {
node ← NEW[RouteDiGraph.NodeRec ← [nodeInfo: nodeInfo, superiorArcs: superiorArcs, inferiorArcs: inferiorArcs]];
};
RemoveNode: PUBLIC PROC [graph: RouteDiGraph.Graph, node: RouteDiGraph.Node] RETURNS [removedArcs: RouteDiGraph.ArcList] = {
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]};
};
IncludeNode: PUBLIC PROC [graph: RouteDiGraph.Graph, node: RouteDiGraph.Node] = {
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]};
};
AddNewNode: PUBLIC PROC [graph: RouteDiGraph.Graph, nodeInfo: REF ANY ← NIL, superiorArcs, inferiorArcs: RouteDiGraph.ArcList ← NIL] RETURNS [node: RouteDiGraph.Node] = {
IF graph # NIL THEN
{node ← RouteDiGraph.CreateNode[nodeInfo, superiorArcs, inferiorArcs];
RouteDiGraph.IncludeNode[graph, node]};
};
Arcs
CreateArc: PUBLIC PROC [arcInfo: REF ANY ← NIL, superiorNode, inferiorNode: RouteDiGraph.Node, weight: REF ANY ← NIL] RETURNS [arc: RouteDiGraph.Arc] = {
arc ← NEW[RouteDiGraph.ArcRec ← [arcInfo: arcInfo, superiorNode: superiorNode, inferiorNode: inferiorNode, weight: weight]];
};
RemoveArc: PUBLIC PROC [graph: RouteDiGraph.Graph, arc: RouteDiGraph.Arc] = {
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]};
};
IncludeArc: PUBLIC PROC [graph: RouteDiGraph.Graph, arc: RouteDiGraph.Arc] = {
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]]};
};
AddNewArc: PUBLIC PROC [graph: RouteDiGraph.Graph, arcInfo: REF ANY ← NIL, superiorNode, inferiorNode: RouteDiGraph.Node, weight: REF ANY ← NIL] RETURNS [arc: RouteDiGraph.Arc] = {
arc ← RouteDiGraph.CreateArc[arcInfo, superiorNode, inferiorNode, weight];
RouteDiGraph.IncludeArc[graph, arc];
};
Predicates
InCycle: PUBLIC PROC [graph: RouteDiGraph.Graph, node: RouteDiGraph.Node] RETURNS [BOOLEAN] = {
RETURN[TRUE]
};
OnLongestPath: PUBLIC PROC [graph: RouteDiGraph.Graph, node: RouteDiGraph.Node] RETURNS [BOOLEAN] = {
RETURN[TRUE]
};
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
EnumNodesInTopoOrder: PUBLIC PROC [graph: RouteDiGraph.Graph, enumNode: RouteDiGraph.EnumNodeProc] RETURNS [quit: BOOLEAN ← FALSE] = {
ResetParity: RouteDiGraph.EnumNodeProc ~ {
node.superiorParity ← List.Length[node.superiorArcs];
node.inferiorParity ← List.Length[node.inferiorArcs]};
recursively go through the constraints
ArcProc: RouteDiGraph.EnumArcsFromNodeProc = {
superiorNode: RouteDiGraph.Node ← arc.superiorNode;
superiorNode.inferiorParity ← superiorNode.inferiorParity - 1;
IF superiorNode.inferiorParity = 0 THEN {
quit ← enumNode[graph, superiorNode];
IF ~quit THEN
quit ← RouteDiGraph.EnumArcsFromNode[graph, superiorNode, out, ArcProc]}};
NodeProc: RouteDiGraph.EnumNodeProc = {
IF node.inferiorParity = 0 THEN {
quit ← enumNode[graph, node];
IF ~quit THEN
quit ← RouteDiGraph.EnumArcsFromNode[graph, node, out, ArcProc]}};
[] ← RouteDiGraph.EnumNodes[graph, ResetParity];
quit ← RouteDiGraph.EnumNodes[graph, NodeProc];
};
EnumNodes: PUBLIC PROC [graph: RouteDiGraph.Graph, enumNode: RouteDiGraph.EnumNodeProc] RETURNS [quit: BOOLEAN ← FALSE] = {
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;
};
EnumArcs: PUBLIC PROC [graph: RouteDiGraph.Graph, enumArc: RouteDiGraph.EnumArcProc] RETURNS [quit: BOOLEAN ← FALSE] = {
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;
};
EnumArcsFromNode: PUBLIC PROC [graph: RouteDiGraph.Graph, node: RouteDiGraph.Node, direction: RouteDiGraph.DirectionOrBoth, enumArc: RouteDiGraph.EnumArcsFromNodeProc] RETURNS [quit: BOOLEAN ← FALSE] = {
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;
};
};
Utility Operations
CheckGraph: PUBLIC PROC [graph: RouteDiGraph.Graph] RETURNS [ok: BOOLEAN] = {
};
WriteNodes: PUBLIC PROC [graph: RouteDiGraph.Graph, writeNode: RouteDiGraph.EnumNodeProc, writeArc: RouteDiGraph.EnumArcsFromNodeProc] = {
ListNode: RouteDiGraph.EnumNodeProc =
{quit ← writeNode[graph, node];
IF ~quit THEN
{TerminalIO.PutRope[Rope.Cat["\n", " superior arcs: "]];
quit ← EnumArcsFromNode[graph, node, out, writeArc]};
IF ~quit THEN
{TerminalIO.PutRope[Rope.Cat["\n", " inferior arcs: "]];
quit ← EnumArcsFromNode[graph, node, in, writeArc]};
};
TerminalIO.PutRope[Rope.Cat["\n", "graph: ", SimpleRefAny[graph.graphInfo]]];
TerminalIO.PutRope["\n nodes: "];
[] ← EnumNodes[graph, ListNode];
};
SimpleListNodeProc: PUBLIC RouteDiGraph.EnumNodeProc = {
TerminalIO.PutRope[Rope.Cat["\n", " name: ", SimpleRefAny[node.nodeInfo]]];
RETURN[FALSE];
};
SimpleListArcNodeProc: PUBLIC RouteDiGraph.EnumArcsFromNodeProc =
{
TerminalIO.PutRope[Rope.Cat["\n", " name: ", SimpleRefAny[arc.arcInfo], ", weight: ", SimpleRefAny[arc.weight]]];
RETURN[FALSE];
};
WriteArcs: PUBLIC PROC [graph: RouteDiGraph.Graph, writeArc: RouteDiGraph.EnumArcProc, writeNode: RouteDiGraph.EnumNodeProc] = {
ListArc: RouteDiGraph.EnumArcProc =
{quit ← writeArc[graph, arc];
IF ~quit THEN
{TerminalIO.PutRope[Rope.Cat["\n", " superior node: "]];
quit ← writeNode[graph, arc.superiorNode]};
IF ~quit THEN
{TerminalIO.PutRope[Rope.Cat["\n", " inferior node: "]];
quit ← writeNode[graph, arc.inferiorNode]};
};
TerminalIO.PutRope[Rope.Cat["\n", "graph: ", SimpleRefAny[graph.graphInfo]]];
TerminalIO.PutRope["\n arcs: "];
[] ← EnumArcs[graph, ListArc];
};
SimpleListArcProc: PUBLIC RouteDiGraph.EnumArcProc = {
TerminalIO.PutRope[Rope.Cat["\n", " name: ", SimpleRefAny[arc.arcInfo], ", weight: ", SimpleRefAny[arc.weight]]];
RETURN[FALSE];
};
SimpleRefAny: PUBLIC PROC [in: REF ANY] RETURNS [out: Rope.ROPE ← NIL] = {
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];
};
}.