DIRECTORY Asserting, Graphs, Rope; GraphOps: CEDAR DEFINITIONS = {OPEN Graphs; RankGraph: PROC [g: Graph, d: DirectedDirection]; GraphRanked: PROC [g: Graph, d: DirectedDirection] RETURNS [BOOL]; VertexRank: PROC [v: Vertex, d: DirectedDirection] RETURNS [rank: INT]; EdgePredicate: TYPE = PROC [v, w: Vertex] RETURNS [BOOL]; DetermineComponents: PROC [g: Graph, d: Direction, predicate: EdgePredicate _ NIL] RETURNS[numComponents: CARDINAL _ 0]; ComponentsDetermined: PROC [g: Graph, d: Direction] RETURNS [BOOL]; VertexComponent: PROC [v: Vertex, d: Direction] RETURNS [component: CARDINAL]; }. *GraphOps.mesa Mike Spreitzer August 21, 1986 3:53:36 pm PDT Dennis Arnon September 11, 1986 12:22:23 pm PDT This interface provides some specializations of general Graphs, and some operations. Ranking A graph g ranked in direction d has a ranking function r: Vertex _ NAT, such that r(v) > 0 & A w: E edge v d w g r(v)  r(w) & r(v) is no larger than it has to be. Rankings are only meaningul for acyclic graphs. Connected Components Decide whether a particular edge is to be noticed in a connected components computation. It is assumed that there actually is a (possibly directed) edge from v to w in the graph. Compute connected components of g, under the conditions that only edges which do not have direction d are ignored, and an edge having direction d is only noticed if it satisfies predicate. Κo– "cedar" style˜code™ K™-K™/—K˜KšΟk œ˜"K˜šΟnœœ œœ˜+K˜Ibody™TK˜head™šœAΟmœ™QKšœŸœŸœŸœŸœ ŸœŸœŸœ%™Q—Kšœ/™/K˜šž œœ"˜1K˜—šž œœ"œœ˜BK˜—Kšž œœ#œœ˜GK˜—™š œœœœœ˜9Kšœ³™³K˜—š žœœ5œœœ˜xK™ΌK˜—šžœœœœ˜CK˜—Kšžœœœ œ˜NK˜—K˜——…—bϋ