Graphs0.mesa
Copyright © 1986 by Xerox Corporation. All rights reserved.
Created by: Christian Jacobi, September 15, 1986 11:07:56 am PDT
Last edited by: Christian Jacobi, October 18, 1986 1:31:20 pm PDT
DIRECTORY PropertyLists;
Graphs0: CEDAR DEFINITIONS =
BEGIN
Abstraction to define and process undirected graphs.
The number in its name is to distinguish this package from arrogant or ignorant
packages which use the very rare name "Graph" in an unqualified manner.
This package assumes clients will respect requested invariants; it may or may not
check them; on detected violations an unqualified error is raised; on undetected
violations correct behaviour is not guaranteed.
This package assumes that clients use each graph in a non forked manner; there is no
protection against asynchrounous client access.
The property lists may be used by both, clients and implementors of this package;
clients may not mistreat them.
Properties pointing to the graph might introduce circularities; but are otherwise ok.
Neither a node nor an arc may be included into more than 1 graph.
If a node or an arc is part of a graph which is destroyed or garbage collected, the
arc, node, info and property fields in its representation record are nilled out.
Graph: TYPE = REF GraphRec;
GraphRec: TYPE = RECORD [--clients must never use NEW[GraphRec]
graphInfo: REF ← NIL,
graphPrivate: PRIVATE REF GraphPrivateRep ←,
props: PropertyLists.PropList ← NIL
];
GraphPrivateRep: TYPE;
Create: PROC [graphInfo: REF ← NIL] RETURNS [graph: Graph];
Creates a new, empty graph.
Destroy: PROC [graph: Graph];
Destroys graph, its arcs and node including properties, to brake any circularities.
As long as no client circularities exist, calling this procedure is optional.
Node: TYPE = REF NodeRec;
NodeList: TYPE = LIST OF Node;
NodeRec: TYPE = RECORD[
nodeInfo: REF ← NIL,
arcs: --READONLY-- ArcList ← NIL, --list and arc refs are readonly
incl: PRIVATE BOOL ← FALSE,
props: PropertyLists.PropList ← NIL
];
Don't cache the arcs LIST: it might be modified whenever the graph is modified
CreateNode: PROC [nodeInfo: REF ← NIL] RETURNS [node: Node];
Creates a new node. The node is not yet included into any graph.
IncludeNode: PROC [graph: Graph, node: Node];
Includes a node into a graph.
If the node has arc fields, they are nilled out before including.
RemoveNode: PROC [graph: Graph, node: Node] RETURNS [removedArcs: ArcList];
Removes a node from graph.
Returns the arcs which connects to this node; the arcs are also removed from the
graph, the removed arcs still contain the information to which node they were
connected before; the not removed nodes forget about the removed arcs.
The removed arcs are out of reach for the destroy or graph garbage collect cleanup.
AddNewNode: PROC [graph: Graph, nodeInfo: REF ← NIL] RETURNS [node: Node];
Shortcut procedure, creates and includes node
Arc: TYPE = REF ArcRec;
ArcList: TYPE = LIST OF Arc;
ArcRec: TYPE = RECORD[
arcInfo: REF ← NIL,
node1, node2: --READONLY-- Node ← NIL, --ref is readonly
incl: PRIVATE BOOL ← FALSE,
props: PropertyLists.PropList ← NIL
];
CreateArc: PROC [arcInfo: REF ← NIL] RETURNS [arc: Arc];
Creates a new arc. The arc is not yet included into any graph.
IncludeArc: PROC [graph: Graph, arc: Arc, node1, node2: Node];
Includes an arc into a graph. The nodes must be already included in the graph.
The arcs node fields are replaced by the parameter nodes.
RemoveArc: PROC [graph: Graph, arc: Arc];
Removes arc from graph and its nodes; the removed arc still contains the information
to which nodes it was connected, but the nodes forget the arc.
The removed arc is out of reach for the destroy or garbage collect graph cleanup.
AddNewArc: PROC [graph: Graph, arcInfo: REF ← NIL, node1, node2: Node] RETURNS [arc: Arc];
Shortcut procedure, creates and includes arc.
EnumNodeProc: TYPE = PROC[graph: Graph, node: Node, data: REF] RETURNS [quit: BOOL ← FALSE];
EnumNodes: PROC [graph: Graph, enumNode: EnumNodeProc, data: REF←NIL] RETURNS [quit: BOOL ← FALSE];
Enumerates nodes in unspecified order.
Nodes included while enumeration is taking place may or may not be seen.
EnumArcProc: TYPE = PROC[graph: Graph, arc: Arc, data: REF] RETURNS [quit: BOOL ← FALSE];
EnumArcs: PROC [graph: Graph, enumArc: EnumArcProc, data: REF←NIL] RETURNS [quit: BOOL ← FALSE];
Enumerates arcs in unspecified order.
Arcs included while enumeration is taking place may or may not be seen.
HasNode: PROC [graph: Graph, node: Node] RETURNS [BOOL];
Returns whether a node is included in a particular graph.
HasArc: PROC [graph: Graph, arc: Arc] RETURNS [BOOL];
Returns whether an arc is included in a particular graph.
NodesInGraph: PROC [graph: Graph] RETURNS [INT];
Returns number of nodes in graph.
ArcsInGraph: PROC [graph: Graph] RETURNS [INT];
Returns number of arcs in graph.
RandomShuffle: PROC [graph: Graph, randomStream: REF←NIL];
Shuffles the order of the arcs in a random manner: Useful to introduce
randomness into applications which depend on the order for enumerations.
Must not be called from inside EnumArcs or any procedure which loops
over the arcs of a node.
randomStream: Random.RandomStream or NIL.
Check: PROC [graph: Graph];
Client debugging aid.
Performs internal checks which could detect certain error conditions introduced
when a client did violate invariants specified in this definitions module.
If a violation is found, the procedure errors.
END.