DIRECTORY Asserting, GraphOps, Graphs, Rope; GraphOpsImpl: CEDAR PROGRAM IMPORTS Asserting, Graphs EXPORTS GraphOps = BEGIN OPEN Graphs, GraphOps; ranks: ARRAY DirectedDirection OF ATOM = [$IncomingRank, $OutgoingRank]; GraphRanked: PUBLIC PROC [g: Graph, d: DirectedDirection] RETURNS [BOOL] = { RETURN [Asserting.FnVal[ranks[d], g.other] = $TRUE]; }; RankGraph: PUBLIC PROC [g: Graph, d: DirectedDirection] = { filter: EdgeFilter _ ALL[FALSE]; ClearRank: Graphs.VertexConsumerProc = {SetRank[vertex, d, notRanked]}; EnsureRanked: Graphs.VertexConsumerProc = { rank: INT _ 0; RankProvider: Graphs.EdgeConsumerProc = { w: Vertex = edge.otherSide; IF VertexRank[w, d] = ranking THEN ERROR--discovered cycle in graph--; EnsureRanked[w]; rank _ MAX[rank, VertexRank[w, d]+1]; }; IF VertexRank[vertex, d] # notRanked THEN RETURN; rank _ 0; SetRank[vertex, d, ranking]; TRUSTED {Expand[vertex, [RankProvider], filter]}; SetRank[vertex, d, rank] }; filter[d] _ TRUE; TRUSTED {EnumerateVertices[g, [ClearRank] ] }; TRUSTED {EnumerateVertices[g, [EnsureRanked] ] }; g.other _ Asserting.AssertFn1[fn: ranks[d], val: $TRUE, inAdditionTo: g.other, mayMute: TRUE]; }; notRanked: INT = FIRST[INT]; ranking: INT = notRanked+1; SetRank: PROC [v: Vertex, d: DirectedDirection, rank: INT] = { v.other _ Asserting.AssertFn1[fn: ranks[d], val: NEW [INT _ rank], inAdditionTo: v.other, mayMute: TRUE]; }; VertexRank: PUBLIC PROC [v: Vertex, d: DirectedDirection] RETURNS [rank: INT] = { ra: REF ANY = Asserting.FnVal[ranks[d], v.other]; rank _ WITH ra SELECT FROM x: REF INT => x^, ENDCASE => notRanked; }; components: ARRAY Direction OF ATOM = [$UndirectedComponent, $IncomingComponent, $OutgoingComponent]; DetermineComponents: PUBLIC PROC [g: Graph, d: Direction, predicate: EdgePredicate _ NIL] RETURNS[numComponents: CARDINAL _ 0] ~ { filter: EdgeFilter _ ALL[FALSE]; ClearComponent: Graphs.VertexConsumerProc = {SetComponent[vertex, d, componentNotDetermined]}; Component: PROC [v: Vertex, comp: CARDINAL] = { NeighborProc: Graphs.EdgeConsumerProc ~ { w: Vertex = edge.otherSide; IF VertexComponent[w, d] = componentNotDetermined THEN IF predicate[v, w] THEN Component[w, comp]; }; SetComponent[v, d, comp]; TRUSTED {Expand[v, [NeighborProc], filter]}; }; EnumerateProc: Graphs.VertexConsumerProc = { IF VertexComponent[vertex, d] = componentNotDetermined THEN { numComponents _ numComponents + 1; Component[vertex, numComponents]; }; }; IF d # Undirected THEN filter[d] _ TRUE ELSE filter _ ALL[TRUE]; TRUSTED {EnumerateVertices[g, [EnumerateProc] ]}; g.other _ Asserting.AssertFn1[fn: components[d], val: $TRUE, inAdditionTo: g.other, mayMute: TRUE]; RETURN[numComponents]; }; componentNotDetermined: CARDINAL = 0; ComponentsDetermined: PUBLIC PROC [g: Graph, d: Direction] RETURNS [BOOL] ~ { RETURN [Asserting.FnVal[components[d], g.other] = $TRUE]; }; SetComponent: PROC [v: Vertex, d: Direction, component: CARDINAL] = { v.other _ Asserting.AssertFn1[fn: components[d], val: NEW [CARDINAL _ component], inAdditionTo: v.other, mayMute: TRUE]; }; VertexComponent: PUBLIC PROC [v: Vertex, d: Direction] RETURNS [component: CARDINAL] ~ { comp: REF ANY = Asserting.FnVal[components[d], v.other]; component _ WITH comp SELECT FROM x: REF CARDINAL => x^, ENDCASE => componentNotDetermined; }; END. ŒGraphOpsImpl.mesa Mike Spreitzer August 21, 1986 4:56:14 pm PDT Dennis Arnon September 11, 1986 12:22:23 pm PDT Connected Components ΚS– "cedar" style˜code™K™-K™/—K˜KšΟk œ#˜,K˜šΟn œœ˜Kšœ˜Kšœ ˜K˜—K˜Kšœœ˜K˜Kšœœœœ"˜HK˜š ž œœœ"œœ˜LKšœ.˜4K˜—K˜šž œœœ%˜;Kšœœœ˜ Kšž œ>˜Gšž œ˜+Kšœœ˜šž œ˜)K˜KšœœΟcœ˜FK˜Jšœœ˜%K˜—Kšœ#œœ˜1K˜ Kšœ˜Kšœ*˜1Kšœ˜K˜—Kšœ œ˜Kšœ.˜.Kšœ1˜1KšœXœ˜^K˜—K˜Kšœ œœœ˜Kšœ œ˜K˜šžœœ)œ˜>K•StartOfExpansion‹[fn: Asserting.Term, val: Asserting.Term, inAdditionTo: Asserting.Assertions, args: Asserting.Terms _ NIL, mayMute: BOOL _ FALSE]šœ1œœ*œ˜iK˜—K˜š ž œœœ#œœ˜QK–‹[fn: Asserting.Term, val: Asserting.Term, inAdditionTo: Asserting.Assertions, args: Asserting.Terms _ NIL, mayMute: BOOL _ FALSE]šœœœ&˜1šœœœ˜Kšœœœ˜Kšœ˜—K˜—head™Kšœ œ œœB˜eK˜š žœœœ5œœœ ˜‚Kšœœœ˜ KšžœP˜^šž œœœ˜/šž œ˜)K˜šœ0œ˜7Kšœœ˜+—K˜—Kšœ˜Kšœ%˜,K˜—šž œ˜,šœ5œ˜=Kšœ"˜"Kšœ!˜!K˜—K˜—Kš œœ œœ œœ˜@Kšœ*˜1Kšœ]œ˜cKšœ˜K˜K˜—Kšœœ˜%K˜š žœœœœœ˜MKšœ3˜9K˜K˜K˜—šž œœ&œ˜EK–‹[fn: Asserting.Term, val: Asserting.Term, inAdditionTo: Asserting.Assertions, args: Asserting.Terms _ NIL, mayMute: BOOL _ FALSE]šœ6œœ/œ˜xK˜—K˜š žœœœœ œ˜YK–‹[fn: Asserting.Term, val: Asserting.Term, inAdditionTo: Asserting.Assertions, args: Asserting.Terms _ NIL, mayMute: BOOL _ FALSE]šœœœ+˜8šœ œœ˜!Kšœœœ˜Kšœ˜"—K˜K˜——K˜Kšœ˜—…— ζΕ