Tree traversal

Next topic: Permutations and permutation groups

Each Tensor in Redberry is a container of its child tensors, so any complicated expression becomes a hierarchical tree of such containers. Iteration over direct child elements of a tensor described in Tensors and Indices. Besides, there are special tools for iteration and modification over a whole tree.

Traversing expression tree

There are two basic ways to perform a depth-first search on expression tree: 

def t = 'a + Sin[x + y]'.t
def elements = []
t.parentAfterChild { a -> elements << a }
println elements

   > [a, x, y, x+y, Sin[x+y], a+Sin[x+y]]

elements = []
t.parentBeforeChild { a -> elements << a }
println elements

   > [a+Sin[y+x], a, Sin[y+x], y+x, y, x]
This example illustrates steps of parent-after-child and parent-before-child iteration modes.

Consider another example: 

def allSymbols = { expr ->
    def r = [] //result
    expr.parentAfterChild { e ->
        if (e.class == SimpleTensor && e.indices.size() == 0)
            r << e
    }
    r
}

def t = 'f_ij*(x*t^i + k^i*a)*c*x'.t
println allSymbols(t)

    > [x, c, a, x]
A function allSymbols(expr) takes an expression and returns a list of all symbols (without any indices) that contained in expr. If one need to take only unique symbols one can do 
println allSymbols(t) as Set

    > [x, c, a]

Modifying expression tree

Modification of expression tree can be performed in the same way. As an example, lets consider a naive implementation of a substitution transformation: 

def subs = { expr, substitution ->
    expr.transformParentAfterChild { element ->
        def mapping = (substitution[0] % element).first
        //if mapping exists apply it and return
        if (mapping) mapping >> substitution[1]
        else element
    }
}

def t = 'z_m*Cos[x_m*y^m - x_n*(z^n + t^n)] + t_m'.t
println subs(t, 'z_a + t_a = y_a'.t)

   > y_m
Here, the function subs(expr, s) applies substitution rule s to the expression expr. Method .transformParentAfterChild(function) applies function to each part of expression (starting from deepest children nodes) and returns the result.

The key aspect of parent-after-child modification, is that if child node is changed, than its parent node will be reduced to standard form before it will be shown. In the above example the first modification will be performed on the sum z^n + t^n, which will be replaced with y^n. After this modification, the whole branch of the expression tree, which contains this term, will be permanently reduced to the standard form. So, when iteration will reach the argument of cosine, which will be x_m*y^m - x_n*y^n, it will be reduced to zero. On the next step the cosine receives zero as an argument and reduces to 1. On the last step of the iteration, it finally becomes possible to replace obtained z_m + t_m with y_m.

It should be noted that when modifying expression using tree traversal, Rebderry will automatically take care about correct dummy indices relabelling when necessary.

See also