User:Doug Mennella/Trees
Representing trees with vectors
Trees are familiar data structures in programming and there are a number of ways to represent them in code. The most common probably is to have each node have "links" to each of its children and use these links to recursively descend the structure of the tree from some root node. But a tree is also a graph and as such can be represented as a list of edges, each edge going from a parent node to one of its children.
For this graph we have the following list of edges.
┬
cat
├────┬─────────┐
ab dog er
│ ├────┐
u hm cat
┌───┬───┐
│cat│ab │
├───┼───┤
│ab │u │
├───┼───┤
│cat│dog│
├───┼───┤
│dog│hm │
├───┼───┤
│dog│cat│
├───┼───┤
│cat│er │
└───┴───┘
There are a couple of things worth noting here. First is that parent to child is a one-to-many relationship and another is that the identity of a node is distinct from the value or "label" of the node. If we simply list the nodes (in any order), we can use the index into that list as the identity of the node.
┌───┬──┬─┬───┬──┬───┬──┐ │0 │1 │2│3 │4 │5 │6 │ ├───┼──┼─┼───┼──┼───┼──┤ │cat│ab│u│dog│hm│cat│er│ └───┴──┴─┴───┴──┴───┴──┘
Now we can distinguish the leaf "cat" from the root "cat". Here's the kicker: While every parent node can have multiple children, each node has at most one parent! Moreover, every node has a parent excepting the root. If we simply declare the parent of a root node to be itself, we can fill this gap and now represent each edge using a single element, namely the parent of that node.
┌─┬─┬─┬─┬─┬─┬─┐ │0│1│2│3│4│5│6│ ├─┼─┼─┼─┼─┼─┼─┤ │0│0│1│0│3│3│0│ └─┴─┴─┴─┴─┴─┴─┘
Having the root node be self-parenting may feel poorly motivated at this point, but if nothing else it serves as an clear way to distinguish it from all other nodes.
Note that now we have represented the entire structure of the tree with a single vector (we can always reproduce the indexing vector), and the tree as a whole with a pair of vectors, namely a parent vector and a values vector.
┌───┬──┬─┬───┬──┬───┬──┐ │0 │0 │1│0 │3 │3 │0 │ ├───┼──┼─┼───┼──┼───┼──┤ │cat│ab│u│dog│hm│cat│er│ └───┴──┴─┴───┴──┴───┴──┘
As far as faithfully representing the tree goes, the only thing that's important here is that both of these vectors are indexed the same. If you listed the nodes in a different order then the parent vector needs to reflect this different ordering.
Paths
One strong motivation for making the root node self-parenting is to be able have a fixed point for indexing. That is, if we chase each node through its parent recursively we stop when we reach a root node.
p=.0 0 1 0 3 3 0
(p{~])^:a:&.>"0 i.#p
┌─┬───┬─────┬───┬─────┬─────┬───┐
│0│1 0│2 1 0│3 0│4 3 0│5 3 0│6 0│
└─┴───┴─────┴───┴─────┴─────┴───┘
These are the paths from each node to the root. There are many uses for these paths. What if we wanted to restrict this to paths from leaf nodes? Well, leaf nodes are nodes which aren't parent nodes to any other nodes.
(-.~ i.&#)p
2 4 5 6
(p{~])^:a:&.>"0 (-.~ i.&#)p
┌─────┬─────┬─────┬───┐
│2 1 0│4 3 0│5 3 0│6 0│
└─────┴─────┴─────┴───┘
We'll now use this as a first step to produce the tree representation at the start of this page.
Tree display
First let's run the fixed point on the entire array rather than at rank 0:
(p{~])^:a: i.#p
0 1 2 3 4 5 6
0 0 1 0 3 3 0
0 0 0 0 0 0 0
With a little thought it shouldn't be surprising that each column ends up at zero. Let's do this for just the leaves.
(p{~])^:a: (-.~ i.&#)p
2 4 5 6
1 3 3 0
0 0 0 0
Here the first row is all the leaves and the second is each of their parents etc. But if we look at the display at the top of this page there are leaves on more than just a single row. In fact each row contains only elements at the same depth. If we reverse each of the paths, we can let unboxing line up the depths.
|.@((p{~])^:a:)&>"0 (-.~ i.&#)p
0 1 2
0 3 4
0 3 5
0 6 0
|:|.@((p{~])^:a:)&>"0 (-.~ i.&#)p
0 0 0 0
1 3 3 6
2 4 5 0
] ls=. ;: 'cat ab u dog hm cat er'
┌───┬──┬─┬───┬──┬───┬──┐
│cat│ab│u│dog│hm│cat│er│
└───┴──┴─┴───┴──┴───┴──┘
ls {"1~ |:|.@((p{~])^:a:)&>"0 (-.~ i.&#)p
┌───┬───┬───┬───┐
│cat│cat│cat│cat│
├───┼───┼───┼───┤
│ab │dog│dog│er │
├───┼───┼───┼───┤
│u │hm │cat│cat│
└───┴───┴───┴───┘
It looks like we're in the ballpark, but not quite there yet. Two issues. One is the repetition of parent nodes and the other is that the fill element looks an awful lot like the index of our root node. We solve the latter problem by temporarily thinking of our array as being 1-indexed.
>:@|.@((p{~])^:a:)&>"0 (-.~ i.&#)p
1 2 3
1 4 5
1 4 6
1 7 0
|:>:@|.@((p{~])^:a:)&>"0 (-.~ i.&#)p
1 1 1 1
2 4 4 7
3 5 6 0
(' ';ls) {"1~ |:>:@|.@((p{~])^:a:)&>"0 (-.~ i.&#)p
┌───┬───┬───┬───┐
│cat│cat│cat│cat│
├───┼───┼───┼───┤
│ab │dog│dog│er │
├───┼───┼───┼───┤
│u │hm │cat│ │
└───┴───┴───┴───┘
This is a little better. Now we just need to handle the repetition.
(***2-.@=/\0,]) >:@|.@((p{~])^:a:)&>"0 (-.~ i.&#)p
1 2 3
0 4 5
0 0 6
0 7 0
(' ';ls) {"1~ |:(***2-.@=/\0,]) >:@|.@((p{~])^:a:)&>"0 (-.~ i.&#)p
┌───┬───┬───┬──┐
│cat│ │ │ │
├───┼───┼───┼──┤
│ab │dog│ │er│
├───┼───┼───┼──┤
│u │hm │cat│ │
└───┴───┴───┴──┘
Now we're cooking with gas! Before moving on there's an important property we just exploited. Earlier we said that the ordering of the nodes is arbitrary and that's true for faithfully representing the tree. But here we wanted an extra property. That is that all children of a given parent be contiguous in the listing of nodes. We achieve this by listing the nodes in depth-first-search pre-ordering. I.e. we list each parent before each of its children recursively. Luckily we chose just such an ordering for this tree.
Cleaning this all up we get:
tr=:(***2~:/\0,])@(|.@:>:@({~^: a:"_ 0) (-.~i.&#))
tr p
1 2 3
0 4 5
0 0 6
0 7 0
Finally we need to alternate rows with labels with rows representing the tree connectors. We use the BOX characters for drawing connectors.
BOXC=: 9!:6 ''
DRAW=: ' ',1 9 3 2 1 10{ BOXC
DRAW
┬│├┐┬─
In order to determine which of these characters go where, we need to classify our nodes according to whether we're a root, an only child, a leftmost child, a middle child or a right most child. To do this, we need to group the nodes according to their parent like so:
(;/.. i.&#)p ┌─┬───────┐ │0│0 1 3 6│ ├─┼───────┤ │1│2 │ ├─┼───────┤ │3│4 5 │ └─┴───────┘
For starters, since root nodes are self parenting, we'll want to remove those from the list of children.
(<@-.~/.. i.&#)p ┌─────┬─┬───┐ │1 3 6│2│4 5│ └─────┴─┴───┘
Now the idea for classifying is imagining starting off with a 0 for everything in p and then adding one in each spot that is a child node except for the last child and then adding a two in each spot that is a child node except the first child. We'll be left with a one in the first child, a three for any middle children and a two for any last child. Any single children or root node will be left with zero. We'll worry about the root node later, but this effectively classifies all the children as being a left child, middle child or right child.
Lopping off the first child or the last for each parent node is pretty easy.
((}:;}.)@-.~/.. i.&#)p ┌───┬───┐ │1 3│3 6│ ├───┼───┤ │ │ │ ├───┼───┤ │4 │5 │ └───┴───┘
But really we want to deal with the leftmost nodes of any parent node, rather than for each parent node. With a clever idea from @elcaro from the The APL Farm Discord server, we can group this slightly differently.
|:@;@(<@(}:,"0}.)@-.~/.. i.&#)p 1 3 4 3 6 5
Now the first row contains leftmost nodes and the second contains right most nodes. Let's mark these spots.
(i.&# e."1 (|:@;@(<@(}:,"0}.)@-.~/.. i.&#)))p 0 1 0 1 1 0 0 0 0 0 1 0 1 1 (1 2+/@:*i.&# e."1 (|:@;@(<@(}:,"0}.)@-.~/.. i.&#)))p 0 1 3 0 1 2 2
To distinguish the root node, we bump all the class numbers up by one and decrease the class number at the root nodes.
((= i.&#)-~1 2>:@+/@:*i.&# e."1 (|:@;@(<@(}:,"0}.)@-.~/.. i.&#)))p 0 2 1 4 2 3 3
One final fix is to remember that we're thinking of this as being 1-indexed, so we bump up the class numbers once again and prepend a 0.
(0,1+(= i.&#)-~1 2>:@+/@:*i.&# e."1 (|:@;@(<@(}:,"0}.)@-.~/.. i.&#)))p 0 1 3 2 5 3 4 4
Now we have all the node types classified. We apply this classification to our tree layout.
cls=:0,1+(= i.&#)-~1 2>:@+/@:*i.&# e."1 (|:@;@(<@(}:,"0}.)@-.~/.. i.&#))
|:@(cls{~"1 tr)p
1 0 0 0
3 5 0 4
2 3 4 0
BOXC=: 9!:6 ''
DRAW=: ' ',1 9 3 2 1 10{ BOXC
(DRAW{~"1|:@(cls{~"1 tr))p
┬
├┬ ┐
│├┐
Nearly home free. Now we just need to connect the left most children with the rightmost children without overwriting the middle children.
To find the places between class 3 and 4, we start by marking them and then use a classic parsing trick of using a not-equals left fold to find the spots between these ones. Note that since we're requiring DFS pre-order we know that at any given depth the leftmost child nodes alternate with rightmost child nodes.
(3 4 e.~(cls{~"1 tr))p
0 1 0
0 0 1
0 0 1
0 1 0
(0 ]F:.~: 3 4 e.~(cls{~"1 tr))p
0 1 0
0 1 1
0 1 0
0 0 0
Now we just find where these marked nodes match up with zeros in the tree layout. It suffices to see where this output is greater than the input and assign those spots a new class number of 6.
|:@(([+6*[<0 ]F:.~: 3 4 e.~])@(cls{~"1 tr))p
1 0 0 0
3 5 6 4
2 3 4 0
(DRAW {~"1])@|:@(([+6*[<0 ]F:.~: 3 4 e.~])@(cls{~"1 tr))p
┬
├┬─┐
│├┐
And now we just piece them together.
]lbls=.(' ';ls){~"1|:(***2-.@=/\0,])>:@|.&>(p{~])^:a:&.>"0 (-.~ i.&#)p
┌───┬───┬───┬──┐
│cat│ │ │ │
├───┼───┼───┼──┤
│ab │dog│ │er│
├───┼───┼───┼──┤
│u │hm │cat│ │
└───┴───┴───┴──┘
]drw=.<"0@(DRAW {~"1])@|:@(([+6*[<0 ]F:.~: 3 4 e.~])@(cls{~"1 tr))p
┌─┬─┬─┬─┐
│┬│ │ │ │
├─┼─┼─┼─┤
│├│┬│─│┐│
├─┼─┼─┼─┤
│││├│┐│ │
└─┴─┴─┴─┘
lbls(,~/:(]|2 i.@*])@#@])drw
┌───┬───┬───┬──┐
│┬ │ │ │ │
├───┼───┼───┼──┤
│cat│ │ │ │
├───┼───┼───┼──┤
│├ │┬ │─ │┐ │
├───┼───┼───┼──┤
│ab │dog│ │er│
├───┼───┼───┼──┤
││ │├ │┐ │ │
├───┼───┼───┼──┤
│u │hm │cat│ │
└───┴───┴───┴──┘
So close!! To fix this we'll need a bigger palate. We'll need to spread out the BOX character drawing before applying the connectors, but we'll also need to draw in the labels character by character.
First we spread out the diagram to leave room for the labels. We'll use this to classify the character types as well as locate the labels.
]t=.4(}.@((] #!.0~ #@] # 1 j. [)0,]))tr p
0 0 0
0 0 0
0 0 0
0 0 0
1 2 3
0 0 0
0 0 0
0 0 0
0 0 0
0 4 5
0 0 0
0 0 0
0 0 0
0 0 0
0 0 6
0 0 0
0 0 0
0 0 0
0 0 0
0 7 0
0 0 0
0 0 0
0 0 0
0 0 0
]drw=.(DRAW {~"1])@|:@(([+6*[<0 ]F:.~: 3 4 e.~])@(t {"1 cls))p
┬
├────┬─────────┐
│ ├────┐
For the labels, the idea is to use a palate as large the diagram just generated, locate the starts of the labels and then insert the characters in consecutive indices from those starts. This is most easily done if we do this under a flattening of the diagram.
ls (>:@i.&#@[ i.~ ;@]) t 12 13 14 28 29 44 58 ls (<@i."0@#&>@[ ; >:@i.&#@[ i.~ ;@]) t ┌─────────────────────────────────┬────────────────────┐ │┌─────┬───┬─┬─────┬───┬─────┬───┐│12 13 14 28 29 44 58│ ││0 1 2│0 1│0│0 1 2│0 1│0 1 2│0 1││ │ │└─────┴───┴─┴─────┴───┴─────┴───┘│ │ └─────────────────────────────────┴────────────────────┘ ls (<@i."0@#&>@[+&.>>:@i.&#@[ i.~ ;@]) t ┌────────┬─────┬──┬────────┬─────┬────────┬─────┐ │12 13 14│13 14│14│28 29 30│29 30│44 45 46│58 59│ └────────┴─────┴──┴────────┴─────┴────────┴─────┘
Now for a little fancy J. These are the indices for each label. We can place each of them with amend, but we can also place them all at once if we raze both the indices and the labels. The fancy J is the tacit form of amend.
lbli=.;@(<@i."0@#&>@[+&.>>:@i.&#@[ i.~ ;@])
]lbls=. ls (($@]$;@[`lbli`(' '"0@;@])}) |:) t
cat
ab dog er
u hm cat
And VOILA!
lbls(,~/:(]|2 i.@*])@#@])drw
┬
cat
├────┬─────────┐
ab dog er
│ ├────┐
u hm cat
The code in full
After a bit of clean up, here is the code in full:
BOXC=: 9!:6 ''
DRAW=: ' ',1 9 3 2 1 10{ BOXC
cls=:0,1+(= i.&#)-~1 2>:@+/@:*i.&# e."1 (|:@;@(<@(}:,"0}.)@-.~/.. i.&#))
tr=:(***2~:/\0,])@(|.@:>:@({~^:a:)"_ 0 (-.~i.&#))
spr=:1}.(0,]) #!.0~ >:@#@] # 1 j. [
cxn=:]+6*]<0]F:.~:e.~
lbli=:;@(<@i."0@#&>@[+&.>>:@i.&#@[ i.~ ;@])
lbl=:($@]$(;@[)`lbli`(' '"0@;@]])}) |:
tree=:{{
(tree~ <@":"0@i.@#)y
:
t=.(>:>./#&>x) spr tr y
d=.DRAW {~"_ 1|:3 4 cxn (t {"1 _ cls)y
l=.x lbl t
l (,~/:(]|2 i.@*])@#@]) d
}}
To be invoked like so:
p=.0 0 1 0 3 3 0
ls=:'cat';'ab';'u';'dog';'hm';'cat';'er'
ls tree p
┬
cat
├────┬─────────┐
ab dog er
│ ├────┐
u hm cat
Note there is a monadic version which just uses the node indices as labels.
tree p ┬ 0 ├──┬─────┐ 1 3 6 │ ├──┐ 2 4 5
Centering display
Some might prefer that tree roots be centered among their children rather than left adjusted. To center adjust, you (ahem) adjust the horizontal positions. To do that, let's have a closer look at the "schematic" of our tree offered by `tr`.
]t =. |:tr p=: 0 0 1 0 3 3 0 1 0 0 0 2 4 0 7 3 5 6 0
Using a sparse representation of this matrix, we'll get a handle on the coordinates of the individual nodes, from which we can extract the values and the coordinates.
]st =. $.t 0 0 │ 1 1 0 │ 2 1 1 │ 4 1 3 │ 7 2 0 │ 3 2 1 │ 5 2 2 │ 6 ]i=.4 $. st 0 0 1 0 1 1 1 3 2 0 2 1 2 2 ]vl=.5 $. st 1 2 4 7 3 5 6
If we sort the coordinates by the values, we'll get them ordered by their index, from there we separate the horizontal from the vertical coordinates. From this representation it's easy to spread out the matrix, by simply multiplying the horizontal coordinates by a spread factor.
]'vt hz' =. <"1 |:i/:vl ┌─────────────┬─────────────┐ │0 1 2 1 2 2 1│0 0 0 1 1 2 3│ └─────────────┴─────────────┘ ]hz =. 2 * hz 0 0 0 2 2 4 6
Now for the center adjusting. We want each parent node to lie at the average horizontal position of its children. Leaves (nodes without children) obviously don't need to be adjusted. But some nodes are both parents and children, so if we adjust them for their children, then their value has changed for calculation of their parents. One way to deal with this is to start at the bottom (i.e. with nodes at the deepest depth) and work your way up. Another is to notice that leaves will not move, and that parents of only leaves will not move after a single adjustment, parents of those nodes won't move after at most two adjustments, etc. I.e. we're headed towards a fixed point.
So here's the plan, collect nodes by their parent and take their average horizontal position and amend the parent's horizontal position by this calculation. Then repeat this until we stabilize. The advantage of this approach is that it's simpler and we don't have to determine the depths of nodes up front to apply it. One hitch is that for self parenting nodes we don't want their current position to be included in the average.
Dealing with this last first we get the following:
(~.-.~&.>(</. i.@#))p ┌─────┬─┬───┐ │1 3 6│2│4 5│ └─────┴─┴───┘
Or with a more modern verb:
(<@-.~/.. i.@#)p ┌─────┬─┬───┐ │1 3 6│2│4 5│ └─────┴─┴───┘
Now we need to take the horizontal positions at these indices and take their average.
hz(((+/ <.@% #)@:{&:>"0 1)~ (<@-.~/.. i.@#))p
2 0 3
Now we use this to repeatedly update the horizontal positions of the parent nodes. Note that we take the flip of the above function because what's being updated should be the right argument.
nw=.((+/ <.@% #)@:{&:>"0 1~ (<@-.~/.. i.@#))~
ctr=.nw`(~.@[)`]} ^:_
hz
0 0 0 2 2 4 6
]hz =. p ctr hz
3 0 0 3 2 4 6
We line these up with the vertical positions and then reassemble our matrix whose dimension are affected by the spread we applied earlier. You should be able to discern the centering and the schematic from the output.
]t =. 0$.(/:~vl)(<"1|:vt,:hz)}(1$.(1 2*$t);0 1) 0 0 0 1 0 0 0 0 2 0 0 4 0 0 7 0 3 0 5 0 6 0 0 0
If we draw this as we did with the left adjusted tree we see we have a bit more work to do, though it's not looking too bad.
DRAW {~"_ 1|:3 4 cxn ((|:t) {"1 _ cls)p
┬
├──┬──┐
│ ├─┐
We're going to need some more characters. For one the leftmost node should get a new character.
DRAWC {~"_ 1|:3 4 cxn ((|:t) {"1 _ cls)p
┬
┌──┬──┐
│ ┌─┐
Now for the tricky bit. Parent nodes are no longer directly above their leftmost child. There are now two cases: parents can be directly above a child as the root is here, or not as the node directly below the root here. Adding to this is that we need to know which of these nodes are parent nodes and which aren't. We can make our lives a little simpler by adding the connecting characters first. That way there will be something under parent nodes and nothing otherwise.
]c =. (t {"1 _ cls)p
0 0 0 1 0 0 0 0
3 0 0 5 0 0 4 0
2 0 3 0 4 0 0 0
]cc =. 3 4&cxn&.:|: c
0 0 0 1 0 0 0 0
3 6 6 5 6 6 4 0
2 0 3 6 4 0 0 0
Here we did the connection under transpose because we're now looking at the classification matrix in a different orientation. (We might be able to avoid this, but it's not currently worth the trouble.)
We shift all our nodes from c down and see what they run into in cc. There are three possibilities: running into another node, running into a connector or anything else. We give the first two cases a classification 8 and 7 respectively and the last we give a 0 so that when we take the max with the current classification it remains unchanged.
cc(8 7 0{~5 6 i.[*0,_1}.*@])c
0 0 0 0 0 0 0 0
0 0 0 8 0 0 0 0
0 0 0 7 0 0 0 0
]c =. cc([>.8 7 0{~5 6 i.[*0,_1}.*@])c
0 0 0 1 0 0 0 0
3 6 6 8 6 6 4 0
2 0 3 7 4 0 0 0
Now we can render our matrix.
]DRAWC=: ' ',1 9 0 2 1 10 7 4{ BOXC
┬│┌┐┬─┴┼
DRAWC {~"_ 1 c
┬
┌──┼──┐
│ ┌┴┐
Merging with the labels is exactly as in the left adjusted case.
ctrtree p ┬ 0 ┌──┼──┐ 1 3 6 │ ┌┴┐ 2 4 5
Here's an example that exercises all of the character classes:
ctrtree 0 0 1 0 3 3 3 0 0
┬
0
┌───┬┴──┬─┐
1 3 7 8
│ ┌─┼─┐
2 4 5 6
Centering labels
What if we have different size labels? This looks fine enough with a left adjusted tree, but looks a little funky for a centered tree.
l =. 'cat';'ab';'u';'dog';'hm';'cat';'er'
l tree p
┬
cat
├────┬─────────┐
ab dog er
│ ├────┐
u hm cat
l ctrtree p
┬
cat
┌─────┼─────┐
ab dog er
│ ┌─┴─┐
u hm cat
The fix should be pretty obvious after studying how labels are placed in the left adjusted version. Instead of writing out the characters from the position of the node, we move back half the length of the label. For this to work, we'll need room on the left to shift back to. This amounts an extra adjustment on the horizontal positions and one on the dimensions of the resultant matrix.
lb =. 'catastrophe';'ab';'u';'dog';'hm';'cat';'er'
lb ctrtree p
┬
catastrophe
┌─────────────────┼─────────────────┐
ab dog er
│ ┌─────┴─────┐
u hm cat
the code
DRAWC=: ' ',1 9 0 2 1 10 7 4{ BOXC
nw=:(((+/ <.@% #)@:{&:>"0 1)~ (<@-.~/.. i.@#))~
ctr =: nw`(~.@[)`]} ^:_
hlv =: {{ <. -: <: #&> y }}
ixs =: {{ <@i."0 #&> y}}
clbli =: ;@(ixs@[ +&.> hlv@[ -~ >:@i.&#@[ i.~ ;@])
clbl =: ($@] $ ;@[`clbli`(' '"0@;@] ])} ) |:
ctrtree=:{{
(ctrtree~ <@":"0@i.@#)y
:
st =. $.t=.|:tr y
vl =. 5 $. st
'hg wd' =. <"1|:vl/:~4$.st
sp =. >:>./#&>x
wd =. y ctr sp * 1 + wd
t =. 0$.(/:~vl)(<"1|:hg,:wd)}(1$.((1,sp)*0 1+$t);0 1)
c =. (t {"1 _ cls)y
cc =. 3 4&cxn&.:|: c
c =. cc([>.8 7 0{~5 6 i.[*0,_1}.*@])c
d=.DRAWC {~"_ 1 c
l=.x clbl |: t
l (,~/:(]|2 i.@*])@#@]) d
}}
Toolset
Once again, to faithfully represent the tree the only requirement is that the values line up with the parent vector. Reordering the nodes means shuffling the parent vector in parallel and make sure that the parent vector has references to the new location.
And again this tree rendering algorithm has an addtional requirement that for any parent node all of its descendants must be contiguous. This last can be assured by putting the nodes in a DFS pre-order.
Let's build up some tools to help us satisfy these assertions. As an example we'll generate a classic tree of a complete binary tree. (Thanks to Raul Miller for suggesting this example.)
]p=.0>.<.-:<:i.32 0 0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 14 15
In this representation siblings are contiguous but not descendants. The children of a node n are at 1 2+2*n. First let's figure out how to do a depth first search through this tree parent vector. The idea is to start at a root and chase descendants. I.e. going down the tree, while indexing into a parent vector means going up a tree. We use key to group children per parent node:
(;/.. i.&#) p ┌──┬─────┐ │0 │0 1 2│ ├──┼─────┤ │1 │3 4 │ ├──┼─────┤ │2 │5 6 │ ├──┼─────┤ │3 │7 8 │ ├──┼─────┤ │4 │9 10 │ ├──┼─────┤ │5 │11 12│ ├──┼─────┤ │6 │13 14│ ├──┼─────┤ │7 │15 16│ ├──┼─────┤ │8 │17 18│ ├──┼─────┤ │9 │19 20│ ├──┼─────┤ │10│21 22│ ├──┼─────┤ │11│23 24│ ├──┼─────┤ │12│25 26│ ├──┼─────┤ │13│27 28│ ├──┼─────┤ │14│29 30│ ├──┼─────┤ │15│31 │ └──┴─────┘
Since root nodes are self-parenting, they also appear as children of themselves, but we obviously don't want to chase down them so the first step is remove this from the list of children.
([ ([;-.~)/.. i.@#) p ┌──┬─────┐ │0 │1 2 │ ├──┼─────┤ │1 │3 4 │ ├──┼─────┤ │2 │5 6 │ ├──┼─────┤ │3 │7 8 │ ├──┼─────┤ │4 │9 10 │ ├──┼─────┤ │5 │11 12│ ├──┼─────┤ │6 │13 14│ ├──┼─────┤ │7 │15 16│ ├──┼─────┤ │8 │17 18│ ├──┼─────┤ │9 │19 20│ ├──┼─────┤ │10│21 22│ ├──┼─────┤ │11│23 24│ ├──┼─────┤ │12│25 26│ ├──┼─────┤ │13│27 28│ ├──┼─────┤ │14│29 30│ ├──┼─────┤ │15│31 │ └──┴─────┘
Now this is the parent-child dictionary we'll use to chase the tree. Note the tree doesn't have keys for all nodes in the tree, though. Also we'll need to lookup children for a given node as we chase the graph. To this end we separate the keys from the values in this look up table. When handed a node we'll search for it in the keys and use that index to find it in the values.
'v k'=.(~.;~a:,~[ <@-.~/.. i.@#) p
┌──────────────────────────────────────────────────────────────────────────────────────┬─────────────────────────────────────┐
│┌───┬───┬───┬───┬────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬──┬┐│0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15│
││1 2│3 4│5 6│7 8│9 10│11 12│13 14│15 16│17 18│19 20│21 22│23 24│25 26│27 28│29 30│31│││ │
│└───┴───┴───┴───┴────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴──┴┘│ │
└──────────────────────────────────────────────────────────────────────────────────────┴─────────────────────────────────────┘
v {~ k i. 0
┌───┐
│1 2│
└───┘
v {~ k i. 15
┌──┐
│31│
└──┘
v {~ k i. 25
┌┐
││
└┘
Notice that we use the classic trick of appending a default to the end of our list of children an empty box so that we can look up nodes not in our list of keys. I.e. nodes not in our list of keys have no children, i.e. are leaves. Now that we have our table, we look up our root node in the table and list it before recursively applying the function to each of its children, stopping when there are no children.
Here's a clean implementation of this algorithm from Raul Miller using a conjunction to pass the keys and values to the recursive call.
df=: {{ y"_`(y(,;)m df n&.>)@.(0<#) ;n{~m i. y }}
dfo=: {{ ; (~.y) df (a:,~(<@-.~/.. i.@#) y)&.> (#~ ]=i.@#)y }}
]g=.dfo p
0 1 3 7 15 31 16 8 17 18 4 9 19 20 10 21 22 2 5 11 23 24 12 25 26 6 13 27 28 14 29 30
This is the first tool for our toolbox. This is the ordering we'd like to have our nodes in. We can apply this ordering to our parent vector, but the contents of the parent vector would still be pointing to the old node indices. What we want to do is for each index in the new parent vector look up the old index in the old parent vector and then convert that to the new index in the new parent vector.
(<@":"0 g) tree p((]{~/:)/:)g
┬
0
├───────────────────────────────┐
1 2
├───────────────┐ ├───────────────┐
3 4 5 6
├───────┐ ├───────┐ ├───────┐ ├───────┐
7 8 9 10 11 12 13 14
├───┐ ├───┐ ├───┐ ├───┐ ├───┐ ├───┐ ├───┐ ├───┐
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
│
31
Building on our last tool, we can use the following to collect the new indexing and the new parent under a DFS preorder:
redo=:(],:]{~/:) /:@:dfo