Appendix: Reference

Appendix: Reference#

Quick reference for the algorithms in this tutorial.

Finding Children:

⍸p∊i

Finding Leaves:

~p∊⍨⍳≢p

Trimming Branches:

i@i⊢p

or

p[i]←i

Finding Roots:

I⍣≡⍨p

Selecting Sub-Trees:

i∊⍨p I@{~⍵∊i}⍣≡⍳≢p

Shuffling:

perm⍳p[perm]

Mirroring:

(¯1+≢-⌽)p

Depth Vector to Parent Vector:

DepthToParent←{d←⍵
    p←⍳≢d
    _←2{p[⍵]←⍺[⍺⍸⍵]}/⊂⍤⊢⌸d
    p
}

Finding Depths:

Depths←{ ⍝ find the depths of each node in a parent vector
    ⍝ ←: a vector of the depths of each node in the input
    p←⍵    ⍝ input parent vector
    depths←(≢p)⍴0
    StepUp←{ ⍝ step up the tree and increment depths
        q←p[⍵]
        depths+←⍵≠q
        q
    }
    _←StepUp⍣≡⍳≢p
    depths
}
(Depths p) PPV p

Parent Vector to Depth Vector:

ParentToDepth←{ ⍝ recover the depths and DFPT ordering of a parent vector
    ⍝ ←: a two element vector consisting of (1) the depths of each node and (2) the permutation vector for DFPT order
    p←⍵    ⍝ input parent vector
    paths←(≢p)0⍴⍬
    depths←(≢p)⍴0
    StepUp←{
        paths,←⍵
        q←p[⍵]
        depths+←⍵≠q
        q
    }
    _←StepUp⍣≡⍳≢p
    order←⍋⌽¨(depths+1)⊂⍤↑⍤¯1⊢paths
    depths order
}

Joining Trees into a Forest:

forest←⊃,/trees+0,+\¯1↓≢¨trees
data←⊃,/data

Splitting a Forest into Trees:

trees←roots{⊂⍵-(+\~forest∊⍵)[⍵]}⌸forest
data←roots{⊂⍵}⌸data

Deleting Nodes:

p←(⍸mask)(⊢-1+⍸)(~mask)/p
data←mask⌿data

Parent Vector to Nested Representation:

ParentToNested←{ ⍝ convert a parent vector to a nested representation
    p←⍵    ⍝ input parent vector
    ⍺←⊂⍤,¨⍳≢p
    r←⍺    ⍝ values to place at nodes (by default, their indices in the parent vector)
    d←Depths p
    maxDepth←⌈/d
    maxDepth=0: r
    DoLayer←{
        i←⍸d=⍵
        _←p[i]{r[⍺],←⊂r[⍵]}⌸i
        1    ⍝ the interpreter will complain if we don't provide a result
    }
    _←DoLayer¨⌽1+⍳maxDepth
    (p=⍳≢p)/r
}