⍝ Spanning tree for graph ⍺ from vertex ⍵:

    ⎕io←1

    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.
    }

    ltree←{                         ⍝ List format of spanning tree.
        tree←⍵                      ⍝ spanning tree.
        bkt←{'[',⍵,']'}             ⍝ bracket.
        sep←{↑{⍺,', ',⍵}/⍵}         ⍝ comma-separate.
        {                           ⍝ radiate outwards from root:
            next←(tree=⍵)/⍳⍴tree    ⍝ nodes that point to this one.
            next≡⍬:⍕⍵               ⍝ none: finished.
            bkt sep(⊂⍕⍵),∇¨next     ⍝ node followed by sub-trees.
        }⍵⍳¯1                       ⍝ starting from root.
    }

⍝      Graph "a".
⍝    ┌─────1←────┐   5 vertices: 1 2 3 4 5
⍝    │     │     │
⍝    ↓     ↓     │   8 edges:    1→2  1→3
⍝    2←───→3────→4               2→3
⍝          ↑     │               3→2  3→4
⍝          │     ↓               4→1  4→5
⍝          └─────5               5→3

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

    show←{↑⍕¨(⍳⍴⍵),¨'→',¨⍵}         ⍝ show graph.

    show a                          ⍝ graph "a".
1 → 2 3
2 → 3  
3 → 2 4
4 → 1 5
5 → 3  

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

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

    ⍕mtree a span 3                 ⍝ formatted spanning tree from vertex 3.
3        
·   2    
·   4    
·   ·   1
·   ·   5

    ltree a span 3                  ⍝ list-format spanning tree from vertex 3.
[3, 2, [4, 1, 5]]

    mix←{⎕ml←0 ⋄ ↑⍵}

    mix{ltree a span ⍵}¨⍳⍴a         ⍝ list format for all of a's span trees.
[1, 2, [3, [4, 5]]]
[2, [3, [4, 1, 5]]]
[3, 2, [4, 1, 5]]  
[4, [1, 2], [5, 3]]
[5, [3, 2, [4, 1]]]

    verts← {↑,/↓¨cmat∘⍵¨⍳⍵}∘⍴       ⍝ all combinations of a's vertices.

    verts a
┌─┬─┬─┬─┬─┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬───────┬───────┬───────┬───────┬───────┬─────────┐
│1│2│3│4│5│1 2│1 3│1 4│1 5│2 3│2 4│2 5│3 4│3 5│4 5│1 2 3│1 2 4│1 2 5│1 3 4│1 3 5│1 4 5│2 3 4│2 3 5│2 4 5│3 4 5│1 2 3 4│1 2 3 5│1 2 4 5│1 3 4 5│2 3 4 5│1 2 3 4 5│
└─┴─┴─┴─┴─┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴───────┴───────┴───────┴───────┴───────┴─────────┘

    a∘span¨verts a                  ⍝ span tree for each combination
┌──────────┬──────────┬──────────┬──────────┬──────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬───────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬────────────┬─────────────┬─────────────┬─────────────┬─────────────┬─────────────┬──────────────┐
│¯1 1 1 3 4│4 ¯1 2 3 4│4 3 ¯1 3 4│4 1 5 ¯1 4│4 3 5 3 ¯1│¯1 ¯1 2 3 4│¯1 3 ¯1 3 4│¯1 1 1 ¯1 4│¯1 1 5 3 ¯1│4 ¯1 ¯1 3 4│4 ¯1 2 ¯1 4│4 ¯1 5 3 ¯1│4 3 ¯1 ¯1 4│4 3 ¯1 3 ¯1│4 3 5 ¯1 ¯1│¯1 ¯1 ¯1 3 4│¯1 ¯1 2 ¯1 4│¯1 ¯1 5 3 ¯1│¯1 3 ¯1 ¯1 4│¯1 3 ¯1 3 ¯1│¯1 1 5 ¯1 ¯1│4 ¯1 ¯1 ¯1 4│4 ¯1 ¯1 3 ¯1│4 ¯1 5 ¯1 ¯1│4 3 ¯1 ¯1 ¯1│¯1 ¯1 ¯1 ¯1 4│¯1 ¯1 ¯1 3 ¯1│¯1 ¯1 5 ¯1 ¯1│¯1 3 ¯1 ¯1 ¯1│4 ¯1 ¯1 ¯1 ¯1│¯1 ¯1 ¯1 ¯1 ¯1│
└──────────┴──────────┴──────────┴──────────┴──────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴───────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴────────────┴─────────────┴─────────────┴─────────────┴─────────────┴─────────────┴──────────────┘

    gx←(2 5)(1 3 6)(2 4 7)(3 8)(1 6 9)(2 5)(3 8)(4 7 12)(5 10 13)(9 14)(12 15)(8 11 16)(9 14)(10 13 15)(11 14 16)(12 15)

    gx span 1
¯1 1 2 3 1 5 3 7 5 9 15 8 9 13 14 15

⍝∇ span cmat

Back to: code

Back to: Workspaces