
<<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.