DIRECTORY List, Rope, TerminalIO; RouteDiGraph: CEDAR DEFINITIONS = BEGIN LORA: TYPE = List.LORA; Relation: TYPE = {none, inferior, equal, superior}; DirectionOrBoth: TYPE = {in, out, both}; Direction: TYPE = DirectionOrBoth[in .. out]; Error: SIGNAL [errorType: ErrorType _ callingError, explanation: Rope.ROPE _ NIL]; ErrorType: TYPE = {programmingError, callingError, noResource, other}; Graph: TYPE = REF GraphRec; GraphRec: TYPE = RECORD [ graphInfo: REF ANY _ NIL, nodeList: NodeList _ NIL, arcList: ArcList _ NIL, superiorNodes: NodeList _ NIL, inferiorNodes: NodeList _ NIL ]; CreateGraph: PROC [graphInfo: REF ANY _ NIL] RETURNS [graph: Graph]; DestroyGraph: PROC [graph: Graph, enumGraph: EnumGraphProc _ NIL, enumNode: EnumNodeProc _ NIL, enumArc: EnumArcProc _ NIL]; EnumGraphProc: TYPE = PROC [graph: Graph] RETURNS [quit: BOOLEAN _ FALSE]; Node: TYPE = REF NodeRec; NodeList: TYPE = LORA -- LIST OF Node -- ; NodeRec: TYPE = RECORD[ nodeInfo: REF ANY, superiorParity, inferiorParity: INT _ 0, superiorArcs: ArcList _ NIL, inferiorArcs: ArcList _ NIL ]; CreateNode: PROC [nodeInfo: REF ANY _ NIL, superiorArcs, inferiorArcs: ArcList _ NIL] RETURNS [node: Node]; RemoveNode: PROC [graph: Graph, node: Node] RETURNS [removedArcs: ArcList]; IncludeNode: PROC [graph: Graph, node: Node]; AddNewNode: PUBLIC PROC [graph: Graph, nodeInfo: REF ANY _ NIL, superiorArcs, inferiorArcs: ArcList _ NIL] RETURNS [node: Node]; Arc: TYPE = REF ArcRec; ArcList: TYPE = LORA -- LIST OF Arc -- ; ArcRec: TYPE = RECORD[ arcInfo: REF ANY, superiorNode, inferiorNode: Node _ NIL, weight: REF ANY ]; CreateArc: PROC [arcInfo: REF ANY _ NIL, superiorNode, inferiorNode: Node, weight: REF ANY _ NIL] RETURNS [arc: Arc]; RemoveArc: PROC [graph: Graph, arc: Arc]; IncludeArc: PROC [graph: Graph, arc: Arc]; AddNewArc: PROC [graph: Graph, arcInfo: REF ANY _ NIL, superiorNode, inferiorNode: Node, weight: REF ANY _ NIL] RETURNS [arc: Arc]; InCycle: PROC [graph: Graph, node: Node] RETURNS [BOOLEAN]; OnLongestPath: PROC [graph: Graph, node: Node] RETURNS [BOOLEAN]; PathExists: PROC [graph: Graph, upperNode, lowerNode: Node]RETURNS [BOOLEAN]; EnumNodesInTopoOrder: PUBLIC PROC [graph: Graph, enumNode: EnumNodeProc] RETURNS [quit: BOOLEAN _ FALSE]; EnumNodeProc: TYPE = PROC[graph: Graph, node: Node] RETURNS [quit: BOOLEAN _ FALSE]; EnumNodes: PROC [graph: Graph, enumNode: EnumNodeProc] RETURNS [quit: BOOLEAN _ FALSE]; EnumArcProc: TYPE = PROC[graph: Graph, arc: Arc] RETURNS [quit: BOOLEAN _ FALSE]; EnumArcs: PROC [graph: Graph, enumArc: EnumArcProc] RETURNS [quit: BOOLEAN _ FALSE]; EnumArcsFromNodeProc: TYPE = PROC[graph: Graph, arc: Arc, node: Node, direction: Direction] RETURNS [quit: BOOLEAN _ FALSE]; EnumArcsFromNode: PROC [graph: Graph, node: Node, direction: DirectionOrBoth, enumArc: EnumArcsFromNodeProc] RETURNS [quit: BOOLEAN _ FALSE]; CheckGraph: PROC [graph: Graph] RETURNS [ok: BOOLEAN]; WriteNodes: PROC [graph: Graph, writeNode: EnumNodeProc, writeArc: EnumArcsFromNodeProc]; SimpleListNodeProc: RouteDiGraph.EnumNodeProc; SimpleListArcNodeProc: RouteDiGraph.EnumArcsFromNodeProc; WriteArcs: PROC [graph: Graph, writeArc: EnumArcProc, writeNode: EnumNodeProc]; SimpleListArcProc: RouteDiGraph.EnumArcProc; SimpleRefAny: PROC [in: REF ANY] RETURNS [out: Rope.ROPE]; END. FRouteDiGraph.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Last Edited by: Preas, July 17, 1985 11:44:46 am PDT Theory This interface provides the procedures necessary to define and process directed graphs. Additions are welcome. Common 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 To NIL any circular references in graphInfo if needed. Nodes Arcs Predicates Graph Operations Utility Operations Κν˜Jšœ™Jšœ Οmœ1™