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:

    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

    ast3∘stpath¨⍳5                  ⍝ ... paths from 3 to all other vertices.
┌─────┬───┬─┬───┬─────┐
│3 4 1│3 2│3│3 4│3 4 5│
└─────┴───┴─┴───┴─────┘

    ⊢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 5 ¯1 4│4 3 5 3 ¯1│
└──────────┴──────────┴──────────┴──────────┴──────────┘

    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 5 3│4    │4 5    │
├───────┼─────┼─────┼─────┼───────┤
│5 3 4 1│5 3 2│5 3  │5 3 4│5      │
└───────┴─────┴─────┴─────┴───────┘

    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 5 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: Workspaces