[Cyan]<CedarChest6.1>Graphs>Graphs.Mesa!6

Graphs.Mesa

Mike Spreitzer September 27, 1986 3:11:50 pm PDT

DIRECTORY Asserting, Rope;

Graphs: CEDAR DEFINITIONS = {

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.

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];

Removes it from the graph.

EqualVertices: VertexEqualityTester;

VertexEqualityTester: TYPE = PROC [Vertex, Vertex] RETURNS [BOOL];

HashVertex: VertexHasher;

VertexHasher: TYPE = PROC [Vertex] RETURNS [CARDINAL];

Useful for HashTable clients.

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];

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.

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];

Just does the NEW.

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];

Removes it from the graph.

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];

Just does the NEW.

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];