⍝ Weighted Graphs:

    ⎕io ⎕ml←1 0

    aa←↑((2 3)3(2 4)(1 5)3) ((1 3)1(4 1)(1 1)1)

    1 disp aa                       ⍝ simple weighted graph "aa"
┌→──┬─┬───┬───┬─┐
↓2 3│3│2 4│1 5│3│
├~─→┼─┼~─→┼~─→┼─┤
│1 3│1│4 1│1 1│1│
└~─→┴─┴~─→┴~─→┴─┘

    show←{↑{⍺,'→',⍵}/⎕a[⍵]}         ⍝ translate path vertices to: A B C ···

    show aa wpath 3 2               ⍝ lowest cost path C→B
C→D→A→B

    show aa[1;] path 3 2            ⍝ compare: best path C→B <ignoring> weights
C→B

    aa wspan 5                      ⍝ spanning tree for aa from vertex 3
4 1 5 3 ¯1

    1 disp(aa wspan 5)∘stpath¨⍳5    ⍝ paths to each vertex from spanning tree 5
┌→──────┬─────────┬───┬─────┬─┐
│5 3 4 1│5 3 4 1 2│5 3│5 3 4│5│
└~─────→┴~───────→┴~─→┴~───→┴→┘

    aa wcost 1 3 4 5 3 2 3 2        ⍝ cost of path through graph "aa"
3 1 1 1 4 1 4

⍝∇ wpath path wspan wcost stpath

Back to: code

Back to: Workspaces