⍝ Graphs:

⍝      Graph "a".
⍝    ┌─────A←────┐
⍝    │     │     │   5 vertices: A B C D E
⍝    ↓     ↓     │
⍝    B←───→C────→D   8 edges:    A→B  A→C  B→C  C→B
⍝          ↑     │               C→D  D→A  D→E  E→C
⍝          │     ↓
⍝          └─────E

    ⎕io←1

    a←(2 3)(3)(2 4)(1 5)(3)             ⍝ simple origin-1 graph "a" (above)

    a inslink 5 1                       ⍝ ··· with new link 5→1
┌───┬─┬───┬───┬───┐
│2 3│3│2 4│1 5│3 1│
└───┴─┴───┴───┴───┘

⍝ As many of the functions take a graph as <left> argument and a "modifier" on
⍝ the <right>, the "fold left" operator is useful:

    a inslink foldl (5 1) (3 5)         ⍝ graph "a" with new links: 5→1, 3→5.
┌───┬─┬─────┬───┬───┐
│2 3│3│2 4 5│1 5│3 1│
└───┴─┴─────┴───┴───┘
    a remlink foldl (1 3) (2 3)         ⍝ graph "a" without links: 1→3, 2→3.
┌─┬┬───┬───┬─┐
│2││2 4│1 5│3│
└─┴┴───┴───┴─┘

    vm←{{⍵/⍳⍴⍵}¨↓⍵}                     ⍝ vector from matrix form.

    mv←{⍉(⍳⍴⍵)∘.∊⍵}                     ⍝ matrix from vector form.

    (,¨a) ≡ vm mv a                     ⍝ round-trip graph a.
1

⍝ We  can borrow some lines from the <kt> Knight's Tour function, to generate
⍝ a graph (k) of the knight's moves on an ⍵-sized chessboard.

    kt_graph←{                      ⍝ Graph of knight's moves on ⍵-board.
        kdef←,0 1∘.⌽1 ¯1∘.,2 ¯2     ⍝ vector of relative knight's moves.
        net←(⊂,⍳⍵)∩¨↓(⍳⍵)∘.+kdef    ⍝ absolute moves from each square.
        ⎕io+,⍵∘⊥¨¨net-⎕io           ⍝ adjacency vector.
    }

    k←kt_graph 8 8                  ⍝ graph of knight's moves on an 8×8 board.
    k
┌─────┬────────┬──────────┬───────────┬───────────┬───────────┬────────┬─────┬───────┬──────────┬───────────────┬───────────────┬───────────────┬───────────────┬──────────┬───────┬──────────┬───────────────┬────────────────────┬─────────────────────┬─────────────────────┬─────────────────────┬───────────────┬──────────┬───────────┬────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬─────────────────┬───────────┬───────────┬─────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬─────────────────┬───────────┬───────────┬─────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬───────────────────────┬─────────────────┬───────────┬────────┬───────────┬─────────────────┬─────────────────┬─────────────────┬─────────────────┬───────────┬────────┬─────┬────────┬───────────┬───────────┬───────────┬───────────┬────────┬─────┐
│11 18│12 17 19│9 13 18 20│10 14 19 21│11 15 20 22│12 16 21 23│13 22 24│14 23│3 19 26│4 20 25 27│1 5 17 21 26 28│2 6 18 22 27 29│3 7 19 23 28 30│4 8 20 24 29 31│5 21 30 32│6 22 31│2 11 27 34│1 3 12 28 33 35│2 4 9 13 25 29 34 36│3 5 10 14 26 30 35 37│4 6 11 15 27 31 36 38│5 7 12 16 28 32 37 39│6 8 13 29 38 40│7 14 30 39│10 19 35 42│9 11 20 36 41 43│10 12 17 21 33 37 42 44│11 13 18 22 34 38 43 45│12 14 19 23 35 39 44 46│13 15 20 24 36 40 45 47│14 16 21 37 46 48│15 22 38 47│18 27 43 50│17 19 28 44 49 51│18 20 25 29 41 45 50 52│19 21 26 30 42 46 51 53│20 22 27 31 43 47 52 54│21 23 28 32 44 48 53 55│22 24 29 45 54 56│23 30 46 55│26 35 51 58│25 27 36 52 57 59│26 28 33 37 49 53 58 60│27 29 34 38 50 54 59 61│28 30 35 39 51 55 60 62│29 31 36 40 52 56 61 63│30 32 37 53 62 64│31 38 54 63│34 43 59│33 35 44 60│34 36 41 45 57 61│35 37 42 46 58 62│36 38 43 47 59 63│37 39 44 48 60 64│38 40 45 61│39 46 62│42 51│41 43 52│42 44 49 53│43 45 50 54│44 46 51 55│45 47 52 56│46 48 53│47 54│
└─────┴────────┴──────────┴───────────┴───────────┴───────────┴────────┴─────┴───────┴──────────┴───────────────┴───────────────┴───────────────┴───────────────┴──────────┴───────┴──────────┴───────────────┴────────────────────┴─────────────────────┴─────────────────────┴─────────────────────┴───────────────┴──────────┴───────────┴────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴─────────────────┴───────────┴───────────┴─────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴─────────────────┴───────────┴───────────┴─────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴───────────────────────┴─────────────────┴───────────┴────────┴───────────┴─────────────────┴─────────────────┴─────────────────┴─────────────────┴───────────┴────────┴─────┴────────┴───────────┴───────────┴───────────┴───────────┴────────┴─────┘

    ⍴¨k(↑,/k)                       ⍝ number of vertices and edges.
┌──┬───┐
│64│336│
└──┴───┘
    k path 1 2                      ⍝ Knight's path from square 1 to 2.
1 18 12 2

⍝ We  can  keep a vector of data associated with each vertex separate from, but
⍝ parallel with, the graph. In this case we might like a vector of board posit-
⍝ ion notations: A1 A2 ··· B1 B2 ··· H8. This vector may exist independently as
⍝ a workspace variable, or could be bound with a "translation" function.

    show←{(,⍉8 8↑⎕A∘.,1↓⎕D)[⍵]}     ⍝ show board positions.

    ⍕show k path 1 9                ⍝ a shortest path from A1 to A2.
 A1  B3  C1  A2 

    ⍕show k path 1 64               ⍝   ··  ··  ··  ··  to opposite corner.
 A1  B3  C5  B7  D8  F7  H8 

    ⍕show k path 1 10               ⍝   ··  ··  ··  ··  to adjacent diagonal
 A1  B3  C5  A4  B2 

    a span 1                        ⍝ spanning tree for graph "a" from vertex 1.
¯1 1 1 3 4

    (a span 1)stpath 2              ⍝ shortest path from 1 to 2 using span tree.
1 2
    (a span 1)∘stpath¨⍳⍴a           ⍝ shortest path from 1 to each vertex.
┌─┬───┬───┬─────┬───────┐
│1│1 2│1 3│1 3 4│1 3 4 5│
└─┴───┴───┴─────┴───────┘
                                    ⍝ shortest path between
    ↑{(a span ⍵)∘stpath¨⍳⍴a}¨⍳⍴a    ⍝ each pair of vertices.
┌───────┬─────┬─────┬─────┬───────┐
│1      │1 2  │1 3  │1 3 4│1 3 4 5│
├───────┼─────┼─────┼─────┼───────┤
│2 3 4 1│2    │2 3  │2 3 4│2 3 4 5│
├───────┼─────┼─────┼─────┼───────┤
│3 4 1  │3 2  │3    │3 4  │3 4 5  │
├───────┼─────┼─────┼─────┼───────┤
│4 1    │4 1 2│4 5 3│4    │4 5    │
├───────┼─────┼─────┼─────┼───────┤
│5 3 4 1│5 3 2│5 3  │5 3 4│5      │
└───────┴─────┴─────┴─────┴───────┘

    k span 1                        ⍝ knight's spanning tree from vertex 1.
¯1 12 18 21 11 12 13 23 3 25 1 18 3 29 21 31 11 1 25 35 11 12 29 39 35 11 33 18 35 45 21 38 18 28 18 26 52 28 29 55 35 52 33 50 35 52 62 38 43 35 45 35 43 60 45 62 51 52 53 50 55 52 53 54

    k span 10                       ⍝ spanning tree from vertex 10.
18 17 20 10 20 12 22 14 26 ¯1 17 27 30 20 30 22 27 33 25 10 27 12 40 30 10 20 10 45 44 20 37 47 27 44 25 42 27 44 54 30 35 27 33 27 35 61 37 54 59 44 61 42 59 44 61 62 42 52 44 54 44 52 53 54

⍝ We can write a format operator to display the spanning tree:

    mtree←{                         ⍝ Matrix format of spanning tree.
        vfmt←⍺⍺                     ⍝ vertex format function.
        tree←⍵                      ⍝ spanning tree.
        ↑''{                        ⍝ mix to char matrix.
            this←⊂⍺,⊃vfmt ⍵         ⍝ indented, formatted vertex.
            next←(tree=⍵)/⍳⍴tree    ⍝ child vertices of current vertex ⍵.
            next≡⍬:this             ⍝ childless: finished.
            dent←⍺,'·   '           ⍝ increased indent.
            this,↑,/dent∘∇¨next     ⍝ formatted sub-trees.
        }tree⍳¯1                    ⍝ ... from starting vertex.
    }

⍝ Using the small graph "a" and {⍵⊃⎕a} as a vertex formatting function:

    a                       ⍝ graph "a"
┌───┬─┬───┬───┬─┐
│2 3│3│2 4│1 5│3│
└───┴─┴───┴───┴─┘

    {⍵⊃⎕a}mtree a span 3    ⍝ spanning tree from vertex 3
C        
·   B    
·   D    
·   ·   A
·   ·   E

⍝ Graph of cube in ⍵-space:

    cube←{                      ⍝ ⍵-cube.
        ↓{                      ⍝ split simple matrix:
            0=⍵:1 0⍴0           ⍝ 0-cube: point.
            (2*⍵-1){            ⍝ number of vertices.
                (⍵⍪⍵+⍺),⍺⌽⍳2×⍺  ⍝ ⍵-cube from
            }∇ ⍵-1              ⍝   ⍵-1-cube.
        }⍵
    }

    cube 0              ⍝ point.
┌┐
││
└┘

    cube 1              ⍝ line.
┌─┬─┐
│2│1│
└─┴─┘

    cube 2              ⍝ square.
┌───┬───┬───┬───┐
│2 3│1 4│4 1│3 2│
└───┴───┴───┴───┘

    cube 3              ⍝ regular cube.
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│2 3 5│1 4 6│4 1 7│3 2 8│6 7 1│5 8 2│8 5 3│7 6 4│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

    cube 4              ⍝ hypercube.
┌───────┬────────┬────────┬────────┬────────┬────────┬────────┬────────┬──────────┬─────────┬─────────┬──────────┬─────────┬──────────┬──────────┬──────────┐
│2 3 5 9│1 4 6 10│4 1 7 11│3 2 8 12│6 7 1 13│5 8 2 14│8 5 3 15│7 6 4 16│10 11 13 1│9 12 14 2│12 9 15 3│11 10 16 4│14 15 9 5│13 16 10 6│16 13 11 7│15 14 12 8│
└───────┴────────┴────────┴────────┴────────┴────────┴────────┴────────┴──────────┴─────────┴─────────┴──────────┴─────────┴──────────┴──────────┴──────────┘

    {(cube ⍵)path 1,2*⍵}10      ⍝ a path between opposite corners of a 10-cube.
1 513 769 897 961 993 1009 1017 1021 1023 1024

    tcm ← {⍵∨⍵∨.∧⍵}⍣≡                           ⍝ transitive closure (matrix).

    try ← tcm\∘{⍵ ⍵}                            ⍝ show (arg rslt) pair.

    try 4 4⍴ 0 1 0 0, 1 0 0 0, 0 0 0 1, 0 0 1 0
┌───────┬───────┐
│0 1 0 0│1 1 0 0│
│1 0 0 0│1 1 0 0│
│0 0 0 1│0 0 1 1│
│0 0 1 0│0 0 1 1│
└───────┴───────┘
    try 4 4⍴ 0 1 0 0, 0 0 1 0, 0 0 0 1, 1 0 0 0
┌───────┬───────┐
│0 1 0 0│1 1 1 1│
│0 0 1 0│1 1 1 1│
│0 0 0 1│1 1 1 1│
│1 0 0 0│1 1 1 1│
└───────┴───────┘
    try 4 4⍴ 0
┌───────┬───────┐
│0 0 0 0│0 0 0 0│
│0 0 0 0│0 0 0 0│
│0 0 0 0│0 0 0 0│
│0 0 0 0│0 0 0 0│
└───────┴───────┘

    tcv ← {⍵{(⍳⍴⍵)∩⍺,1↓↑,/0,⍺⊃¨⊂⍵}¨⊂⍵}⍣≡        ⍝ transitive closure (vector).

    try ← tcv\∘{⍵ ⍵}                            ⍝ show (arg rslt) pair.

    ⍕disp¨ try ,¨2 1 4 3
 ┌─┬─┬─┬─┐  ┌───┬───┬───┬───┐ 
 │2│1│4│3│  │1 2│1 2│3 4│3 4│ 
 └─┴─┴─┴─┘  └───┴───┴───┴───┘ 

    ⍕disp¨ try ,¨2 3 4 1
 ┌─┬─┬─┬─┐  ┌───────┬───────┬───────┬───────┐ 
 │2│3│4│1│  │1 2 3 4│1 2 3 4│1 2 3 4│1 2 3 4│ 
 └─┴─┴─┴─┘  └───────┴───────┴───────┴───────┘ 

    ⍕disp¨ try ⍬ ⍬ ⍬ ⍬                          ⍝ null graph.
 ┌┬┬┬┐  ┌┬┬┬┐ 
 │││││  │││││ 
 └┴┴┴┘  └┴┴┴┘ 

    ⍕disp¨ try a                    ⍝ transitive closure of graph "a" (above).
 ┌───┬─┬───┬───┬─┐  ┌─────────┬─────────┬─────────┬─────────┬─────────┐ 
 │2 3│3│2 4│1 5│3│  │1 2 3 4 5│1 2 3 4 5│1 2 3 4 5│1 2 3 4 5│1 2 3 4 5│ 
 └───┴─┴───┴───┴─┘  └─────────┴─────────┴─────────┴─────────┴─────────┘ 

Back to: code

Back to: Workspaces