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]; 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. NRouteDiGraph.mesa Copyright c 1985, 1986 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šœ Οmœ7™BJ™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šŸ œžœžœžœžœ,žœžœžœžœ ˜ƒ—™ 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šžœ˜—…— ΰ