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