Idiomatic graphs in APL

Question

APL is great for array type problems but I'm curious as to how best work with graphs in APL. I'm playing around with leet questions, for example question 662. Maximum Width of Binary Tree, the exercise works with Node objects with a value/left/right pointer style, however the test-case uses a basic array like [1,3,null,5,3]. The notation is compressed; uncompressed would be [[1], [3,null], [5,3,null,null]]. Reading layer-by-layer give [[1], [3], [5,3]] (so 2 is the widest layer).

Another example,

[5,4,7,3,null,2,null,-1,null,9] gives the answer 2

So I'm not sure the idiomatic way to work with trees. Do I use classes? Or are arrays best? In either case how do I convert the input?

I came up with a couple of solutions, but both feel inelegant. (Apologies for lack of comments)

 convert←{
     prev ← {(-⌈2÷⍨≢⍵)↑⍵}
     nxt←{
         ⍵≡⍬:⍺
         m←2/×prev ⍺
         cnt←+/m
         (⍺,(m\cnt↑⍵))nxt(cnt↓⍵)
     }

     (1↑⍵)nxt(1↓⍵)
 }

Alternatively,

convert ← {
     total←(+/×⍵)
     nxt←{
         double←×1,2↓2/0,⍵
         (((+/double)↑⍺)@⊢)double
     }
     ⍵ nxt⍣{(+/×⍺)=total}1
 }

Both solutions are limited in they assume that 0 is null.

Once I've decompressed the input it's simply just a matter of stratifying by it's order

⌈/(1+⌈/-⌊/)∘⍸¨×nodes⊆⍨⍸2*¯1+⍳⌈2⍟≢nodes

In Python though I could use other methods to traverse i.e. keep track of the left/right-most node on a per-depth basis.

NOTE: This may be two questions, one to decompress and the other how to traverse graphs in general, but one depends on the other

Any ideas?

Answer 1

The work of Co-dfns compiler has given lots of insights on working tree/graph like data structures with APL.

Thesis: A Data Parallel Compiler Hosted on the GPU

GitHub repo: github.com/Co-dfns/Co-dfns (Many related goodies in project README file)

However the thesis is quite lengthy so for this particular exercise I would give a brief explanation on how to approach it.

the exercise works with Node objects with a value/left/right pointer style, however the test-case uses a basic array like [1,3,null,5,3].

Do we really actually build the tree with Node type objects to get an answer to the question? You can write the solution in something like Python and translate to APL, but that would be, losing the whole point of writing it in APL...

Notice the input is already an array! It is a bfs traverse of the binary tree. (The co-dfns compiler uses dfs traverse order, though)

so, actually what we need to do is just built a matrix like below for the input like [1,3,2,5,3,null,9] (⍬ is a placeholder value for for null):

1 ⍬ ⍬ ⍬ ⍝ level 0
3 2 ⍬ ⍬ ⍝ level 1
5 3 ⍬ 9 ⍝ level 2

For this problem we don't need to know which node's parent is which. We can even do something like, by abusing the fact that input has no negative value (even the number could be negative, actually we only care about if it is null), and change ⍬ to ¯1 or 0 and make it easier to compute the answer.

So the problem has became: "compute the matrix representation of the tree as variable tree from the input array, then calculate the width of each level by +/0<tree, then the output is just 2*level (notice the first level is level-0)" This is using wrong definition for the width. I'll show how to correct it below

And it is actually very easy to do the conversion from input to matrix, hint: ↑.

      1 (3 2) 5
┌─┬───┬─┐
│1│3 2│5│
└─┴───┴─┘
      ↑1 (3 2) 5
1 0
3 2
5 0

Thanks for pointing out that my original solution has problem on constructing the tree matrix.

This is the corrected method for constructing the tree. To distinguish from 0 for null and the padding, I add one to the input array so 2 is for non-null and 1 is for null.

 buildmatrix←{
     ⎕IO←0
     in←1+(⊂⊂'null')(≢⍤1 0)⎕JSON ⍵
     ⍝ Build the matrix
     loop←{
         (n acc)←⍺
         0=≢⍵:acc
         cur←n↑⍵
         (2×+/2=cur)(acc,⊂cur)∇ n↓⍵
     }
     ↑1 ⍬ loop in
 }

However since the definition for width here is:

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes are also counted into the length calculation.

We can just compute the width while attempting to reconstructing the tree (compute each level's width using \ and / with patterns from previous level):

If last level is 1011 and next level is 100010

 1   0   1   1
1 0 0 0 0 0 1 0

      (2/1 0 1 1)\1 0 0 0 1 0
1 0 0 0 0 0 1 0

So the it isn't needed to construct the complete matrix, and the answer for the exercise is just:

 width←{
     ⎕IO←0
     in←(⊂⊂'null')(≢⍤1 0)⎕JSON ⍵
     ⍝ strip leading trailing zero
     strip←(⌽⍳∘1↓⊢)⍣2
     ⍝ Build the matrix
     loop←{
         (prev mw)←⍺
         0=≢⍵:mw
         cur←⍵↑⍨n←2×+/prev
         ((⊢,⍥⊂mw⌈≢)strip cur\⍨2/prev)∇ n↓⍵
     }
     (,1)1 loop 1↓in
 }

      width '[1,null,2,3,null,4,5,6]'
2

And the interesting fact is, you can probably do the same in other non-array based languages like Haskell. So instead of translating existing algorithms between similar looking languages, by thinking in the APL way you find new algorithms for problems!