tree ← graph ##.span fm ⍝ Breadth-first span tree for graph ⍺ from vertex ⍵.
Returns a tree that, starting from the given vertex, spans all accessible verti-
ces of the graph "breadth-first". The tree has the property that it has the
least depth possible: no spanning tree exists that has a shorter path from its
root to any vertex.
More generally, [fm] may be a _vector_ of vertices, in which case the breadth-
first search starts in parallel from each given vertex.
The tree is returned in compact form: each item of the vector, with the except-
ion of the root item, is the index of the tree node's parent node.
The following operator may be used to display the tree in an indented format.
The function operand takes a vertex number and returns a label:
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.
}
... and this function displays the tree in list format:
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.
}
Technical notes:
This coding differs slightly from classic breadth-first search, see →bfs←.
Examples:
⍝ 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]]
↑{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, 3], 5]
[5, [3, 2, [4, 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)
⍝ graph gx: breadth-first visiting sequence:
⍝
⍝ 1───────2───────3───────4 [1]─────[2]─────[3]─────[4] c.f. →dfspan←
⍝ │ │ │ │ │ │
⍝ │ │ │ │ │ │
⍝ │ │ │ │ │ │
⍝ 5───────6 7───────8 [2]─────[3] [4]─────[5]
⍝ │ │ │ │
⍝ │ │ │ │
⍝ │ │ │ │
⍝ 9──────10 11──────12 [3]─────[4] [7] [6]
⍝ │ │ │ │ │ │
⍝ │ │ │ │ │ │
⍝ │ │ │ │ │ │
⍝ 13──────14──────15──────16 [4]─────[5]─────[6]─────[7]
gx span 1
¯1 1 2 3 1 5 3 7 5 9 15 8 9 13 14 15
See also: Graphs bfs stpath path search dfspan
Back to: contents
Back to: Workspaces