```⍝ Strongly connected components of graph ⍵:

show←{↑(⍕¨⍳⍴⍵),¨' → '∘,¨⍕¨⍵}            ⍝ table display of graph

⎕io←0   ⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝ try with origin 0

g ← ,¨1(2 4 5)(3 6)(2 7)(0 5)6 5(3 6)
g
┌─┬─────┬───┬───┬───┬─┬─┬───┐
│1│2 4 5│3 6│2 7│0 5│6│5│3 6│
└─┴─────┴───┴───┴───┴─┴─┴───┘
show g
0 → 1
1 → 2 4 5
2 → 3 6
3 → 2 7
4 → 0 5
5 → 6
6 → 5
7 → 3 6

scc g                                   ⍝ strongly connected components
0 0 1 1 0 2 2 1

h ← ,¨4 0(1 3)2 1(1 4 6)(2 5)(3 6 7)
h
┌─┬─┬───┬─┬─┬─────┬───┬─────┐
│4│0│1 3│2│1│1 4 6│2 5│3 6 7│
└─┴─┴───┴─┴─┴─────┴───┴─────┘
show h
0 → 4
1 → 0
2 → 1 3
3 → 2
4 → 1
5 → 1 4 6
6 → 2 5
7 → 3 6 7

scc h                                   ⍝ strongly connected components
0 0 1 1 0 2 2 3

mike ← (3)(4)(3 4)(0 2 4)(1 2 3)        ⍝ Mike Day's example

scc mike                                ⍝ graph is strongly connected
0 0 0 0 0

perms←{ ⍵∘gperm¨ ↓pmat ≢⍵}              ⍝ all permutations of graph ⍵

↑ ∪ scc¨ perms mike                     ⍝ perms don't affect connectivity
0 0 0 0 0

⎕io←1   ⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝⍝ try with origin 1

scc g+1
1 1 2 2 1 3 3 2
scc h+1
1 1 2 2 1 3 3 4

scc 1⌽⍳10                               ⍝ polygon is strongly connected
1 1 1 1 1 1 1 1 1 1
scc ⍳10                                 ⍝ graph with no connections
1 2 3 4 5 6 7 8 9 10
scc 2⌽⍳10                               ⍝ graph with two components
1 2 1 2 1 2 1 2 1 2
⍬≡scc ⍬                                 ⍝ 0-vertex graph
1
(⍳10)≡scc 10⍴⊂⍬                         ⍝ null graph.
1
cube←{                                  ⍝ ⍵-cube.
↓{                                  ⍝ split simple matrix:
0=⍵:1 0⍴0                       ⍝ 0-cube: point.
(2*⍵-1){                        ⍝ number of vertices.
(⍵⍪⍵+⍺),⍺⌽⍳2×⍺              ⍝ ⍵-cube from
}∇ ⍵-1                          ⍝   ⍵-1-cube.
}⍵
}

⎕io∧.=scc cube 4                        ⍝ ⍵-cube is strongly connected
1
con←{               ⍝ Condensation of graph ⍵.
c←scc ⍵         ⍝ strongly connected components
v←{⊂⍵}⌸c        ⍝ component-grouped vertex indices
e←c{⊂⍵}⌸⍵       ⍝   ..      ..      edges
x←∪¨(∊¨e)~¨v    ⍝ out-of-component edges
m←↓∨/¨x∘.∊v     ⍝ masks of remote vertices
g←m/¨⊂⍳⍴v       ⍝ condensed DAG
g v             ⍝ ... and contracted vertices
}

g+1                         ⍝ graph
┌─┬─────┬───┬───┬───┬─┬─┬───┐
│2│3 5 6│4 7│3 8│1 6│7│6│4 7│
└─┴─────┴───┴───┴───┴─┴─┴───┘

scc g+1                     ⍝ strongly connected components
1 1 2 2 1 3 3 2

⍕disp¨ con g+1              ⍝ condensation and contracted vertices
┌───┬─┬┐  ┌─────┬─────┬───┐
│2 3│3││  │1 2 5│3 4 8│6 7│
└───┴─┴┘  └─────┴─────┴───┘

isdag ← scc ≡ ⍳∘≢                   ⍝ is-a-DAG (contains no cycles)
isdag g+1                           ⍝ g contains at least one cycle
0
isdag (⍳10),⊂⍬                      ⍝ graph is acyclic
1

Back to: code

Back to: Workspaces
```