Essays/Tree Display
Tree Display
The verb tree produces a tree display from a 2-column table of the edges. The result is a list of boxed literal tables, one box for each tree in the forest specified by the edges.
BOXC=: 9!:6 '' NB. box drawing characters
EW =: {: BOXC NB. east-west
tree=: 3 : 0
assert. ($y) -: (#y),2
y=. ":&.>^:(32 ~: 3!:0) y
assert. ((2 = 3!:0&>) *. 1 >: #@$&>) y
j=. ~. , y
t=. (<EW,' ') ,@<@,:@,&.> j NB. GTs (generational trees)
c=. |: j i. y
while. +./ b=. ({.c)*.//.-.e.~/c do.
i=. b#~.{.c NB. parents whose children are leaves
j=. </./(({.c)e.i)#"1 c NB. leaves grouped by parents
assert. ~:;j NB. non-unique means not forest
t=. a: (;j)}t i}~ (i{t) subtree&.> j{&.><t
c=. (-.({.c)e.i)#"1 c NB. prune edges to leaves
end.
assert. c -: i.2 0 NB. non-empty means not a forest
([: ,.&.>/ extend&.>)&> t -. a:
)
subtree=: 4 : 0
p=. EW={."1 s=. >{.t=. graft y
(<(>{.x) root p),(<(connect p),.s),}.t
)
graft=: 3 : 0
n=. (-~ >./) #&> y
f=. i.@(,&0)@#&.>@{.&.> y
,&.>/ y ,&> n$&.>f
)
connect=: 3 : 0
b=. (+./\ *. +./\.) y
c=. (b+2*y){' ',9 3 3{BOXC NB. │ NS ├ E
c=. (0{BOXC) (b i. 1)}c NB. ┌ NW
c=. (6{BOXC) (b i: 1)}c NB. └ SW
j=. (b i. 1)+<.-:+/b
EW&(j})^:(1=+/b) c j}~ ((0 3 6 9{BOXC)i.j{c){1 4 7 5{BOXC
)
root=: 4 : 0
j=. k+<.-:1+(y i: 1)-k=. y i. 1
(-j)|.(#y){.x,.,:' ',EW
)
extend=: 3 : '(+./\"1 (y=EW) *. *./\."1 y e.'' '',EW)}y,:EW'
Examples
] t1=: }. (p:^:_1 ,. ]) i.20
0 1
0 2
1 3
2 4
2 5
3 6
3 7
4 8
4 9
4 10
4 11
5 12
5 13
6 14
6 15
6 16
6 17
7 18
7 19
tree t1
┌────────────────────────────┐
│ ┌─ 14│
│ ├─ 15│
│ ┌─ 6 ─┼─ 16│
│ │ └─ 17│
│ ┌─ 1 ─── 3 ─┤ ┌─ 18│
│ │ └─ 7 ─┴─ 19│
│ │ ┌─ 8 │
│─ 0 ─┤ ├─ 9 │
│ │ ┌─ 4 ─┼─ 10 │
│ │ │ └─ 11 │
│ └─ 2 ─┤ ┌─ 12 │
│ └─ 5 ─┴─ 13 │
└────────────────────────────┘
tree t1,30+5{.t1
┌────────────────────────────┬──────────────────┐
│ ┌─ 14│ ┌─ 31 ─── 33│
│ ├─ 15│─ 30 ─┤ ┌─ 34│
│ ┌─ 6 ─┼─ 16│ └─ 32 ─┴─ 35│
│ │ └─ 17│ │
│ ┌─ 1 ─── 3 ─┤ ┌─ 18│ │
│ │ └─ 7 ─┴─ 19│ │
│ │ ┌─ 8 │ │
│─ 0 ─┤ ├─ 9 │ │
│ │ ┌─ 4 ─┼─ 10 │ │
│ │ │ └─ 11 │ │
│ └─ 2 ─┤ ┌─ 12 │ │
│ └─ 5 ─┴─ 13 │ │
└────────────────────────────┴──────────────────┘
The nodes can have labels specified as strings. For example:
a=: ;:'zero one two three four five six seven eight nine'
a=: a ,;:'ten eleven twelve thirteen fourteen fifteen sixteen seventeen eighteen nineteen'
t2=: (?.~@# { ]) t1{a
$ t2
19 2
5{.t2
┌─────┬────────┐
│three│seven │
├─────┼────────┤
│seven│nineteen│
├─────┼────────┤
│zero │two │
├─────┼────────┤
│four │eight │
├─────┼────────┤
│one │three │
└─────┴────────┘
tree t2
┌─────────────────────────────────────────────────┐
│ ┌─ eight │
│ ├─ eleven │
│ ┌─ four ──┼─ nine │
│ │ └─ ten │
│ ┌─ two ─┤ ┌─ twelve │
│ │ └─ five ──┴─ thirteen │
│ │ ┌─ nineteen │
│─ zero ─┤ ┌─ seven ──┴─ eighteen │
│ │ │ ┌─ fifteen │
│ └─ one ─── three ─┤ ├─ fourteen │
│ └─ six ────┼─ sixteen │
│ └─ seventeen│
└─────────────────────────────────────────────────┘
] t3=: _2 ]\ ;:'tree subtree tree extend subtree graft subtree root subtree connect'
┌───────┬───────┐
│tree │subtree│
├───────┼───────┤
│tree │extend │
├───────┼───────┤
│subtree│graft │
├───────┼───────┤
│subtree│root │
├───────┼───────┤
│subtree│connect│
└───────┴───────┘
tree t3
┌──────────────────────────────┐
│ ┌─ graft │
│ ┌─ subtree ─┼─ root │
│─ tree ─┤ └─ connect│
│ └─ extend │
└──────────────────────────────┘
Program Logic
A generational tree is a list of boxed literal tables having the same number of rows, such that the nodes at the same depth are in the same box. For example, the GT for the tree t1 above is:
┌─────┬──────┬──────┬──────┬─────┐ │ │ │ │ │┌─ 14│ │ │ │ │ │├─ 15│ │ │ │ │┌─ 6 ─│┼─ 16│ │ │ │ ││ │└─ 17│ │ │┌─ 1 ─│── 3 ─│┤ │┌─ 18│ │ ││ │ │└─ 7 ─│┴─ 19│ │ ││ │ │┌─ 8 │ │ │─ 0 ─│┤ │ │├─ 9 │ │ │ ││ │┌─ 4 ─│┼─ 10 │ │ │ ││ ││ │└─ 11 │ │ │ │└─ 2 ─│┤ │┌─ 12 │ │ │ │ │└─ 5 ─│┴─ 13 │ │ └─────┴──────┴──────┴──────┴─────┘
The main verb tree maintains a GT for each node (in the local name t). Each iteration of main loop generates subtrees represented as GTs for those parents all of whose children are leaves, then all branches leading to leaves are pruned and the GTs for the leaves are purged. The iteration terminates when there are no such parents.
For the tree t1 above, the initial list of GTs is:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬ ─┬──────┐ │┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│ │┌────┐│ ││─ 0│││─ 1│││─ 2│││─ 3│││─ 4│││─ 5│││─ 6│││─ 7││ ... ││─ 19││ │└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│ │└────┘│ └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴ ─┴──────┘
After the next iteration, the resultant list of GTs is:
┌─────┬─────┬─────┬─────┬─────────────┬─────────────┬─────────────┬─────────────┬┬┬┬┬┬┬┬┬┬┬┬┐ │┌───┐│┌───┐│┌───┐│┌───┐│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│││││││││││││ ││─ 0│││─ 1│││─ 2│││─ 3│││ │┌─ 8 │││ │┌─ 12│││ │┌─ 14│││ │┌─ 18││││││││││││││ │└───┘│└───┘│└───┘│└───┘││ │├─ 9 │││─ 5 ─│┴─ 13│││ │├─ 15│││─ 7 ─│┴─ 19││││││││││││││ │ │ │ │ ││─ 4 ─│┼─ 10││└─────┴─────┘││─ 6 ─│┼─ 16││└─────┴─────┘│││││││││││││ │ │ │ │ ││ │└─ 11││ ││ │└─ 17││ │││││││││││││ │ │ │ │ │└─────┴─────┘│ │└─────┴─────┘│ │││││││││││││ └─────┴─────┴─────┴─────┴─────────────┴─────────────┴─────────────┴─────────────┴┴┴┴┴┴┴┴┴┴┴┴┘
And after the next:
┌─────┬─────┬────────────────────┬────────────────────┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┬┐ │┌───┐│┌───┐│┌─────┬──────┬─────┐│┌─────┬──────┬─────┐│││││││││││││││││ ││─ 0│││─ 1│││ │ │┌─ 8 │││ │ │┌─ 14││││││││││││││││││ │└───┘│└───┘││ │ │├─ 9 │││ │ │├─ 15││││││││││││││││││ │ │ ││ │┌─ 4 ─│┼─ 10│││ │┌─ 6 ─│┼─ 16││││││││││││││││││ │ │ ││ ││ │└─ 11│││ ││ │└─ 17││││││││││││││││││ │ │ ││─ 2 ─│┤ │┌─ 12│││─ 3 ─│┤ │┌─ 18││││││││││││││││││ │ │ ││ │└─ 5 ─│┴─ 13│││ │└─ 7 ─│┴─ 19││││││││││││││││││ │ │ │└─────┴──────┴─────┘│└─────┴──────┴─────┘│││││││││││││││││ └─────┴─────┴────────────────────┴────────────────────┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┴┘
subtree
subtree does the "heavy-lifting" of the main loop. The left argument is the label for a parent; the right argument is a list of boxed GTs for its children. The result is a single GT for that parent. For example:
x ┌───┐ │─ 2│ └───┘ y ┌─────────────┬─────────────┐ │┌─────┬─────┐│┌─────┬─────┐│ ││ │┌─ 8 │││ │┌─ 12││ ││ │├─ 9 │││─ 5 ─│┴─ 13││ ││─ 4 ─│┼─ 10││└─────┴─────┘│ ││ │└─ 11││ │ │└─────┴─────┘│ │ └─────────────┴─────────────┘ x subtree y ┌─────┬──────┬─────┐ │ │ │┌─ 8 │ │ │ │├─ 9 │ │ │┌─ 4 ─│┼─ 10│ │ ││ │└─ 11│ │─ 2 ─│┤ │┌─ 12│ │ │└─ 5 ─│┴─ 13│ └─────┴──────┴─────┘
graft
graft takes a list of boxed GTs for the children of a node and combines them into a single GT. For example:
y ┌───────────────────────────┬────────────────────┐ │┌─────┬──────┬──────┬─────┐│┌─────┬──────┬─────┐│ ││ │ │ │┌─ 14│││ │ │┌─ 8 ││ ││ │ │ │├─ 15│││ │ │├─ 9 ││ ││ │ │┌─ 6 ─│┼─ 16│││ │┌─ 4 ─│┼─ 10││ ││ │ ││ │└─ 17│││ ││ │└─ 11││ ││─ 1 ─│── 3 ─│┤ │┌─ 18│││─ 2 ─│┤ │┌─ 12││ ││ │ │└─ 7 ─│┴─ 19│││ │└─ 5 ─│┴─ 13││ │└─────┴──────┴──────┴─────┘│└─────┴──────┴─────┘│ └───────────────────────────┴────────────────────┘ graft y ┌─────┬──────┬──────┬─────┐ │ │ │ │┌─ 14│ │ │ │ │├─ 15│ │ │ │┌─ 6 ─│┼─ 16│ │ │ ││ │└─ 17│ │─ 1 ─│── 3 ─│┤ │┌─ 18│ │ │ │└─ 7 ─│┴─ 19│ │ │ │┌─ 8 │ │ │ │ │├─ 9 │ │ │ │┌─ 4 ─│┼─ 10 │ │ │ ││ │└─ 11 │ │ │─ 2 ─│┤ │┌─ 12 │ │ │ │└─ 5 ─│┴─ 13 │ │ └─────┴──────┴──────┴─────┘
connect
connect applies to a boolean list with 1s indicating where subtree roots are located. The result is is a literal list with the following properties:
- vertical lines spanning the first and the last 1s, with "corners" at those first and last 1s
- tick marks on the right for subtree roots
- a single tick mark on the left for the root located midway between the first and the last 1
This result is best viewed as a column.
Examples:
connect 1 1 1 ┌┼└ ,. connect 1 1 1 ┌ ┼ └ ,. connect 0 0 1 0 1 0 0 1 1 ┌ │ ├ ┤ │ ├ └ ,. connect 1 ─
root
The dyad root applies to a one-row literal matrix left argument and to a boolean list with 1s indicating where subtree roots are located (same as the argument for connect). It produces a literal matrix suitable for use as the root (the leftmost matrix) of a GT. For example:
] t=: (,:EW,' abc') root 0 0 1 0 1 0 ─ abc ─ $ t 6 7
extend
extend extends the trailing horizontal line (EW) characters in a literal table to the right edge of the table. For example:
t ┌────────┬────────┬──────────┬───────────┬────────────┐ │ │ │ │┌─ eight │ │ │ │ │ │├─ eleven │ │ │ │ │┌─ four ─ │┼─ nine │ │ │ │ ││ │└─ ten │ │ │ │┌─ two ─│┤ │┌─ twelve │ │ │ ││ │└─ five ─ │┴─ thirteen│ │ │ ││ │ │ │┌─ nineteen │ │─ zero ─│┤ │ │┌─ seven ─ │┴─ eighteen │ │ ││ │ ││ │┌─ fifteen │ │ │└─ one ─│── three ─│┤ │├─ fourteen │ │ │ │ │└─ six ─ │┼─ sixteen │ │ │ │ │ │└─ seventeen│ └────────┴────────┴──────────┴───────────┴────────────┘ extend&.> t ┌────────┬────────┬──────────┬───────────┬────────────┐ │ │ │ │┌─ eight │ │ │ │ │ │├─ eleven │ │ │ │ │┌─ four ──│┼─ nine │ │ │ │ ││ │└─ ten │ │ │ │┌─ two ─│┤ │┌─ twelve │ │ │ ││ │└─ five ──│┴─ thirteen│ │ │ ││ │ │ │┌─ nineteen │ │─ zero ─│┤ │ │┌─ seven ──│┴─ eighteen │ │ ││ │ ││ │┌─ fifteen │ │ │└─ one ─│── three ─│┤ │├─ fourteen │ │ │ │ │└─ six ────│┼─ sixteen │ │ │ │ │ │└─ seventeen│ └────────┴────────┴──────────┴───────────┴────────────┘
Contributed by Roger Hui. The program logic is similar to that in a post to the comp.lang.apl newsgroup on 1991-09-28.