# RootedTrees

A collection of functionality around rooted trees to generate order conditions for Runge-Kutta methods in Julia. This package also provides basic functionality for BSeries.jl.

## API Documentation

The API of RootedTrees.jl is documented in the following. Additional information on each function is available in their docstrings and in the online documentation.

### Construction

`RootedTree`

s are represented using level sequences, i.e., `AbstractVector`

s
containing the distances of the nodes from the root, see

- Beyer, Terry, and Sandra Mitchell Hedetniemi. "Constant time generation of rooted trees". SIAM Journal on Computing 9.4 (1980): 706-712. DOI: 10.1137/0209055

`RootedTree`

s can be constructed from their level sequence using

```
julia> t = rootedtree([1, 2, 3, 2])
RootedTree{Int64}: [1, 2, 3, 2]
```

In the notation of Butcher (Numerical Methods for ODEs, 2016),
this tree can be written as `[[τ] τ]`

or `(τ ∘ τ) ∘ (τ ∘ τ)`

, where
`∘`

is the non-associative Butcher product of `RootedTree`

s, which is also
implemented.

To get the representation of a `RootedTree`

introduced by Butcher, use `butcher_representation`

:

```
julia> t = rootedtree([1, 2, 3, 4, 3, 3, 2, 2, 2, 2, 2])
RootedTree{Int64}: [1, 2, 3, 4, 3, 3, 2, 2, 2, 2, 2]
julia> butcher_representation(t)
"[[[τ]τ²]τ⁵]"
```

There are also some simple plot recipes for Plots.jl.
Thus, you can visualize a rooted tree `t`

using `plot(t)`

when `using Plots`

.

Additionally, there is an un-exported function `RootedTrees.latexify`

that can
generate LaTeX code for a rooted tree `t`

based on the LaTeX package
forest. The relevant code that needs to be included
in the preamble can be obtained from the docstring of `RootedTrees.latexify`

(type `?`

and `RootedTrees.latexify`

in the Julia REPL). The same format is
used when you are `using Latexify`

and their function `latexify`

, see
Latexify.jl.

`RootedTree`

s

Iteration over A `RootedTreeIterator(order::Integer)`

can be used to iterate efficiently
over all `RootedTree`

s of a given `order`

.

Be careful that the iterator is stateful for efficiency reasons, so you might
need to use `copy`

appropriately, e.g.,

```
julia> map(identity, RootedTreeIterator(4))
4-element Array{RootedTrees.RootedTree{Int64,Array{Int64,1}},1}:
RootedTree{Int64}: [1, 2, 2, 2]
RootedTree{Int64}: [1, 2, 2, 2]
RootedTree{Int64}: [1, 2, 2, 2]
RootedTree{Int64}: [1, 2, 2, 2]
julia> map(copy, RootedTreeIterator(4))
4-element Array{RootedTrees.RootedTree{Int64,Array{Int64,1}},1}:
RootedTree{Int64}: [1, 2, 3, 4]
RootedTree{Int64}: [1, 2, 3, 3]
RootedTree{Int64}: [1, 2, 3, 2]
RootedTree{Int64}: [1, 2, 2, 2]
```

### Functions on Trees

The usual functions on `RootedTree`

s are implemented, cf.
Butcher (Numerical Methods for ODEs, 2016).

`order(t::RootedTree)`

: The order of a`RootedTree`

, i.e., the length of its level sequence.`σ(t::RootedTree)`

or`symmetry(t)`

: The symmetry`σ`

of a rooted tree, i.e., the order of the group of automorphisms on a particular labelling (of the vertices) of`t`

.`γ(t::RootedTree)`

or`density(t)`

: The density`γ(t)`

of a rooted tree, i.e., the product over all vertices of`t`

of the order of the subtree rooted at that vertex.`α(t::RootedTree)`

: The number of monotonic labelings of`t`

not equivalent under the symmetry group.`β(t::RootedTree)`

: The total number of labelings of`t`

not equivalent under the symmetry group.

Additionally, functions on trees connected to Runge-Kutta methods are implemented.

`elementary_weight(t, A, b, c)`

: Compute the elementary weight Φ(`t`

) of`t::RootedTree`

for the Butcher coefficients`A, b, c`

of a Runge-Kutta method.`derivative_weight(t, A, b, c)`

: Compute the derivative weight (ΦᵢD)(`t`

) of`t`

for the Butcher coefficients`A, b, c`

of a Runge-Kutta method.`residual_order_condition(t, A, b, c)`

: The residual of the order condition`(Φ(t) - 1/γ(t)) / σ(t)`

with elementary weight`Φ(t)`

, density`γ(t)`

, and symmetry`σ(t)`

of the rooted tree`t`

for the Runge-Kutta method with Butcher coefficients`A, b, c`

.

## Brief Changelog

- v2.16: The LaTeX printing of rooted trees changed to allow representing
colored rooted trees. Please update your LaTeX preamble as described in
the docstring of
`RootedTrees.latexify`

. - v2.0: Rooted trees are considered up to isomorphisms introduced by shifting each coefficient of their level sequence by the same number.

## Referencing

If you use RootedTrees.jl for your research, please cite the paper

```
@article{ketcheson2022computing,
title={Computing with {B}-series},
author={Ketcheson, David I and Ranocha, Hendrik},
journal={ACM Transactions on Mathematical Software},
year={2022},
month={12},
doi={10.1145/3573384},
eprint={2111.11680},
eprinttype={arXiv},
eprintclass={math.NA}
}
```

In addition, you can also refer to RootedTrees.jl directly as

```
@misc{ranocha2019rootedtrees,
title={{RootedTrees.jl}: {A} collection of functionality around rooted trees
to generate order conditions for {R}unge-{K}utta methods in {J}ulia
for differential equations and scientific machine learning ({SciM}L)},
author={Ranocha, Hendrik and contributors},
year={2019},
month={05},
howpublished={\url{https://github.com/SciML/RootedTrees.jl}},
doi={10.5281/zenodo.5534590}
}
```