scc←{⎕ML←1                                  ⍝ Strongly connected components.
                                            ⍝ (Tarjan)
    loop←{                                  ⍝ for each vertex in graph G
        vert←{⍺ conn(0=X ⍺⊃⍵)⊢⍵}           ⍝ connection of unvisited vertex ⍺
        ⊃vert/(⌽⍳⍴G),⊂⍵                     ⍝   for each vertex in G
    }                                       ⍝ :: T ← ∇ T

    conn←{v←⍺                               ⍝ connection of vertex v
        T0v trace ⍵                        ⍝ optional tracing
        T1x1 v push v Lx v Xx T0           ⍝ successor state for x S L and X
        T2←↑{w←⍺                            ⍝ edge v → w
            min_L←{(w⊃⍵)⌊@(L v)⊢⍵}       ⍝ L[v] ⌊← ⍺[w]
            0=X w⊃⍵:L min_L w conn ⍵        ⍝ w not connected: depth-first trav
            X min_L(wS⊃⍵)⊢⍵               ⍝ low-link if w on stack
        }/(vG),⊂T1                        ⍝ for each edge from vertex v
        root(L vT2)=X vT2                ⍝ is a root vertex?
        v comprootT2                      ⍝ new component if root
    }                                       ⍝ :: T ← v ∇ T

    comp←{v←⍺                               ⍝ strongly connected component
        pops←1++/∧\vstkS⊃⍵                ⍝ number of connected comps on stack
        C∆(1+⌈/C⊃⍵)⊣@(popsstk)C⊃⍵        ⍝ extended strongly connected comps
        (popsstk)C∆⊣@S C⊢⍵                 ⍝ reduced stack; extended comps
    }                                       ⍝ :: T ← v ∇ T

    T(3/⊂0⊣¨G←⍵),1 ⍬                       ⍝ state tuple T :: C L X x S
    C L X x S←⍳⍴T                           ⍝ access names for items of tuple T

    put{(⍵⍵⊃⍵)⊣@(⊂⍺⍺ ⍺)⊢⍵}                 ⍝ ⍵⍵ at ⍺ in field ⍺⍺ of ⍵
    LxL put x                              ⍝ ⍺ at x in lowlink vec :: T ← ⍺ ∇ T
    XxX put x                              ⍝ ⍺ at x in indices vec :: T ← ⍺ ∇ T
    x1←1+@x⊢                                ⍝ successor of index x  :: T ←   ∇ T
    push←,¨@S                               ⍝ ⍺ pushed onto stack   :: T ← ⍺ ∇ T

    ⍺←0 ⋄ trace←{⍵⊣⎕←0 dsp ⍺,⍵}⍣(⍺≢0)       ⍝ ⍺: optional tracing   :: T ←   ∇ T

    (∪⍳⊢)Cloop T                           ⍝ for each vertex

    ⍝ T :: C L X x S                        ⍝ state tuple
    ⍝ C :: [x]                              ⍝ connected components vector
    ⍝ L :: [x]                              ⍝ low-link vector
    ⍝ X :: [x]                              ⍝ indices vector
    ⍝ x ::  #                               ⍝ index of vertex in graph G
    ⍝ S :: [x]                              ⍝ stack of vertices
}
code_colours

test script

Back to: notes

Back to: Workspaces