DIRECTORY PropertyLists; Graphs0: CEDAR DEFINITIONS = BEGIN 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]; Destroy: PROC [graph: Graph]; 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 ]; CreateNode: PROC [nodeInfo: REF _ NIL] RETURNS [node: Node]; IncludeNode: PROC [graph: Graph, node: Node]; RemoveNode: PROC [graph: Graph, node: Node] RETURNS [removedArcs: ArcList]; AddNewNode: PROC [graph: Graph, nodeInfo: REF _ NIL] RETURNS [node: 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]; IncludeArc: PROC [graph: Graph, arc: Arc, node1, node2: Node]; RemoveArc: PROC [graph: Graph, arc: Arc]; AddNewArc: PROC [graph: Graph, arcInfo: REF _ NIL, node1, node2: Node] RETURNS [arc: 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]; 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]; HasNode: PROC [graph: Graph, node: Node] RETURNS [BOOL]; HasArc: PROC [graph: Graph, arc: Arc] RETURNS [BOOL]; NodesInGraph: PROC [graph: Graph] RETURNS [INT]; ArcsInGraph: PROC [graph: Graph] RETURNS [INT]; RandomShuffle: PROC [graph: Graph, randomStream: REF_NIL]; Check: PROC [graph: Graph]; END. hGraphs0.mesa Copyright c 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 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. Creates a new, empty 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. Don't cache the arcs LIST: it might be modified whenever the graph is modified Creates a new node. The node is not yet included into any graph. Includes a node into a graph. If the node has arc fields, they are nilled out before including. 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. Shortcut procedure, creates and includes node Creates a new arc. The arc is not yet included into any graph. 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. 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. Shortcut procedure, creates and includes arc. Enumerates nodes in unspecified order. Nodes included while enumeration is taking place may or may not be seen. Enumerates arcs in unspecified order. Arcs included while enumeration is taking place may or may not be seen. Returns whether a node is included in a particular graph. Returns whether an arc is included in a particular graph. Returns number of nodes in graph. Returns number of arcs in graph. 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. 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. ΚΙ˜codešœ ™ Kšœ Οmœ1™K™NK™9—K˜šŸ œžœ˜)KšœU™UKšœ>™>KšœQ™QKšœ˜—š Ÿ œžœžœžœžœ ˜ZK™-—K™K™Kš œžœžœ!žœžœžœžœ˜\šŸ œžœ.žœžœžœžœžœ˜cKšœ&™&K™H—K˜Kš œ žœžœžœžœžœžœ˜YšŸœžœ,žœžœžœžœžœ˜`Kšœ%™%K™G—K™K˜šŸœžœžœžœ˜8K™9K™—šŸœžœžœžœ˜5K™9—K™K˜šŸ œžœžœžœ˜0K™!—K˜šŸ œžœžœžœ˜/K™ —K˜K˜šŸ œžœžœžœ˜:K™GK™HKšΟbœ<™DKšœ™Kšœ)™)—K˜šŸœžœ˜K™K™OK™JK™.—K˜Kšžœ˜—…—1