DIRECTORY 
Convert,
List,
Rope,
RouteDiGraph,
TerminalIO;

RouteDiGraphImpl: CEDAR PROGRAM
IMPORTS Convert, List, Rope, RouteDiGraph, TerminalIO
EXPORTS RouteDiGraph = {
Error: PUBLIC SIGNAL [errorType: RouteDiGraph.ErrorType _ callingError, explanation: Rope.ROPE _ NIL] = CODE; 

CreateGraph: PUBLIC PROC [graphInfo: REF ANY _ NIL] RETURNS [graph: RouteDiGraph.Graph] = {
graph _ NEW[RouteDiGraph.GraphRec _ [graphInfo: graphInfo]];
};

DestroyGraph: PUBLIC PROC [graph: RouteDiGraph.Graph, enumGraph: RouteDiGraph.EnumGraphProc, enumNode: RouteDiGraph.EnumNodeProc, enumArc: RouteDiGraph.EnumArcProc] = {

UnlinkNode: RouteDiGraph.EnumNodeProc =

{DeleteArcs: RouteDiGraph.EnumArcsFromNodeProc =
{RemoveArc[graph, arc]};

graph.nodeList _ List.Remove[node, graph.nodeList];
[] _ RouteDiGraph.EnumArcsFromNode[graph, node, both, DeleteArcs];
};


IF enumNode # NIL THEN [] _ EnumNodes[graph, enumNode];
IF enumArc # NIL THEN [] _ EnumArcs[graph, enumArc];
IF enumGraph # NIL THEN [] _ enumGraph[graph];

[] _ EnumNodes[graph, UnlinkNode];
};
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]};
};

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]];
graph.arcList _ List.Union[graph.arcList, LIST[arc]]};
};

IncludeArcs: PUBLIC PROC [graph: RouteDiGraph.Graph, arcs: RouteDiGraph.ArcList] ~ {
IF graph # NIL THEN
FOR aList: RouteDiGraph.NodeList _ arcs, aList.rest WHILE aList # NIL DO
arc: RouteDiGraph.Arc _ NARROW[aList.first];
IncludeArc[graph, arc];
ENDLOOP;
};

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];
};

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] = {

ArcProc: RouteDiGraph.EnumArcsFromNodeProc = {
IF arc.inferiorNode = lowerNode THEN quit _ TRUE
ELSE quit _ RouteDiGraph.EnumArcsFromNode[graph, arc.inferiorNode, in, ArcProc]};

quit _ RouteDiGraph.EnumArcsFromNode[graph, upperNode, in, ArcProc]};

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]};

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;
};
};
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];
};
}.

¦RouteDiGraphImpl.mesa
Copyright c 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

Common Types
types
Errors
Graph
Create a directed Graph.

There may be circular references. enumGraph, enumNode and enumArc allow client to NIL any circular references in graphInfo, nodeInfo and arcInfo if necessary
first do the client data
next unlink the arcs from the nodes
Nodes

Arcs
need to include only if not already in the list
Predicates
recursively go through the constraints
Graph Operations
recursively go through the constraints
Utility Operations
Κ
˜Jš
œ™Jšœ
Οm
œ1™<J™4J™Jš
œF™FJ™šΟk	œ
˜
Jš
œ˜Jš
œ˜Jš
œ˜Jš
œ
˜
Jš
œ˜—J˜JšΟnœžœ
ž˜Jšžœ.˜5Jšžœ˜
head™Jš
œ™—™IcodešŸœžœ
žœFžœžœžœ˜n—™J˜šŸœžœ
žœ
žœ
žœžœžœ ˜[L™L™Lšœžœ1˜<Lš
œ˜L˜—šŸœžœ
žœ
˜¨
Lš
œ
™
L˜šŸ
œ˜'L˜šœ
Ÿ
œ%˜0š
œ˜L˜——Lš
œ3˜3Lš
œB˜BLš
œ˜L˜—L˜Lš
œ™Lšžœžœ!˜7Lšžœžœ˜4Lšžœžœ˜.L˜Lš
œ#™#Lš
œ"˜"Lš
œ˜——™šŸ
œžœ
žœžœ
žœžœ5žœžœ˜
Lšœžœf˜pLš
œ˜L™L˜—šŸ
œžœ
žœ6žœ(˜|L˜šŸ
œ%˜/š
œ˜L˜——šžœ	žœ
ž˜Lš
œ4˜4Lš
œ@˜@Lš
œC˜C—Lš
œ˜L˜—šŸœžœ
žœ9˜QšŸœ%˜,šœžœ
žœ˜(L˜——šžœ	žœ
ž˜Lšœ-žœ˜9Lš
œ@˜@—Lš
œ˜L˜—šŸ
œžœ
žœ'žœ
žœžœ5žœžœ˜ͺ
šžœ	žœ
ž˜Lš
œF˜FLš
œ'˜'—Lš
œ˜——™J˜šŸ	œžœ
žœžœ
žœžœ9žœ
žœžœžœ˜™
Lšœžœs˜|Lš
œ˜—L˜šŸ	œžœ
žœ7˜Mš	žœ	žœ
žœžœ
ž˜!Lš
œ-˜-Lš
œ,˜,Lš
œ:˜:Lš
œ:˜:Lš
œ1˜1—Lš
œ˜L˜—šŸ
œžœ
žœ7˜Nš	žœ	žœ
žœžœ
ž˜!Lš
œ-˜-Lš
œ,˜,Lšœ4žœ˜?Lšœ4žœ˜?Lš
œ/™/Lšœ*žœ˜6—Lš
œ˜—L˜šŸœžœ
žœ<˜Tšžœ	žœ
ž˜šžœ1žœ	žœ
ž˜HLšœžœ˜,Lš
œ˜Lšžœ
˜——L˜L˜—šŸ	œžœ
žœ&žœ
žœžœ9žœ
žœžœžœ˜΄
Lš
œJ˜JLš
œ$˜$Lš
œ˜——™
J˜š
Ÿœžœ
žœ6žœžœ˜_Lšžœ
žœ
˜Lš
œ˜—L˜š
Ÿ
œžœ
žœ6žœžœ˜eLšžœ
žœ
˜Lš
œ˜—L˜šŸ
œžœ
žœEžœžœžœ˜L˜Lš
œ&™&šŸœ'˜.Lšžœžœž˜0LšžœM˜QL˜—Lš
œE˜E——™J˜šŸœžœ
žœBžœžœžœ˜†
šŸœ˜*Lš
œ5˜5Lš
œ6˜6L˜—Lš
œ&™&šŸœ'˜.Lš
œ3˜3Lš
œ>˜>šžœ!žœ˜)Lš
œ%˜%šžœžœ
˜Lš
œJ˜J——L˜—šŸœ˜'šžœžœ˜!Lš
œ˜šžœžœ
˜Lš
œB˜B——L˜—Lš
œ0˜0Lš
œ/˜/Lš
œ˜—L˜šŸ	œžœ
žœBžœžœžœ˜{šžœ	žœ
ž˜š	žœ;žœžœ	žœ
ž˜\Lšœžœ˜,Lšžœ
˜——Lš
œ˜L˜—šŸœžœ
žœ@žœžœžœ˜yšžœ	žœ
ž˜š	žœ9žœžœ	žœ
ž˜ZLšœžœ˜+Lšžœ
˜——Lš
œ˜—L˜šŸœžœ
žœ‹
žœžœžœ˜Λ
š	žœžœ
žœ	žœ
ž˜"šœ
žœžœž˜+š	žœ=žœžœ	žœ
ž˜^Lšœžœ˜5Lšžœ
˜——šžœžœž˜+š	žœ=žœžœ	žœ
ž˜^Lšœžœ˜6Lšžœ
˜——L˜—Lš
œ˜——™š
Ÿ
œžœ
žœžœžœ˜MLš
œ˜—L˜šŸ
œžœ
žœs˜Š
šŸœ˜%Lš
œ˜L˜šžœž˜
Lš
œA˜ALš
œ5˜5—L˜šžœž˜
Lš
œA˜ALš
œ4˜4—L˜L˜—Lš
œM˜MLš
œ!˜!Lš
œ ˜ Lš
œ˜—L˜šŸœžœ˜8Lš
œO˜OLšžœ
žœ˜Lš
œ˜L˜—šŸœžœ$˜AL˜Lš
œ
˜
Lš
œ˜Lšžœ
žœ˜Lš
œ˜L˜—˜L˜—šŸ	œžœ
žœj˜€
šŸœ˜#Lš
œ˜L˜šžœž˜
Lš
œA˜ALš
œ+˜+—L˜šžœž˜
Lš
œA˜ALš
œ+˜+—L˜L˜—Lš
œM˜MLš
œ ˜ Lš
œ˜Lš
œ˜L˜—šŸœžœ˜6Lš
œt˜tLšžœ
žœ˜Lš
œ˜L˜—šŸœžœ
žœžœ
žœžœžœžœ˜Jšžœžœ
ž˜šžœžœ
ž˜Lšœžœžœ˜Lšœžœ˜Lšœžœ
žœ#˜.Lšœžœ
žœ%˜2Lšžœ2˜9——Lšžœ˜Lš
œ˜——Jš
œ˜J˜—…—"Φ/™