RouteDiGraph.mesa
Copyright Ó 1985, 1986, 1987 by Xerox Corporation. All rights reserved.
Last Edited by: Preas, December 18, 1986 5:10:35 pm PST
DIRECTORY
Rope;
RouteDiGraph: CEDAR DEFINITIONS = BEGIN
Theory
This interface provides the procedures necessary to define and process directed graphs. Additions are welcome.
Common Types
Relation: TYPE = {none, inferior, equal, superior};
DirectionOrBoth: TYPE = {in, out, both};
Direction: TYPE = DirectionOrBoth[in .. out];
LORA: TYPE = LIST OF REF ANY;
Errors
Error: SIGNAL [errorType: ErrorType ← callingError, explanation: Rope.ROPENIL];
ErrorType: TYPE = {programmingError, callingError, noResource, other};
Graph
Graph: TYPE = REF GraphRec;
GraphRec: TYPE = RECORD [
graphInfo: REF ANYNIL,
nodeList: NodeList ← NIL,
arcList: ArcList ← NIL,
superiorNodes: NodeList ← NIL,
inferiorNodes: NodeList ← NIL
];
CreateGraph: PROC [graphInfo: REF ANYNIL] RETURNS [graph: Graph];
Create a directed Graph.
DestroyGraph: PROC [graph: Graph, enumGraph: EnumGraphProc ← NIL, enumNode: EnumNodeProc ← NIL, enumArc: EnumArcProc ← NIL];
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: BOOLEANFALSE];
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,
superiorParity, inferiorParity: INT ← 0,
superiorArcs: ArcList ← NIL,
inferiorArcs: ArcList ← NIL
];
CreateNode: PROC [nodeInfo: REF ANYNIL, 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 ANYNIL, 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 ANYNIL, superiorNode, inferiorNode: Node, weight: REF ANYNIL] RETURNS [arc: Arc];
RemoveArc: PROC [graph: Graph, arc: Arc];
IncludeArc: PROC [graph: Graph, arc: Arc];
AddNewArc: PROC [graph: Graph, arcInfo: REF ANYNIL, superiorNode, inferiorNode: Node, weight: REF ANYNIL] 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
EnumNodesInTopoOrder: PUBLIC PROC [graph: Graph, enumNode: EnumNodeProc] RETURNS [quit: BOOLEANFALSE];
EnumNodeProc: TYPE = PROC[graph: Graph, node: Node] RETURNS [quit: BOOLEANFALSE];
EnumNodes: PROC [graph: Graph, enumNode: EnumNodeProc] RETURNS [quit: BOOLEANFALSE];
EnumArcProc: TYPE = PROC[graph: Graph, arc: Arc] RETURNS [quit: BOOLEANFALSE];
EnumArcs: PROC [graph: Graph, enumArc: EnumArcProc] RETURNS [quit: BOOLEANFALSE];
EnumArcsFromNodeProc: TYPE = PROC[graph: Graph, arc: Arc, node: Node, direction: Direction] RETURNS [quit: BOOLEANFALSE];
EnumArcsFromNode: PROC [graph: Graph, node: Node, direction: DirectionOrBoth, enumArc: EnumArcsFromNodeProc] RETURNS [quit: BOOLEANFALSE];
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.