
    <<GraphOpsImpl.mesa>>
        <<Mike Spreitzer September 27, 1986 3:19:00 pm PDT>>

    DIRECTORY Asserting, GraphOps, Graphs, Rope;

    GraphOpsImpl: CEDAR PROGRAM
        IMPORTS Asserting, Graphs
        EXPORTS GraphOps
        =

    BEGIN OPEN Graphs, GraphOps;

<<Ranking>>
    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;

<<Connected Components>>
    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.