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. HGraphsImpl.Mesa Mike Spreitzer September 27, 1986 3:13:40 pm PDT Κ”– "cedar" style˜™Icode™0—J˜KšΟk œ˜"K˜šΡbnx œœ˜Kšœ˜Kšœ ˜—K˜Kšœœ˜K˜Kš Οnœœœœœœ˜>Kš Ÿ œœœ œœ˜DK˜šŸ œœœΟcœ˜BKšœœœœ ˜OK˜—K˜š Ÿ œœœœœ œ˜[Kšœœœœœœœœœ ˜ƒK˜—K˜š Ÿ œœœ œœ œ˜QKš œœœœœ ˜CK˜—K˜š Ÿœœœ œ œ˜hKšŸœœœœ˜_Kšœœœœœœœœ œ˜K˜—K˜šŸœœœ Ÿœœœ œ˜ŒKšœœœ œ ˜RK˜—K˜š Ÿœœœœ œ˜^Kš œœœœœ ˜YKšœ˜—K˜š ŸœœœŸœ9 œ˜wKšœœœ.œ ˜`K˜—K˜š ŸœœœŸœ: œ˜‰Kš œœ#œœ!œ7˜ŠKšœ˜—K˜š ŸœœœŸœ: œ˜“šŸœœ:˜GKšœC˜C—Kšœ ˜ Kšœ˜—K˜š Ÿ œœœ™œ  œ˜ξKš œœœœœM˜₯K˜—K˜š Ÿœœœ™œ  œ˜ψKšœœ˜ K˜šŸœœ:˜GKšœœœœ˜$Kšœœœœ˜7šœœ˜Kšœœœ ˜;Kšœœœ%˜DKšœœœ.˜M—šœœ˜Kšœœ3˜GKšœ ˜ Kšœ˜Kšœ˜—Kšœœœ˜Kšœœœœ+˜xK˜—Kšœ˜Kšœ)œ˜3K˜ K˜KšŸœœœ˜—K˜š Ÿœœœ;œœ œ˜ŽKšœœ!œœœœ#œœœ-˜ΪK˜—K˜š Ÿœœœ;œœ œ˜˜šŸœœ:˜HKšœ"˜"K˜—Kšœ˜Kšœ:˜:K˜—K˜š Ÿœœœ;œœ œ˜˜šŸœœ:˜GKšœ"˜"K˜—Kšœ˜Kšœ-˜-K˜—K˜š ŸœœœSœ  œ˜Kšœœœ:œœœœLœ ˜ΨK˜—K˜šŸœœœœ˜SKšœœ˜$K˜—K˜šŸ œœœ  œ˜5Kšœœœœ˜A—K˜š Ÿ œœœ œ  œ˜OKš œœœœœ ˜G—K˜š Ÿ œœœ œ œ˜bKšŸœœœœ˜^Kšœœœœœœœœ ˜ŽK˜—K˜šŸœœœ Ÿœœœ œ˜†Kšœœœ œ ˜RK˜—K˜šŸ œœœœ˜MKšœœ˜#—K˜Kš œ)ŸœœŸ œœ˜IKšœ œ œ˜-K˜š Ÿ œœœ œ œ˜dKšŸœœœœ˜^Kšœœœœœœœœ œ˜K˜—K˜šŸœœœ Ÿœœœ œ˜†Kšœœœ œ˜S—K˜š ŸœœœŸœœ˜IKšœ.˜.K˜—K˜šŸ œœœ˜,Kšœœœ˜=K˜—K˜šŸ œœœœ˜NKšœœ˜!K˜—K˜š Ÿœœœœ3œœ+˜‘Kšœ*œ˜L—K˜š Ÿ œœœœœ˜ZKšœœœ˜)šœœœ˜Kšœœ ˜Kšœœ˜—K˜—K˜Kšœ˜—…—'l