RouteDiGraph.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Last Edited by: Preas, July 17, 1985 11:44:46 am PDT
DIRECTORY
List,
Rope,
TerminalIO;
RouteDiGraph: CEDAR DEFINITIONS = BEGIN
Theory
This interface provides the procedures necessary to define and process directed graphs. Additions are welcome.
Common Types
LORA: TYPE = List.LORA;
Relation: TYPE = {none, inferior, equal, superior};
DirectionOrBoth: TYPE = {in, out, both};
Direction: TYPE = DirectionOrBoth[in .. out];
Errors
Error: SIGNAL [errorType: ErrorType ← callingError, explanation: Rope.ROPE ← NIL];
ErrorType: TYPE = {programmingError, callingError, noResource, other};
Graph
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];
Create a directed Graph.
DestroyGraph:
PROC [graph: Graph
, enumGraph: EnumGraphProc, enumNode: EnumNodeProc, enumArc: EnumArcProc];
There may be circular references. enumGraph, enumNode and enumArc allow client to NIL any circular references in graphInfo, nodeInfo and arcInfo if necessary
EnumGraphProc:
TYPE =
PROC [graph: Graph]
RETURNS [quit:
BOOLEAN ←
FALSE];
To NIL any circular references in graphInfo if needed.
Nodes
Node: TYPE = REF NodeRec;
NodeList: TYPE = LORA -- LIST OF Node -- ;
NodeRec:
TYPE =
RECORD[
nodeInfo: REF ANY,
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];
Arcs
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];
Predicates
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];
Graph Operations
TopoSort: PROC [graph: Graph] RETURNS [sortedNodes: NodeList];
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];
Utility Operations
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.