tree display

[Roger|Dyalog]

The function “tree” produces a tree display from a 2-column matrix of the edges. The result is a vector of boxed character matrices, one box for each tree in the forest specified by the edges.

For example:

      p←0 0 1 2 2 3 3 4 4  4  4  5  5  6  6  6  6  7  7
      q←1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
      ⊢ t0←p,⍪q
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 t0
┌────────────────────────────┐
│                       ┌─ 14│
│                       ├─ 15│
│                 ┌─ 6 ─┼─ 16│
│                 │     └─ 17│
│     ┌─ 1 ─── 3 ─┤     ┌─ 18│
│     │           └─ 7 ─┴─ 19│
│     │           ┌─ 8       │
│─ 0 ─┤           ├─ 9       │
│     │     ┌─ 4 ─┼─ 10      │
│     │     │     └─ 11      │
│     └─ 2 ─┤     ┌─ 12      │
│           └─ 5 ─┴─ 13      │
└────────────────────────────┘

      tree t0⍪100+5↑t0
┌────────────────────────────┬─────────────────────┐
│                       ┌─ 14│       ┌─ 101 ─── 103│
│                       ├─ 15│─ 100 ─┤       ┌─ 104│
│                 ┌─ 6 ─┼─ 16│       └─ 102 ─┴─ 105│
│                 │     └─ 17│                     │
│     ┌─ 1 ─── 3 ─┤     ┌─ 18│                     │
│     │           └─ 7 ─┴─ 19│                     │
│     │           ┌─ 8       │                     │
│─ 0 ─┤           ├─ 9       │                     │
│     │     ┌─ 4 ─┼─ 10      │                     │
│     │     │     └─ 11      │                     │
│     └─ 2 ─┤     ┌─ 12      │                     │
│           └─ 5 ─┴─ 13      │                     │
└────────────────────────────┴─────────────────────┘

(Misalignments in the display are due to defects in the APL Chat Forum software.)

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'
      a←a,' sixteen seventeen eighteen nineteen'
      a←' '(≠⊆⊢)a 
      a
┌────┬───┬───┬─────┬────┬────┬───┬─────┬─────┬────┬───┬   ┬────────┬────────┐
│zero│one│two│three│four│five│six│seven│eight│nine│ten│...│eighteen│nineteen│
└────┴───┴───┴─────┴────┴────┴───┴─────┴─────┴────┴───┴   ┴────────┴────────┘
      ⊢ t1←a[t0]
┌─────┬─────────┐
│zero │one      │
├─────┼─────────┤
│zero │two      │
├─────┼─────────┤
│one  │three    │
├─────┼─────────┤
│two  │four     │
├─────┼─────────┤
│two  │five     │
├─────┼─────────┤
...
│six  │seventeen│
├─────┼─────────┤
│seven│eighteen │
├─────┼─────────┤
│seven│nineteen │
└─────┴─────────┘
      tree t1
┌─────────────────────────────────────────────────┐
│                                     ┌─ fourteen │
│                                     ├─ fifteen  │
│                          ┌─ six ────┼─ sixteen  │
│                          │          └─ seventeen│
│        ┌─ one ─── three ─┤          ┌─ eighteen │
│        │                 └─ seven ──┴─ nineteen │
│        │                 ┌─ eight               │
│─ zero ─┤                 ├─ nine                │
│        │       ┌─ four ──┼─ ten                 │
│        │       │         └─ eleven              │
│        └─ two ─┤         ┌─ twelve              │
│                └─ five ──┴─ thirteen            │
└─────────────────────────────────────────────────┘

      t←  ' tree assert tree do tree extend do subtree' 
      t←t,' subtree graft subtree root subtree connect'
      t2← 7 2⍴' '(≠⊆⊢) t
      t2
┌───────┬───────┐
│tree   │assert │
├───────┼───────┤
│tree   │do     │
├───────┼───────┤
│tree   │extend │
├───────┼───────┤
│do     │subtree│
├───────┼───────┤
│subtree│graft  │
├───────┼───────┤
│subtree│root   │
├───────┼───────┤
│subtree│connect│
└───────┴───────┘

      tree t2
┌───────────────────────────────────────┐
│        ┌─ assert                      │
│        │                    ┌─ graft  │
│─ tree ─┼─ do ───── subtree ─┼─ root   │
│        │                    └─ connect│
│        └─ extend                      │
└───────────────────────────────────────┘

The Code

      ⍝
BOXC ← '┌┬┐├┼┤└┴┘│─'   ⍝ box drawing characters
EW   ← ⊃⌽ BOXC         ⍝ east-west

assert←{⍺←'assertion failure' ⋄ 0∊⍵:⍺ ⎕SIGNAL 8 ⋄ shy←0}

tree←{
 do←{
  b←⍵[0;]{∧/⍵}⌸~⍵[1;]∊⍵[0;]       ⍝ parents all whose children are leaves
  ~∨/b:(⍺ ⍵)
  p←⍵[0;]∊b/∪⍵[0;]
  (i j)←↓⍉⊃{⍺ ⍵}⌸/↓p/⍵            ⍝ such parents and corresp. leaves
  t←(⍺[i]subtree¨⍺∘{⍺[⍵]}¨j)@i⊢⍺  ⍝ replace such parents by GTs 
  (0@(∊j)⊢t)∇(~p)/⍵               ⍝ repeat after pruning
 } 
                                                                           
 assert(⍴⍵)≡(≢⍵),2:
 y←⍕¨⍣(2≠≡⍵)⊢⍵                    ⍝ nodes as chars
 assert{(80=⎕DR ⍵)∧1≥≢⍴⍵}¨y:      ⍝ each node must be char scalar or vector
 x←∪,y
 c←⍉x⍳y                           ⍝ nodes as 2-row matrix of indices
 assert(⍳⊃⌽⍴c)=⍳⍨c[1;]:           ⍝ can not have multiple parents
 t←{⊂⍉⍪EW,' ',⍵}¨x                ⍝ initial GTs (generational trees)
 (t c)←t do c
 assert c≡2 0⍴0:                  ⍝ non-empty means not a forest
 {⊃,/extend¨⍵}¨t~0
}

subtree←{
 p←EW=0⌷⍤1⊢s←⊃t←graft ⍵
 (⊂(⊃⍺)root p),(⊂(connect p),s),1↓t
}

graft←{
 cat←{m←1↓(⍴⍺)⌈⍴⍵ ⋄ (m↑⍤1⊢⍺)⍪m↑⍤1⊢⍵}
 n←(⌈/-⊢)≢¨⍵
 f←{⊂''⍴⍨(≢⊃⍵),0}¨⍵
 cat⌿t←↑⍵⍪¨n⍴¨f
}                                   

connect←{
 b←,(∨\⍵)∧⌽∨\⌽⍵
 c←(' ',BOXC[9 3 3])[b+2×⍵]      ⍝ │ NS ├ E
 c←BOXC[0]@(b⍳1)⊢c               ⍝ ┌ NW
 c←BOXC[6]@(¯1+(≢b)-(⌽b)⍳1)⊢c    ⍝ └ SW
 j←(b⍳1)+⌊0.5×+/b
 EW@j⍣(1=+/b)⊢BOXC[1 4 7 5[BOXC[0 3 6 9]⍳j⌷c]]@j⊢c
}
      
root←{(-k+⌊2÷⍨(≢⍵)-(k←⍵⍳1)+(⌽⍵)⍳1)⊖(≢⍵)↑⍺,⍉⍪' ',EW}

extend←{EW@{∨\(⍵=EW)∧⌽∧\⌽⍵∊' ',EW}⍵}

Program Logic

The tree display is created bottom up, from the leaves.

A generational tree (GT) is a vector of boxed character matrices 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 t0 above is:

      ⍝
┌─────┬──────┬──────┬──────┬─────┐
│     │      │      │      │┌─ 14│
│     │      │      │      │├─ 15│
│     │      │      │┌─ 6 ─│┼─ 16│
│     │      │      ││     │└─ 17│
│     │┌─ 1 ─│── 3 ─│┤     │┌─ 18│
│     ││     │      │└─ 7 ─│┴─ 19│
│     ││     │      │┌─ 8  │     │
│─ 0 ─│┤     │      │├─ 9  │     │
│     ││     │┌─ 4 ─│┼─ 10 │     │
│     ││     ││     │└─ 11 │     │
│     │└─ 2 ─│┤     │┌─ 12 │     │
│     │      │└─ 5 ─│┴─ 13 │     │
└─────┴──────┴──────┴──────┴─────┘

The local name t in function “tree” is a vector of GTs for each node, likewise the left argument ⍺ of the subfunction “do”. Each invocation of “do” generates subtrees represented as GTs for the parents all of whose children are leaves, then for those leaves all branches leading to them are pruned and their GTs are purged. “do” terminates when there are no such parents.

For the tree t0 above, the initial vector of GTs is:

      ⍝
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬    ─┬──────┐
│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│┌───┐│     │┌────┐│
││─ 0│││─ 1│││─ 2│││─ 3│││─ 4│││─ 5│││─ 6│││─ 7││ ... ││─ 19││
│└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│└───┘│     │└────┘│
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴    ─┴──────┘

After the first invocation of “do”, the resultant vector of GTs is:

      ⍝
┌─────┬─────┬─────┬─────┬─────────────┬─────────────┬─────────────┬─────────────┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐
│┌───┐│┌───┐│┌───┐│┌───┐│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│┌─────┬─────┐│0│0│0│0│0│0│0│0│0│0│0│0│
││─ 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│0│0│0│0│0│0│0│0│0│0│0│0│0│0│0│
││─ 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 vector 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 vector 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 vector with 1s indicating where subtree roots are located. The result is is a character vector 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

“root” applies to a 1-row character matrix and a boolean vector with 1s indicating where subtree roots are located (same as the argument for “connect”). It produces a character 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 character matrix to the right edge of the matrix. 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│
└────────┴────────┴──────────┴───────────┴────────────┘

_________________________

Substantially the same contents previously appeared as the J Wiki essay Tree Display. See also the write-up on trees in http://dfns.dyalog.com/n_Trees.htm.