DIRECTORY Asserting, GraphOps, Graphs, Rope; GraphOpsImpl: CEDAR PROGRAM IMPORTS Asserting, Graphs EXPORTS GraphOps = BEGIN OPEN Graphs, GraphOps; ranks: ARRAY DirectedDirection OF ATOM = [$IncomingRank, $OutgoingRank]; VertexRank: PUBLIC PROC [v: Vertex, d: DirectedDirection] RETURNS [rank: INT] = { ra: REF ANY = Asserting.FnVal[ranks[d], v.GetVertexOther[]]; rank _ WITH ra SELECT FROM x: REF INT => x^, ENDCASE => notRanked; }; SetRank: PROC [v: Vertex, d: DirectedDirection, rank: INT] = { Update: PROC [old: Asserting.Assertions] RETURNS [new: Asserting.Assertions] = { new _ Asserting.AssertFn1[fn: ranks[d], val: NEW [INT _ rank], inAdditionTo: old, mayMute: TRUE]}; v.ChangeVertexOther[Update]; }; GraphRanked: PUBLIC PROC [g: Graph, d: DirectedDirection] RETURNS [BOOL] = { RETURN [Asserting.FnVal[ranks[d], g.GetGraphOther[]] = $TRUE]; }; RankGraph: PUBLIC PROC [g: Graph, d: DirectedDirection] = { filter: DirectionFilter = Only[d]; ClearRank: PROC [v: Vertex] = {SetRank[v, d, notRanked]}; EnsureRanked: PROC [v: Vertex] = { rank: INT _ 0; RankProvider: PROC [edge: Edge, direction: Direction, otherSide: Vertex] = { w: Vertex = otherSide; IF VertexRank[w, d] = ranking THEN ERROR--discovered cycle in graph--; EnsureRanked[w]; rank _ MAX[rank, VertexRank[w, d]+1]; }; IF VertexRank[v, d] # notRanked THEN RETURN; rank _ 0; SetRank[v, d, ranking]; Expand[v, RankProvider, filter]; SetRank[v, d, rank] }; SetRanked: PROC [old: Asserting.Assertions] RETURNS [new: Asserting.Assertions] = {new _ Asserting.AssertFn1[fn: ranks[d], val: $TRUE, inAdditionTo: old, mayMute: TRUE]}; EnumerateVertices[g, ClearRank]; EnumerateVertices[g, EnsureRanked]; g.ChangeGraphOther[SetRanked]; }; notRanked: INT = FIRST[INT]; ranking: INT = notRanked+1; components: ARRAY Direction OF ATOM = [$UndirectedComponent, $IncomingComponent, $OutgoingComponent]; DetermineComponents: PUBLIC PROC [g: Graph, d: Direction, predicate: EdgePredicate _ NIL] RETURNS[numComponents: CARDINAL _ 0] ~ { filter: DirectionFilter = Only[d]; Component: PROC [v: Vertex, comp: CARDINAL] = { NeighborProc: PROC [edge: Edge, direction: Direction, otherSide: Vertex] ~ { w: Vertex = otherSide; IF VertexComponent[w, d] = componentNotDetermined THEN IF predicate[v, w] THEN Component[w, comp]; }; SetComponent[v, d, comp]; Expand[v, NeighborProc, filter]; }; EnumerateProc: PROC [vertex: Vertex] = { IF VertexComponent[vertex, d] = componentNotDetermined THEN { numComponents _ numComponents + 1; Component[vertex, numComponents]; }; }; SetComponented: PROC [old: Asserting.Assertions] RETURNS [new: Asserting.Assertions] = { new _ Asserting.AssertFn1[fn: components[d], val: $TRUE, inAdditionTo: old, mayMute: TRUE]}; EnumerateVertices[g, EnumerateProc]; g.ChangeGraphOther[SetComponented]; RETURN[numComponents]; }; componentNotDetermined: CARDINAL = 0; ComponentsDetermined: PUBLIC PROC [g: Graph, d: Direction] RETURNS [BOOL] ~ { RETURN [Asserting.FnVal[components[d], g.GetGraphOther[]] = $TRUE]; }; SetComponent: PROC [v: Vertex, d: Direction, component: CARDINAL] = { Set: PROC [old: Asserting.Assertions] RETURNS [new: Asserting.Assertions] = { new _ Asserting.AssertFn1[fn: components[d], val: NEW [CARDINAL _ component], inAdditionTo: old, mayMute: TRUE]}; v.ChangeVertexOther[Set]; }; VertexComponent: PUBLIC PROC [v: Vertex, d: Direction] RETURNS [component: CARDINAL] ~ { comp: REF ANY = Asserting.FnVal[components[d], v.GetVertexOther[]]; component _ WITH comp SELECT FROM x: REF CARDINAL => x^, ENDCASE => componentNotDetermined; }; END. fGraphOpsImpl.mesa Mike Spreitzer September 27, 1986 3:19:00 pm PDT Ranking Connected Components Κƒ– "cedar" style˜code™K™0—K˜KšΟk œ#˜,K˜šΟn œœ˜Kšœ˜Kšœ ˜K˜—K˜Kšœœ˜K˜head™Kšœœœœ"˜HK˜š ž œœœ#œœ˜QK•StartOfExpansion‹[fn: Asserting.Term, val: Asserting.Term, inAdditionTo: Asserting.Assertions, args: Asserting.Terms _ NIL, mayMute: BOOL _ FALSE]šœœœ1˜<šœœœ˜Kšœœœ˜Kšœ˜—K˜—K˜šžœœ)œ˜>–‹[fn: Asserting.Term, val: Asserting.Term, inAdditionTo: Asserting.Assertions, args: Asserting.Terms _ NIL, mayMute: BOOL _ FALSE]šžœœœ ˜PKšœ-œœ&œ˜b—Kšœ˜K˜—K˜š ž œœœ"œœ˜LKšœ8˜>K˜—K˜šž œœœ%˜;Kšœ"˜"Kšž œœ*˜9šž œœ˜"Kšœœ˜šž œœ:˜LKšœ˜KšœœΟcœ˜FK˜Jšœœ˜%K˜—Kšœœœ˜,K˜ Kšœ˜Kšœ ˜ Kšœ˜K˜—Kšž œœœpœ˜ͺKšœ ˜ Kšœ#˜#Kšœ˜K˜Kšœ œœœ˜Kšœ œ˜—K˜—™Kšœ œ œœB˜eK˜š žœœœ5œœœ ˜‚Kšœ"˜"šž œœœ˜/šž œœ:˜LKšœ˜šœ0œ˜7Kšœœ˜+—K˜—Kšœ˜Kšœ ˜ K˜—šž œœ˜(šœ5œ˜=Kšœ"˜"Kšœ!˜!K˜—K˜—šžœœœ ˜XKšœUœ˜\—Kšœ$˜$Kšœ#˜#Kšœ˜K˜K˜—Kšœœ˜%K˜š žœœœœœ˜MKšœ=˜CK˜K˜K˜—šž œœ&œ˜E–‹[fn: Asserting.Term, val: Asserting.Term, inAdditionTo: Asserting.Assertions, args: Asserting.Terms _ NIL, mayMute: BOOL _ FALSE]šžœœœ ˜MKšœ2œœ+œ˜q—Kšœ˜K˜—K˜š žœœœœ œ˜YK–‹[fn: Asserting.Term, val: Asserting.Term, inAdditionTo: Asserting.Assertions, args: Asserting.Terms _ NIL, mayMute: BOOL _ FALSE]šœœœ6˜Cšœ œœ˜!Kšœœœ˜Kšœ˜"—K˜K˜——Kšœ˜—…— ΦΏ