vvec ← tree ##.stpath to ⍝ Path through spanning tree ⍺ to vertex ⍵.
Given a spanning tree from one vertex of a graph, returns a vector of vertices
that represent a path to the supplied vertex. If many paths from a common start-
ing vertex are to be calculated, it is more efficient to produce and reuse the
spanning tree, than to calculate the paths independently using the →path← funct-
ion each time.
Examples:
disp a ⍝ simple graph "a".
┌→──┬─┬───┬───┬─┐
│2 3│3│2 4│1 5│3│
└~─→┴─┴~─→┴~─→┴─┘
⎕←ast3←a span 3 ⍝ a's spanning tree from vertex 3, yields:
4 3 ¯1 3 4
disp ast3∘stpath¨⍳5 ⍝ ... paths from 3 to all other vertices.
┌→────┬───┬─┬───┬─────┐
│3 4 1│3 2│3│3 4│3 4 5│
└~───→┴~─→┴→┴~─→┴~───→┘
disp vast←a∘span¨⍳⍴a ⍝ vector of a's spanning trees.
┌→─────────┬──────────┬──────────┬──────────┬──────────┐
│¯1 1 1 3 4│4 ¯1 2 3 4│4 3 ¯1 3 4│4 1 1 ¯1 4│4 3 5 3 ¯1│
└~────────→┴~────────→┴~────────→┴~────────→┴~────────→┘
disp vast∘.stpath⍳⍴a ⍝ extract paths between all 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 1 3│ 4 │ 4 5 │
├~─────→┼~───→┼~───→┼~───→┼~─────→┤
│5 3 4 1│5 3 2│ 5 3 │5 3 4│ 5 │
└~─────→┴~───→┴~───→┴~───→┴~─────→┘
disp a∘path¨{⍵∘.,⍵}⍳⍴a ⍝ ... same as direct path extraction.
┌→──────┬─────┬─────┬─────┬───────┐
↓ 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 1 3│ 4 │ 4 5 │
├~─────→┼~───→┼~───→┼~───→┼~─────→┤
│5 3 4 1│5 3 2│ 5 3 │5 3 4│ 5 │
└~─────→┴~───→┴~───→┴~───→┴~─────→┘
See also: Graphs span path search
Back to: contents
Back to: Dyalog APL
Trouble seeing APL font?