<> <> DIRECTORY Asserting, Graphs, Rope; GraphsImpl: CEDAR PROGRAM IMPORTS Asserting, Rope EXPORTS Graphs = BEGIN OPEN Graphs; Error: PUBLIC ERROR [code: ErrorCode, msg: ROPE _ NIL] = CODE; ErrorCodeName: PUBLIC ARRAY ErrorCode OF ROPE _ ["Cant", "BadArgs"]; DeleteVertex: PUBLIC PROC [vertex: Vertex] --VertexDestroyer-- = { IF vertex.class.Delete # NIL THEN vertex.class.Delete[vertex] ELSE Error[Cant]; }; EqualVertices: PUBLIC PROC [v1, v2: Vertex] RETURNS [eq: BOOL] --VertexEqualityTester-- = { eq _ IF v1.class.Equal # NIL THEN v1.class.Equal[v1, v2] ELSE IF v2.class.Equal # NIL THEN v2.class.Equal[v2, v1] ELSE Error[Cant]; }; HashVertex: PUBLIC PROC [v: Vertex] RETURNS [hash: CARDINAL] --VertexHasher-- = { hash _ IF v.class.Hash # NIL THEN v.class.Hash[v] ELSE Error[Cant]; }; GetVertexOther: PUBLIC PROC [v: Vertex] RETURNS [other: Asserting.Assertions] --VertexGetOtherProc-- = { Give: PROC [got: Asserting.Assertions] RETURNS [Asserting.Assertions] = {RETURN [other _ got]}; IF v.class.GetOther # NIL THEN other _ v.class.GetOther[v] ELSE IF v.class.ChangeOther # NIL THEN v.class.ChangeOther[v, Give] ELSE other _ NIL; }; ChangeVertexOther: PUBLIC PROC [v: Vertex, Change: PROC [Asserting.Assertions] RETURNS [Asserting.Assertions]] --VertexChangeOtherProc-- = { IF v.class.ChangeOther # NIL THEN v.class.ChangeOther[v, Change] ELSE Error[Cant]; }; GetVertexLabel: PUBLIC PROC [vertex: Vertex] RETURNS [label: Label] --VertexGetLabelProc-- = { label _ IF vertex.class.GetLabel # NIL THEN vertex.class.GetLabel[vertex] ELSE unlabeled; }; Expand: PUBLIC PROC [vertex: Vertex, Consume: EdgeConsumer, filter: DirectionFilter _ allDirections] --ExpandProc-- = { IF vertex.class.Expand # NIL THEN vertex.class.Expand[vertex, Consume, filter] ELSE Error[Cant]; }; EnumerateForLabels: PUBLIC PROC [vertex: Vertex, Consume: LabelConsumer, filter: DirectionFilter _ allDirections] --LabelEnumerator-- = { (IF vertex.class.EnumerateForLabels # NIL THEN vertex.class.EnumerateForLabels ELSE EnumerateForLabelsFromExpand)[vertex, Consume, filter] }; EnumerateForLabelsFromExpand: PUBLIC PROC [vertex: Vertex, Consume: LabelConsumer, filter: DirectionFilter _ allDirections] --LabelEnumerator-- = { PerEdge: PROC [edge: Edge, direction: Direction, otherSide: Vertex] = { Consume[direction, GetEdgeLabel[edge], GetVertexLabel[otherSide]]}; Expand[vertex, PerEdge, filter]; }; GetNeighbor: PUBLIC PROC [vertex: Vertex, filter: DirectionFilter _ allDirections, edgeLabel, vertexLabel: Label _ unlabeled, index: Index _ noIndex, goal: Vertex _ nullVertex] RETURNS [edge: Edge, neighbor: Vertex] --NeighborGetter-- = { [edge, neighbor] _ (IF vertex.class.GetNeighbor # NIL THEN vertex.class.GetNeighbor ELSE GetNeighborFromExpand)[vertex, filter, edgeLabel, vertexLabel, index, goal]; }; GetNeighborFromExpand: PUBLIC PROC [vertex: Vertex, filter: DirectionFilter _ allDirections, edgeLabel, vertexLabel: Label _ unlabeled, index: Index _ noIndex, goal: Vertex _ nullVertex] RETURNS [edge: Edge, neighbor: Vertex] --NeighborGetter-- = { i: INT _ 0; ans: Edge _ nullEdge; PerEdge: PROC [edge: Edge, direction: Direction, otherSide: Vertex] = { IF NOT filter[direction] THEN ERROR; IF index # noIndex AND index # (i _ i + 1) THEN RETURN; {inconsistent: BOOL = goal # nullVertex AND NOT EqualVertices[otherSide, goal] OR edgeLabel # unlabeled AND NOT GetEdgeLabel[edge].Equal[edgeLabel] OR vertexLabel # unlabeled AND NOT GetVertexLabel[otherSide].Equal[vertexLabel]; IF index # noIndex THEN { IF inconsistent THEN Error[BadArgs, "Inconsistent edge specification"]; ans _ edge; neighbor _ goal; Abort}; IF inconsistent THEN RETURN; IF goal # nullVertex OR edgeLabel # unlabeled OR vertexLabel # unlabeled THEN {ans _ edge; neighbor _ otherSide; Abort}; }}; neighbor _ nullVertex; Expand[vertex, PerEdge, filter !Abort => CONTINUE]; edge _ ans; }; Abort: ERROR = CODE; GetNeighborCount: PUBLIC PROC [vertex: Vertex, filter: DirectionFilter _ allDirections] RETURNS [neighborCount: INT] --NeighborCountProc-- = { neighborCount _ (IF vertex.class.GetNeighborCount # NIL THEN vertex.class.GetNeighborCount ELSE IF vertex.class.EnumerateForLabels # NIL THEN GetNeighborCountFromLabels ELSE GetNeighborCountFromExpand)[vertex, filter]; }; GetNeighborCountFromLabels: PUBLIC PROC [vertex: Vertex, filter: DirectionFilter _ allDirections] RETURNS [neighborCount: INT] --NeighborCountProc-- = { PerLabel: PROC [direction: Direction, edgeLabel, vertexLabel: Label] = { neighborCount _ neighborCount + 1; }; neighborCount _ 0; vertex.class.EnumerateForLabels[vertex, PerLabel, filter]; }; GetNeighborCountFromExpand: PUBLIC PROC [vertex: Vertex, filter: DirectionFilter _ allDirections] RETURNS [neighborCount: INT] --NeighborCountProc-- = { PerEdge: PROC [edge: Edge, direction: Direction, otherSide: Vertex] = { neighborCount _ neighborCount + 1; }; neighborCount _ 0; vertex.class.Expand[vertex, PerEdge, filter]; }; AddEdge: PUBLIC PROC [v1, v2: Vertex, direction: Direction, label: Label, other: Asserting.Assertions] RETURNS [edge: Edge] --EdgeAdder-- = { IF v1.class.AddEdge # NIL THEN edge _ v1.class.AddEdge[v1, v2, direction, label, other] ELSE IF v2.class.AddEdge # NIL THEN edge _ v2.class.AddEdge[v2, v1, ReverseDirection[direction], label, other] ELSE Error[Cant]; }; NewVertexClass: PUBLIC PROC [vtp: VertexClassPrivate] RETURNS [vt: VertexClass] = { vt _ NEW [VertexClassPrivate _ vtp]; }; DeleteEdge: PUBLIC PROC [e: Edge] --EdgeDeleter-- = { IF e.class.Delete # NIL THEN e.class.Delete[e] ELSE Error[Cant]}; GetEdgeLabel: PUBLIC PROC [e: Edge] RETURNS [l: Label] --EdgeGetLabelProc-- = { l _ IF e.class.GetLabel # NIL THEN e.class.GetLabel[e] ELSE unlabeled}; GetEdgeOther: PUBLIC PROC [e: Edge] RETURNS [other: Asserting.Assertions] --EdgeGetOtherProc-- = { Get: PROC [got: Asserting.Assertions] RETURNS [Asserting.Assertions] = {RETURN [other _ got]}; IF e.class.GetOther # NIL THEN other _ e.class.GetOther[e] ELSE IF e.class.ChangeOther # NIL THEN e.class.ChangeOther[e, Get] ELSE other _ NIL }; ChangeEdgeOther: PUBLIC PROC [e: Edge, Change: PROC [Asserting.Assertions] RETURNS [Asserting.Assertions]] --EdgeChangeOtherProc-- = { IF e.class.ChangeOther # NIL THEN e.class.ChangeOther[e, Change] ELSE Error[Cant]; }; NewEdgeClass: PUBLIC PROC [ecp: EdgeClassPrivate] RETURNS [ec: EdgeClass] = { ec _ NEW [EdgeClassPrivate _ ecp]}; dullEdgeClass: EdgeClass = NewEdgeClass[[Delete: NIL, ChangeOther: NIL]]; dullEdge: PUBLIC Edge _ [NIL, dullEdgeClass]; GetGraphOther: PUBLIC PROC [g: Graph] RETURNS [other: Asserting.Assertions] --GraphOtherGetter-- = { Get: PROC [got: Asserting.Assertions] RETURNS [Asserting.Assertions] = {RETURN [other _ got]}; IF g.class.GetOther # NIL THEN other _ g.class.GetOther[g] ELSE IF g.class.ChangeOther # NIL THEN g.class.ChangeOther[g, Get] ELSE other _ NIL; }; ChangeGraphOther: PUBLIC PROC [g: Graph, Change: PROC [Asserting.Assertions] RETURNS [Asserting.Assertions]] --GraphOtherChanger-- = { IF g.class.ChangeOther # NIL THEN g.class.ChangeOther[g, Change] ELSE Error[Cant]}; EnumerateVertices: PUBLIC PROC [graph: Graph, Consume: PROC [Vertex]] = { graph.class.EnumerateVertices[graph, Consume]; }; DestroyGraph: PUBLIC PROC [graph: Graph] = { IF graph.class.Destroy # NIL THEN graph.class.Destroy[graph]; }; NewGraphClass: PUBLIC PROC [gp: GraphClassPrivate] RETURNS [g: GraphClass] = { g _ NEW [GraphClassPrivate _ gp]; }; AssertOtherProc: PUBLIC PROC [key: ATOM, proc: Proc, inAdditionTo: Asserting.Assertions _ NIL] RETURNS [allTogetherNow: Asserting.Assertions] = { allTogetherNow _ Asserting.AssertFn1[key, NEW [Proc _ proc], inAdditionTo]}; GetOtherProc: PUBLIC PROC [key: ATOM, from: Asserting.Assertions] RETURNS [proc: Proc] = { rp: REF ANY = Asserting.FnVal[key, from]; proc _ WITH rp SELECT FROM x: REF Proc => x^, ENDCASE => NIL; }; END.