Basics, printing, and visualization

As described in the introduction, RootedTrees are represented using level sequences, i.e., AbstractVectors containing the distances of the nodes from the root. For example,

using RootedTrees
for t in RootedTreeIterator(4)
    println(t)
end

RootedTree{Int64}: [1, 2, 3, 4]
RootedTree{Int64}: [1, 2, 3, 3]
RootedTree{Int64}: [1, 2, 3, 2]
RootedTree{Int64}: [1, 2, 2, 2]

Visualization of trees

Depending on your background, you may be more familiar with the classical notation used in the books of Butcher or Hairer & Wanner. You can get these representation via butcher_representation.

for t in RootedTreeIterator(4)
    println(butcher_representation(t))
end

[[[τ]]]
[[τ²]]
[[τ]τ]
[τ³]

Remember that you can change the printing style globally via RootedTrees.set_printing_style.

When working with LaTeX, it can be convenient to use the LaTeX package forest to draw trees. You can find more information about this in the docstring of RootedTrees.latexify. For example,

for t in RootedTreeIterator(4)
    println(RootedTrees.latexify(t))
end

\rootedtree[.[.[.[.]]]]
\rootedtree[.[.[.][.]]]
\rootedtree[.[.[.]][.]]
\rootedtree[.[.][.][.]]

This results in the following LaTeX output:

To get a human-readable output, you can use RootedTrees.set_latexify_style. This can be particularly helpful when working in Jupyter notebooks, e.g., by passing the output of latexify to IPython.display.Latex.

RootedTrees.set_latexify_style("butcher")

for t in RootedTreeIterator(4)
    println(RootedTrees.latexify(t))
end

RootedTrees.set_latexify_style("forest")

for t in RootedTreeIterator(4)
    println(RootedTrees.latexify(t))
end

[[[τ]]]
[[τ²]]
[[τ]τ]
[τ³]
\rootedtree[.[.[.[.]]]]
\rootedtree[.[.[.][.]]]
\rootedtree[.[.[.]][.]]
\rootedtree[.[.][.][.]]

If you want to visualize individual trees, you can also use our plot recipes for Plots.jl.

using Plots
t = rootedtree([1, 2, 3, 3, 2])
plot(t)

To get the elementary differential, corresponding to a RootedTree, as a LaTeXString, you can use elementary_differential_latexstring.

for t in RootedTreeIterator(4)
    println(elementary_differential_latexstring(t))
end

$f^{\prime}f^{\prime}f^{\prime}f$
$f^{\prime}f^{\prime\prime}(f, f)$
$f^{\prime\prime}(f^{\prime}f, f)$
$f^{\prime\prime\prime}(f, f, f)$

In LaTeX this results in the following output:

Similarly, to get the elementary weight, corresponding to a RootedTree, as a LaTeXString, you can use elementary_weight_latexstring.

for t in RootedTreeIterator(4)
    println(elementary_weight_latexstring(t))
end

$\sum_{d, e, f}b_{d}a_{d,e}a_{e,f}c_{f}$
$\sum_{d, e}b_{d}a_{d,e}c_{e}^{2}$
$\sum_{d, e}b_{d}a_{d,e}c_{e}c_{d}$
$\sum_{d}b_{d}c_{d}^{3}$

Number of trees

The number of rooted trees grows exponentially. Please consider this when iterating over some set of rooted trees. The implementations in RootedTrees.jl are reasonably efficient, but an exponential growth will always win in the end.

The function count_trees iterates over rooted trees explicitly. Thus, it provides a lower bound on the computational complexity of operations on all trees. For example,

julia> using RootedTrees
julia> @time count_trees(10)  0.000012 seconds (1 allocation: 144 bytes)
719
julia> @time count_trees(20)  0.203146 seconds (1 allocation: 224 bytes)
12826228

A nice way to create and print tables of properties of trees is by using the Julia package PrettyTables.jl.

julia> using RootedTrees, PrettyTables
julia> orders = 1:101:10
julia> pretty_table(hcat(orders, count_trees.(orders)), header=["Order", "# Trees"])┌───────┬─────────┐
│ Order │ # Trees │
├───────┼─────────┤
│     1 │       1 │
│     2 │       1 │
│     3 │       2 │
│     4 │       4 │
│     5 │       9 │
│     6 │      20 │
│     7 │      48 │
│     8 │     115 │
│     9 │     286 │
│    10 │     719 │
└───────┴─────────┘

To get the corresponding number of Runge-Kutta (RK) order conditions, we must sum up the number of trees, i.e.,

julia> using RootedTrees, PrettyTables
julia> orders = 1:101:10
julia> pretty_table(hcat(orders, cumsum(count_trees.(orders))), header=["Order", "# RK Order Conditions"])┌───────┬───────────────────────┐
│ Order │ # RK Order Conditions │
├───────┼───────────────────────┤
│     1 │                     1 │
│     2 │                     2 │
│     3 │                     4 │
│     4 │                     8 │
│     5 │                    17 │
│     6 │                    37 │
│     7 │                    85 │
│     8 │                   200 │
│     9 │                   486 │
│    10 │                  1205 │
└───────┴───────────────────────┘

We can also visualize the exponential growth.

using Plots
orders = 1:15
scatter(orders, count_trees.(orders), yscale=:log10,
        xguide="Order", yguide="Number of Trees")

Colored trees

A lot of the same functionality is also available for colored trees. Note that the additional choice of different colors increases the number of trees significantly. For example, the number of trees of order 3 increases from

for t in RootedTreeIterator(3)
    println(t)
end

RootedTree{Int64}: [1, 2, 3]
RootedTree{Int64}: [1, 2, 2]

to

for t in BicoloredRootedTreeIterator(3)
    println(t)
end

ColoredRootedTree{Int64}: ([1, 2, 3], Bool[0, 0, 0])
ColoredRootedTree{Int64}: ([1, 2, 3], Bool[1, 0, 0])
ColoredRootedTree{Int64}: ([1, 2, 3], Bool[0, 1, 0])
ColoredRootedTree{Int64}: ([1, 2, 3], Bool[1, 1, 0])
ColoredRootedTree{Int64}: ([1, 2, 3], Bool[0, 0, 1])
ColoredRootedTree{Int64}: ([1, 2, 3], Bool[1, 0, 1])
ColoredRootedTree{Int64}: ([1, 2, 3], Bool[0, 1, 1])
ColoredRootedTree{Int64}: ([1, 2, 3], Bool[1, 1, 1])
ColoredRootedTree{Int64}: ([1, 2, 2], Bool[0, 0, 0])
ColoredRootedTree{Int64}: ([1, 2, 2], Bool[1, 0, 0])
ColoredRootedTree{Int64}: ([1, 2, 2], Bool[0, 1, 0])
ColoredRootedTree{Int64}: ([1, 2, 2], Bool[1, 1, 0])
ColoredRootedTree{Int64}: ([1, 2, 2], Bool[0, 1, 1])
ColoredRootedTree{Int64}: ([1, 2, 2], Bool[1, 1, 1])

RootedTrees.latexify also supports bicolored rooted trees:

for t in BicoloredRootedTreeIterator(3)
    println(RootedTrees.latexify(t))
end

\rootedtree[.[.[.]]]
\rootedtree[o[.[.]]]
\rootedtree[.[o[.]]]
\rootedtree[o[o[.]]]
\rootedtree[.[.[o]]]
\rootedtree[o[.[o]]]
\rootedtree[.[o[o]]]
\rootedtree[o[o[o]]]
\rootedtree[.[.][.]]
\rootedtree[o[.][.]]
\rootedtree[.[o][.]]
\rootedtree[o[o][.]]
\rootedtree[.[o][o]]
\rootedtree[o[o][o]]

The style can be adapted as well via RootedTrees.set_latexify_style.

RootedTrees.set_latexify_style("butcher")

for t in BicoloredRootedTreeIterator(3)
    println(RootedTrees.latexify(t))
end

RootedTrees.set_latexify_style("forest")

for t in BicoloredRootedTreeIterator(3)
    println(RootedTrees.latexify(t))
end

[[τ₀]₀]₀
[[τ₀]₀]₁
[[τ₀]₁]₀
[[τ₀]₁]₁
[[τ₁]₀]₀
[[τ₁]₀]₁
[[τ₁]₁]₀
[[τ₁]₁]₁
[τ₀²]₀
[τ₀²]₁
[τ₁τ₀]₀
[τ₁τ₀]₁
[τ₁²]₀
[τ₁²]₁
\rootedtree[.[.[.]]]
\rootedtree[o[.[.]]]
\rootedtree[.[o[.]]]
\rootedtree[o[o[.]]]
\rootedtree[.[.[o]]]
\rootedtree[o[.[o]]]
\rootedtree[.[o[o]]]
\rootedtree[o[o[o]]]
\rootedtree[.[.][.]]
\rootedtree[o[.][.]]
\rootedtree[.[o][.]]
\rootedtree[o[o][.]]
\rootedtree[.[o][o]]
\rootedtree[o[o][o]]

Plotting is of course also implemented for colored rooted trees.

using Plots
t = rootedtree([1, 2, 3, 3, 2, 2], Bool[0, 0, 1, 0, 1, 0])
plot(t)

The general implementation supports more than two colors, e.g.,

using Plots
t = rootedtree([1, 2, 3, 3, 2], [1, 2, 3, 4, 5])
plot(t)

However, the support for multiple colors is limited at the moment, e.g., concerning efficient iterators.