This shows you the differences between two versions of the page.
|
documentation:guide:tree_traversal [2015/11/21 12:33] |
documentation:guide:tree_traversal [2015/11/21 12:33] (current) |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| + | ====== Tree traversal ====== | ||
| + | <html> | ||
| + | <div class="text-right" style="font-size: 15px; "> | ||
| + | </html> | ||
| + | Next topic: [[documentation:guide:permutations_and_permutation_groups]] | ||
| + | <html> | ||
| + | <span class="glyphicon glyphicon-arrow-right"></span> | ||
| + | </div> | ||
| + | </html> | ||
| + | |||
| + | ---- | ||
| + | |||
| + | Each [[documentation:ref: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 [[documentation:guide: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: | ||
| + | <sxh groovy; gutter: true> | ||
| + | def t = 'a + Sin[x + y]'.t | ||
| + | def elements = [] | ||
| + | t.parentAfterChild { a -> elements << a } | ||
| + | println elements | ||
| + | </sxh> | ||
| + | <sxh plain; gutter: false> | ||
| + | > [a, x, y, x+y, Sin[x+y], a+Sin[x+y]] | ||
| + | </sxh> | ||
| + | <sxh groovy; gutter: true; first-line: 5> | ||
| + | elements = [] | ||
| + | t.parentBeforeChild { a -> elements << a } | ||
| + | println elements | ||
| + | </sxh> | ||
| + | <sxh plain; gutter: false> | ||
| + | > [a+Sin[y+x], a, Sin[y+x], y+x, y, x] | ||
| + | </sxh> | ||
| + | This example illustrates steps of parent-after-child and parent-before-child iteration modes. | ||
| + | |||
| + | Consider another example: | ||
| + | <sxh groovy; gutter: true> | ||
| + | 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) | ||
| + | </sxh> | ||
| + | <sxh plain; gutter: false> | ||
| + | > [x, c, a, x] | ||
| + | </sxh> | ||
| + | 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 | ||
| + | <sxh groovy; gutter: true; first-line: 12> | ||
| + | println allSymbols(t) as Set | ||
| + | </sxh> | ||
| + | <sxh plain; gutter: false> | ||
| + | > [x, c, a] | ||
| + | </sxh> | ||
| + | |||
| + | ====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: | ||
| + | <sxh groovy; gutter: true> | ||
| + | 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) | ||
| + | </sxh> | ||
| + | <sxh plain; gutter: false> | ||
| + | > y_m | ||
| + | </sxh> | ||
| + | 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 [[documentation:guide:standard_form_of_mathematical_expressions|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==== | ||
| + | * Related guides: [[documentation:guide:tensors_and_indices]], [[documentation:guide:mappings_of_indices]] | ||
| + | * JavaDocs: [[http://api.redberry.cc/redberry/1.1.9/java-api/cc/redberry/core/tensor/iterator/package-summary.html| Tree iterators]], [[http://api.redberry.cc/redberry/1.1.9/java-api/cc/redberry/core/transformations/substitutions/SubstitutionIterator.html| SubstitutionIterator]] | ||
| + | * Source code: [[https://bitbucket.org/redberry/redberry/src/tip/core/src/main/java/cc/redberry/core/tensor/iterator|Tree iterators]], [[https://bitbucket.org/redberry/redberry/src/tip/core/src/main/java/cc/redberry/core/transformations/substitutions/SubstitutionIterator.java|SubstitutionIterator.java]] | ||