```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
```