DIRECTORY Rope; RouteDiGraph: CEDAR DEFINITIONS = BEGIN Relation: TYPE = {none, inferior, equal, superior}; DirectionOrBoth: TYPE = {in, out, both}; Direction: TYPE = DirectionOrBoth[in .. out]; LORA: TYPE = LIST OF REF ANY; 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]; IncludeArcs: PROC [graph: Graph, arcs: ArcList]; 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. TRouteDiGraph.mesa Copyright Σ 1985, 1986, 1987 by Xerox Corporation. All rights reserved. Last Edited by: Preas, December 18, 1986 5:10:35 pm PST 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šœH™HJ™7J™šΟk œ˜ Jšœ˜—J˜JšΟn œœ œ˜'head™Ibody™o—™ Jšœ œ%˜3Jšœœ˜(Jšœ œ˜-Jš œœœœœœ˜—™Jšžœœ9œœ˜SJšœ œ7˜F—™Jšœœœ ˜šœ œœ˜Jšœ œœœ˜Jšœœ˜Jšœœ˜Jšœœ˜Jšœ˜Jšœ˜—J˜š ž œœ œœœœ˜DJ™J™—šž œœj˜|Jšœ™—J˜š œœœœœœ˜JJ™6——™Jšœœœ ˜Jšœ œœΟcœ˜+šœ œœ˜Jšœ œœ˜Jšœ œ˜(Jšœœ˜Jšœ˜Jšœ˜J˜—J˜Jšž œœ œœœ(œœ˜kJ˜Jšž œœœ˜KJ˜Jšž œœ˜-J˜Jšž œœœœœœ(œœ˜€—™Jšœœœ˜Jšœ œœŸœ˜)šœœœ˜Jšœ œœ˜Jšœ#œ˜'Jšœœ˜Jšœ˜J˜—Jšž œœ œœœ,œœœœ ˜uJ˜Jšž œœ˜)J˜Jšž œœ˜*J˜Jšž œœ˜0J˜Jšž œœœœœ,œœœœ ˜ƒ—™ Jšžœœœœ˜;J˜Jšž œœœœ˜AJ˜Jšž œœ+œœ˜M—™Jš žœœœ(œœœ˜iJ˜Icodeš œœœœœœ˜TJš ž œœ(œœœ˜WJ˜Mš œ œœœœœ˜QJš žœœ&œœœ˜TJ˜Mš œœœ;œœœ˜|Jš žœœWœœœ˜—™Jšž œœœœ˜6J˜Jšž œœI˜YJšžœ˜.Jšžœ$˜9J˜Jšž œœ@˜OJšžœ˜,J˜Jš ž œœœœœ œ˜:J˜—Jšœ˜—…— \