⍝ Spanning tree for graph ⍺ from vertex ⍵:

      ⎕io←1

      mtree←{⎕ML←0                  ⍝ 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.

    disp 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│
└→┴→┴→┴→┴→┴~─→┴~─→┴~─→┴~─→┴~─→┴~─→┴~─→┴~─→┴~─→┴~─→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~───→┴~─────→┴~─────→┴~─────→┴~─────→┴~─────→┴~───────→┘

    disp 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

Back to: code

Back to: Workspaces

Trouble seeing APL font?