DIRECTORY Asserting, Rope; Graphs: CEDAR DEFINITIONS = { ROPE: TYPE = Rope.ROPE; Error: ERROR [code: ErrorCode, msg: ROPE _ NIL]; ErrorCode: TYPE = { Cant--someone asked for an operation not supported by this graph/vertex/edge--, BadArgs--the usual-- }; ErrorCodeName: READONLY ARRAY ErrorCode OF ROPE; Label: TYPE = ROPE _ NIL; unlabeled: Label = NIL; Vertex: TYPE = RECORD [rep: REF ANY, class: VertexClass]; nullVertex: Vertex = [NIL, NIL]; DeleteVertex: VertexDeleter; VertexDeleter: TYPE = PROC [vertex: Vertex]; EqualVertices: VertexEqualityTester; VertexEqualityTester: TYPE = PROC [Vertex, Vertex] RETURNS [BOOL]; HashVertex: VertexHasher; VertexHasher: TYPE = PROC [Vertex] RETURNS [CARDINAL]; GetVertexOther: VertexGetOtherProc; VertexGetOtherProc: TYPE = PROC [Vertex] RETURNS [Asserting.Assertions]; ChangeVertexOther: VertexChangeOtherProc; VertexChangeOtherProc: TYPE = PROC [Vertex, PROC [Asserting.Assertions] RETURNS [Asserting.Assertions]]; GetVertexLabel: VertexGetLabelProc; VertexGetLabelProc: TYPE = PROC [vertex: Vertex] RETURNS [label: Label]; Expand: ExpandProc; ExpandProc: TYPE = PROC [vertex: Vertex, Consume: EdgeConsumer, filter: DirectionFilter _ allDirections]; EdgeConsumer: TYPE = PROC [edge: Edge, direction: Direction, otherSide: Vertex]; EnumerateForLabels: LabelEnumerator; EnumerateForLabelsFromExpand: LabelEnumerator; LabelEnumerator: TYPE = PROC [vertex: Vertex, Consume: LabelConsumer, filter: DirectionFilter _ allDirections]; LabelConsumer: TYPE = PROC [direction: Direction, edgeLabel, vertexLabel: Label]; GetNeighbor: NeighborGetter; GetNeighborFromExpand: NeighborGetter; NeighborGetter: TYPE = PROC [vertex: Vertex, filter: DirectionFilter _ allDirections, edgeLabel, vertexLabel: Label _ unlabeled, index: Index _ noIndex, goal: Vertex _ nullVertex] RETURNS [edge: Edge, neighbor: Vertex]; Index: TYPE = INT--origin 1--; noIndex: INT = FIRST[INT]; GetNeighborCount: NeighborCountProc; GetNeighborCountFromLabels: NeighborCountProc; GetNeighborCountFromExpand: NeighborCountProc; NeighborCountProc: TYPE = PROC [vertex: Vertex, filter: DirectionFilter _ allDirections] RETURNS [neighborCount: INT]; AddEdge: EdgeAdder; EdgeAdder: TYPE = PROC [v1, v2: Vertex, direction: Direction, label: Label, other: Asserting.Assertions] RETURNS [edge: Edge]; VertexClass: TYPE = REF VertexClassPrivate; VertexClassPrivate: TYPE = RECORD [ data: REF ANY _ NIL, Delete: VertexDeleter, Equal: VertexEqualityTester, Hash: VertexHasher, GetOther: VertexGetOtherProc _ NIL, ChangeOther: VertexChangeOtherProc, GetLabel: VertexGetLabelProc _ NIL--means unlabelled--, Expand: ExpandProc, EnumerateForLabels: LabelEnumerator _ NIL, GetNeighbor: NeighborGetter _ NIL, GetNeighborCount: NeighborCountProc _ NIL, AddEdge: EdgeAdder, other: Asserting.Assertions _ NIL ]; NewVertexClass: PROC [vtp: VertexClassPrivate] RETURNS [vt: VertexClass]; DirectionFilter: TYPE = ARRAY Direction OF BOOL; allDirections: DirectionFilter = ALL[TRUE]; Only: ARRAY Direction OF DirectionFilter = [ Undirected: [TRUE, FALSE, FALSE], Incoming: [FALSE, TRUE, FALSE], Outgoing: [FALSE, FALSE, TRUE]]; AllBut: ARRAY Direction OF DirectionFilter = [ Undirected: [FALSE, TRUE, TRUE], Incoming: [TRUE, FALSE, TRUE], Outgoing: [TRUE, TRUE, FALSE]]; Direction: TYPE = {Undirected, Incoming, Outgoing}; DirectedDirection: TYPE = Direction[Incoming .. Outgoing]; ReverseDirection: ARRAY Direction OF Direction = [Undirected, Outgoing, Incoming]; Edge: TYPE = RECORD [rep: REF ANY, class: EdgeClass]; nullEdge: Edge = [NIL, NIL]; dullEdge: READONLY Edge; DeleteEdge: EdgeDeleter; EdgeDeleter: TYPE = PROC [Edge]; GetEdgeLabel: EdgeGetLabelProc; EdgeGetLabelProc: TYPE = PROC [Edge] RETURNS [Label]; GetEdgeOther: EdgeGetOtherProc; EdgeGetOtherProc: TYPE = PROC [Edge] RETURNS [Asserting.Assertions]; ChangeEdgeOther: EdgeChangeOtherProc; EdgeChangeOtherProc: TYPE = PROC [Edge, PROC [Asserting.Assertions] RETURNS [Asserting.Assertions]]; EdgeClass: TYPE = REF EdgeClassPrivate; EdgeClassPrivate: TYPE = RECORD [ Delete: EdgeDeleter, GetLabel: EdgeGetLabelProc _ NIL--means unlabeled--, GetOther: EdgeGetOtherProc _ NIL, ChangeOther: EdgeChangeOtherProc ]; NewEdgeClass: PROC [ecp: EdgeClassPrivate] RETURNS [ec: EdgeClass]; Graph: TYPE = RECORD [rep: REF ANY, class: GraphClass]; GetGraphOther: GraphOtherGetter; GraphOtherGetter: TYPE = PROC [Graph] RETURNS [Asserting.Assertions]; ChangeGraphOther: GraphOtherChanger; GraphOtherChanger: TYPE = PROC [Graph, PROC [Asserting.Assertions] RETURNS [Asserting.Assertions]]; EnumerateVertices: GraphEnumerator; GraphEnumerator: TYPE = PROC [graph: Graph, Consume: PROC [Vertex]]; DestroyGraph: GraphDestroyer; GraphDestroyer: TYPE = PROC [graph: Graph]; GraphClass: TYPE = REF GraphClassPrivate; GraphClassPrivate: TYPE = RECORD [ GetOther: GraphOtherGetter _ NIL, ChangeOther: GraphOtherChanger, EnumerateVertices: GraphEnumerator, Destroy: GraphDestroyer _ NIL--NIL means just drop it on the floor-- ]; NewGraphClass: PROC [gp: GraphClassPrivate] RETURNS [g: GraphClass]; Proc: TYPE = PROC ANY RETURNS ANY; AssertOtherProc: PROC [key: ATOM, proc: Proc, inAdditionTo: Asserting.Assertions _ NIL] RETURNS [allTogetherNow: Asserting.Assertions]; GetOtherProc: PROC [key: ATOM, from: Asserting.Assertions] RETURNS [proc: Proc]; }. ²Graphs.Mesa Mike Spreitzer September 27, 1986 3:11:50 pm PDT This interface defines an abstract data-type for graphs. A graph has a set of vertices, and edges between the vertices. The edges may or may not be directed. The edges and the vertices may or may not be labelled; if they are, the labels are ROPEs. Other interfaces may be defined with a richer structure, built on top of these graphs. The implementor of a graph vertex uses the `rep' and `class' fields. A client of a graph deals with a vertex through the vertex class procedures, or the procedures in this interface. The structure of a graph is revealed through the class procedures of the vertices of the graph. Some of the class procedures can be derived from others. The class has slots for the derivatives because they can sometimes be computed more cheaply than by the obvious derivation from the basic procedures. An implementor of a class of vertex that can compute the derivatives more cheaply should provide them. An implementor of a class that cannot compute the derivatives more cheaply need not provide them. Clients can call the procedures in this interface, rather than calling the class procedures directly. The procedures in this interface will derive themselves from the provided class procedures in the most efficient way. On the other hand, if a client is interested in some derivative procedure that has not been provided for in this interface, it must be synthesized by the client from the procedures in the vertex class and the procedures in this interface. An implementor of a graph vertex class is not even obliged to provide all of the basic procedures. Clients and users must be aware that not all graphs support all operations. Removes it from the graph. Useful for HashTable clients. Intended for retrieving a unique edge identified by given information. If there is no such edge, NILs are returned. If the info does not uniquely identify an edge, Error may be raised, or any one of the suitable edges may be returned. The index takes the direction filter into account, but nothing else. If unlabeled is given, it means don't care about the label. Just does the NEW. Removes it from the graph. Just does the NEW. ÊU– "cedar" style˜™ Icode™0—J˜JšÏk œ˜J˜KšÑbnxœœ œ˜K˜IbodyšœÒ™ÒLšœ·™·L™ÉL™¯K˜Kšœœœ˜K˜KšÏnœœœœ˜0šœ œ˜KšœÏcJœ˜OKšœ  ˜K˜—K˜Kš Ÿ œœœ œœ˜0K˜Kšœœœœ˜Kšœœ˜K˜Kš œœœœœ˜9K˜Kšœœœ˜ K˜KšŸ œ˜šœœœ˜,K™—K˜KšŸ œ˜$Kš œœœœœ˜BK˜KšŸ œ˜š œœœ œœ˜6K™—K˜KšŸœ˜#Kšœœœ œ˜HK˜KšŸœ˜)Kš œœœ œœ˜hK˜KšŸœ˜#šœœœœ˜HK˜—KšŸœ ˜šœ œœR˜iK˜Kšœœœ7˜PK˜—KšŸœ˜$KšŸœ˜.šœœœS˜oK˜Kšœœœ7˜Q—K˜KšŸ œ˜KšŸœ˜&šœœœ™œ ˜ÛKšœ‹Ïeœ¡œŒ¡ œ/™ïK˜Kšœœ  œ˜Kšœ œœœ˜K˜—KšŸœ˜$KšŸœ˜.KšŸœ˜.Kš œœœ;œœ˜vK˜KšŸœ ˜Kšœ œœSœ˜~K˜Kšœ œœ˜+šœœœ˜#Kšœœœœ˜KšŸœ˜KšŸœ˜KšŸœ˜KšŸœœ˜#KšŸ œ˜#KšŸœ œ˜7KšŸœ ˜KšŸœœ˜*KšŸ œœ˜"KšŸœœ˜*KšŸœ ˜Kšœ˜!K˜—K˜šŸœœœ˜IK™—K˜Kš œœœ œœ˜0Kšœ!œœ˜+šŸœœ œ˜,Kšœ œœœ˜!Kšœ œœœ˜Kšœ œœœ˜ —šŸœœ œ˜.Kšœ œœœ˜ Kšœ œœœ˜Kšœ œœœ˜—K˜Kšœ œ$˜3Kšœœ#˜:KšŸœœ œ.˜RK˜Kš œœœœœ˜5Kšœœœ˜Kšœ œ˜K˜KšŸ œ˜šœ œœ˜ K™—K˜KšŸ œ˜Kšœœœœ ˜5K˜KšŸ œ˜Kšœœœœ˜DK˜KšŸœ˜%Kš œœœœœ˜dK˜Kšœ œœ˜'šœœœ˜!KšŸœ˜KšŸœ œ˜4KšŸœœ˜!KšŸ œ˜ K˜—K˜KšŸ œœœ˜CK˜Kš œœœœœ˜7K˜KšŸ œ˜ Kšœœœ œ˜EK˜KšŸœ˜$Kš œœœ œœ˜cK˜KšŸœ˜#Kš œœœŸœœ ˜DK˜KšŸ œ˜Kšœœœ˜+K˜Kšœ œœ˜)šœœœ˜"KšŸœœ˜!KšŸ œ˜KšŸœ˜#KšŸœ '˜DK˜—K˜šŸ œœœ˜DK™—K˜Kš œœœœœœ˜"K˜Kš Ÿœœœ3œœ(˜‡KšŸ œœœœ˜PK˜Kšœ˜—…—Ä$Ë