⍝ 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

⍝∇ scc gperm pmat

Back to: code

Back to: Workspaces