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
        T0←v trace ⍵                        ⍝ optional tracing
        T1←x1 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⍣(w∊S⊃⍵)⊢⍵               ⍝ low-link if w on stack
        }/(⌽v⊃G),⊂T1                        ⍝ for each edge from vertex v
        root←(L v⊃T2)=X v⊃T2                ⍝ is a root vertex?
        v comp⍣root⊢T2                      ⍝ new component if root
    }                                       ⍝ :: T ← v ∇ T

    comp←{v←⍺                               ⍝ strongly connected component
        pops←1++/∧\v≠stk←S⊃⍵                ⍝ number of connected comps on stack
        C∆←(1+⌈/C⊃⍵)⊣@(pops↑stk)⊢C⊃⍵        ⍝ extended strongly connected comps
        (pops↓stk)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 ⍵
    Lx←L put x                              ⍝ ⍺ at x in lowlink vec :: T ← ⍺ ∇ T
    Xx←X 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

    (∪⍳⊢)C⊃loop 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