DIRECTORY Convert, List, Rope, RouteDiGraph, TerminalIO; RouteDiGraphImpl: CEDAR PROGRAM IMPORTS Convert, List, Rope, RouteDiGraph, TerminalIO EXPORTS RouteDiGraph = BEGIN Error: PUBLIC SIGNAL [errorType: RouteDiGraph.ErrorType _ callingError, explanation: Rope.ROPE _ NIL] = CODE; CreateGraph: PUBLIC PROC [graphInfo: REF ANY _ NIL] RETURNS [graph: RouteDiGraph.Graph] = BEGIN graph _ NEW[RouteDiGraph.GraphRec _ [graphInfo: graphInfo]]; END; DestroyGraph: PUBLIC PROC [graph: RouteDiGraph.Graph, enumGraph: RouteDiGraph.EnumGraphProc, enumNode: RouteDiGraph.EnumNodeProc, enumArc: RouteDiGraph.EnumArcProc] = BEGIN UnlinkNode: RouteDiGraph.EnumNodeProc = {DeleteArcs: RouteDiGraph.EnumArcsFromNodeProc = {RemoveArc[graph, arc]}; graph.nodeList _ List.Remove[node, graph.nodeList]; [] _ RouteDiGraph.EnumArcsFromNode[graph, node, both, DeleteArcs]; }; [] _ EnumNodes[graph, enumNode]; [] _ EnumArcs[graph, enumArc]; [] _ enumGraph[graph]; [] _ EnumNodes[graph, UnlinkNode]; END; 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; 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]]; 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; 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] = { 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]}; 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; 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. €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 Utility Operations ‌ت çکJڑœ™Jڑœ دmœ1™