RootedTrees.jl API

RootedTrees

Construct rooted and colored rooted trees, enumerate their combinatorial structures, and evaluate order conditions for time-integration methods.

AdditiveRungeKuttaMethod(rks)
AdditiveRungeKuttaMethod(As, bs, cs=map(A -> vec(sum(A, dims=2)), As))

Represent an additive Runge-Kutta method with collections of Butcher coefficients As, bs, and cs. Alternatively, you can pass a collection of RungeKuttaMethods to the constructor. If the cs are not provided, the usual "row sum" requirement of consistency with autonomous problems is applied.

Fields

• rks: The Runge-Kutta method for each additive component.

Arguments

• rks: A collection of RungeKuttaMethods. Coefficients are promoted to a shared element type.
• As: A collection of stage-coefficient matrices.
• bs: A collection of final-update-weight vectors.
• cs=map(A -> vec(sum(A, dims=2)), As): A collection of stage-abscissa vectors; defaults to the row sums of the corresponding matrices.

An additive Runge-Kutta method applied to the ODE problem

\[ u'(t) = \sum_\nu f^\nu(t, u(t))\]

has the form

\[\begin{aligned} y^i &= u^n + \Delta t \sum_\nu \sum_j a^\nu_{i,j} f^\nu(t^n + c_j \Delta t, y^j), \\ u^{n+1} &= u^n + \Delta t \sum_\nu \sum_i b^\nu_{i} f^\nu(t^n + c_i \Delta t, y^i). \end{aligned}\]

In particular, additive Runge-Kutta methods are a superset of partitioned RK methods, which are applied to partitioned problems of the form

\[ (u^1)'(t) = f^1(t, u^1, u^2), \quad (u^2)'(t) = f^2(t, u^1, u^2).\]

Examples

julia> ark = AdditiveRungeKuttaMethod(
           [[0.0;;], [1.0;;]], [[1.0], [1.0]]);

julia> length(ark.rks)
2

References

• A. L. Araujo, A. Murua, and J. M. Sanz-Serna. "Symplectic Methods Based on Decompositions". SIAM Journal on Numerical Analysis 34.5 (1997): 1926-1947. DOI: 10.1137/S0036142995292128

BicoloredRootedTree{T<:Integer}

Alias for ColoredRootedTree whose color_sequence contains Bool values. false and true are conventionally used for the two colors.

Fields

• level_sequence: Integer level of every node in depth-first order.
• color_sequence: Boolean color for each node, with the same axes as level_sequence.
• iscanonical: Whether both sequences use the package's canonical ordering.

Arguments

• level_sequence: Integer vector satisfying the rooted-tree level-sequence rules.
• color_sequence: Boolean vector with the same axes as level_sequence.

Examples

julia> t = rootedtree([1, 2], Bool[false, true]);

julia> t isa BicoloredRootedTree
true

See also ColoredRootedTree, RootedTree, rootedtree.

BicoloredRootedTreeIterator(order::Integer)

Iterator over all bicolored rooted trees of given order. The returned trees are views to an internal tree modified during the iteration. If the returned trees shall be stored or modified during the iteration, a copy has to be made.

Arguments

• order: Number of nodes in every yielded tree.

Iterator interface

This iterator implements iterate, eltype, and length. length counts only canonical bicolored trees. Iteration reuses one mutable tree buffer; copy a yielded tree before retaining it.

Examples

julia> trees = collect(BicoloredRootedTreeIterator(1));

julia> length(trees)
2

julia> first(trees).color_sequence isa AbstractVector{Bool}
true

ColoredRootedTree(level_sequence, color_sequence, is_canonical::Bool=false)

Represent a colored rooted tree using its level sequence. The single-colored version is RootedTree.

Fields

• level_sequence: Integer level of every node in depth-first order.
• color_sequence: One color for each node, with the same axes as level_sequence.
• iscanonical: Whether the level and color sequences are in the package's canonical ordering.

Arguments

• level_sequence: An integer vector satisfying the rooted-tree level-sequence rules.
• color_sequence: A vector of node colors with the same axes as level_sequence.
• is_canonical=false: Whether the caller guarantees canonical ordering.

See also BicoloredRootedTree, rootedtree.

References

• Terry Beyer and Sandra Mitchell Hedetniemi. "Constant time generation of rooted trees". SIAM Journal on Computing 9.4 (1980): 706-712. DOI: 10.1137/0209055
• A. L. Araujo, A. Murua, and J. M. Sanz-Serna. "Symplectic Methods Based on Decompositions". SIAM Journal on Numerical Analysis 34.5 (1997): 1926–1947. DOI: 10.1137/S0036142995292128

PartitionForestIterator(t::AbstractRootedTree, edge_set)

Lazy iterator representation of the partition_forest of the rooted tree t. Similar to RootedTreeIterator, you should copy the iterates if you want to store or modify them during the iteration since they may be views to internal caches.

Arguments

• t::AbstractRootedTree: Tree whose partition forests are enumerated.
• edge_set: Boolean vector of length order(t) - 1. Each false edge is removed in the next forest.

Iterator interface

This iterator implements iterate, eltype, and length. It yields one tree for each possible forest obtained by removing a suffix-compatible set of edges. The yielded tree uses internal working storage; copy it before storing it.

Examples

julia> length(PartitionForestIterator(rootedtree([1, 2, 2]), Bool[false, true]))
2

See also partition_forest, partition_skeleton, and PartitionIterator.

References

Section 2.3 of

• Philippe Chartier, Ernst Hairer, Gilles Vilmart (2010) Algebraic Structures of B-series. Foundations of Computational Mathematics DOI: 10.1007/s10208-010-9065-1

PartitionIterator(t::AbstractRootedTree)

Iterator over all partition forests and skeletons of the rooted tree t. This is basically a pure iterator version of all_partitions. In particular, the partition forest may only be realized as an iterator. Similar to RootedTreeIterator, you should copy the iterates if you want to store or modify them during the iteration since they may be views to internal caches.

Arguments

• t::AbstractRootedTree: Rooted tree whose partitions should be enumerated.

Iterator interface

This iterator implements iterate, eltype, and length. Each value is a (forest_iterator, skeleton) pair. The forest iterator and skeleton use working storage and must be copied before being retained across iterations.

Examples

julia> length(PartitionIterator(rootedtree([1, 2, 2])))
4

See also partition_forest, partition_skeleton, and PartitionForestIterator.

References

Section 2.3 of

• Philippe Chartier, Ernst Hairer, Gilles Vilmart (2010) Algebraic Structures of B-series. Foundations of Computational Mathematics DOI: 10.1007/s10208-010-9065-1

RootedTree(level_sequence, is_canonical::Bool=false)

Represent a rooted tree using its level sequence.

Fields

• level_sequence: Integer level of every node in depth-first order. The first entry is the root level; every later entry must be larger than the root level and at most one greater than its predecessor.
• iscanonical: Whether level_sequence is already in the package's canonical ordering. Call rootedtree when this invariant is not known.

Arguments

• level_sequence: An integer vector that stores the tree representation.
• is_canonical=false: Whether the caller guarantees canonical ordering.

Examples

julia> t = rootedtree([1, 2, 2]);

julia> t.level_sequence
3-element Vector{Int64}:
 1
 2
 2

References

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

RootedTreeIterator(order::Integer)

Iterator over all rooted trees of given order. The returned trees are views to an internal tree modified during the iteration. If the returned trees shall be stored or modified during the iteration, a copy has to be made.

Arguments

• order: Number of nodes in every yielded tree.

Iterator interface

This iterator implements iterate, eltype, and length. Iteration reuses one mutable tree buffer; copy a yielded tree before retaining it. Computing length enumerates the trees.

Examples

julia> trees = collect(RootedTreeIterator(2));

julia> length(trees)
1

julia> butcher_representation(first(trees))
"[τ]"

RosenbrockMethod(γ, A, b, c=vec(sum(A, dims=2)))

Represent a Rosenbrock (or Rosenbrock-Wanner, ROW) method with coefficients γ, A, b, and c. If c is not provided, the usual "row sum" requirement of consistency with autonomous problems is applied.

Fields

• γ: Rosenbrock coupling matrix.
• A: Stage-coefficient matrix.
• b: Final-update weights.
• c: Stage abscissae.

Arguments

• γ: Rosenbrock coupling matrix.
• A: Square stage-coefficient matrix.
• b: Final-update weights, one per stage.
• c=vec(sum(A, dims=2)): Stage abscissae, one per stage. The default uses row sums of A.

Examples

julia> ros = RosenbrockMethod([1.0;;], [0.0;;], [1.0]);

julia> ros.c
1-element Vector{Float64}:
 0.0

Reference

• Ernst Hairer, Gerhard Wanner. Solving ordinary differential equations II: Stiff and differential-algebraic problems. Springer, 2010. Section IV.7

RungeKuttaMethod(A, b, c=vec(sum(A, dims=2)))

Represent a Runge-Kutta method with Butcher coefficients A, b, and c. If c is not provided, the usual "row sum" requirement of consistency with autonomous problems is applied.

Fields

• A: Stage-coefficient matrix.
• b: Final-update weights.
• c: Stage abscissae.

Arguments

• A: Square matrix of stage coefficients.
• b: Final-update weights, one per stage.
• c=vec(sum(A, dims=2)): Stage abscissae, one per stage. The default uses row sums of A.

Examples

julia> rk = RungeKuttaMethod([0.0 0.0; 1.0 0.0], [0.5, 0.5]);

julia> rk.c
2-element Vector{Float64}:
 0.0
 1.0

SplittingIterator(t::RootedTree)

Iterator over all splitting forests and subtrees of the rooted tree t. This is basically an iterator version of all_splittings.

Arguments

• t: Rooted tree whose ordered subtrees define the splittings.

Iterator interface

This iterator implements iterate, eltype, and length. Each iterate is a (forest, subtree) pair. The forest vector and its trees are mutable working storage; copy values that must outlive the next iteration.

Examples

julia> first(collect(SplittingIterator(rootedtree([1, 2, 2]))))[2] isa RootedTree
true

See also partition_forest and partition_skeleton.

References

Section 2.2 of

• Philippe Chartier, Ernst Hairer, Gilles Vilmart (2010) Algebraic Structures of B-series. Foundations of Computational Mathematics DOI: 10.1007/s10208-010-9065-1

SubtreeIterator(t::AbstractRootedTree)

Lazy iterator representation of the subtrees of the rooted tree t. Similar to RootedTreeIterator, you should copy the iterates if you want to store or modify them during the iteration since they may be views to internal caches.

Arguments

• t: Rooted tree whose child subtrees should be traversed.

Iterator interface

This lazy iterator guarantees the two-argument iterate protocol. It yields each subtree rooted at a child of t in level-sequence order. The yielded trees may share storage with t; copy a value before retaining or mutating it.

Use a for loop or a manual iterate consumer. This type does not guarantee length or eltype and is therefore not intended to be materialized with collect.

Examples

julia> sum(1 for _ in SubtreeIterator(rootedtree([1, 2, 2])))
2

==(t1::ColoredRootedTree, t2::ColoredRootedTree)

Compares two rooted trees based on their level (first) and color (second) sequences while considering equivalence classes given by different root indices.

==(t1::RootedTree, t2::RootedTree)

Compares two rooted trees based on their level sequences while considering equivalence classes given by different root indices.

Examples

julia> t1 = rootedtree([1, 2, 3]);

julia> t2 = rootedtree([2, 3, 4]);

julia> t3 = rootedtree([1, 2, 2]);

julia> t1 == t2
true

julia> t1 == t3
false

t1 ∘ t2

The non-associative Butcher product of rooted trees. It is formed by adding an edge from the root of t1 to the root of t2.

See also butcher_product!.

Reference: Section 301 of

• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2016.

isless(t1::ColoredRootedTree, t2::ColoredRootedTree)

Compares two colored rooted trees using a lexicographical comparison of their level (first) and color (second) sequences while considering equivalence classes given by different root indices.

isless(t1::RootedTree, t2::RootedTree)

Compares two rooted trees using a lexicographical comparison of their level sequences while considering equivalence classes given by different root indices.

all_partitions(t::RootedTree)

Create all partition forests and skeletons of a rooted tree t. This returns vectors of the return values of partition_forest and partition_skeleton when looping over all possible edge sets.

Arguments

• t::RootedTree: Rooted tree whose edge partitions should be enumerated.

Returns

• NamedTuple: A pair of vectors (forests, skeletons). Corresponding entries describe the same edge set, and there are 2^(order(t) - 1) entries.

See also PartitionIterator.

Examples

julia> length(all_partitions(rootedtree([1, 2, 2])).forests)
4

References

Section 2.3 of

• Philippe Chartier, Ernst Hairer, Gilles Vilmart (2010) Algebraic Structures of B-series. Foundations of Computational Mathematics DOI: 10.1007/s10208-010-9065-1

all_splittings(t::RootedTree)

Create all splitting forests and subtrees associated to ordered subtrees of a rooted tree t.

Arguments

• t::RootedTree: Rooted tree whose ordered subtrees define the splittings.

Returns

• NamedTuple: Vectors forests and subtrees, with matching entries for every valid ordered splitting.

See also SplittingIterator.

Examples

julia> length(all_splittings(rootedtree([1, 2, 2])).forests)
5

References

Section 2.2 of

• Philippe Chartier, Ernst Hairer, Gilles Vilmart (2010) Algebraic Structures of B-series. Foundations of Computational Mathematics DOI: 10.1007/s10208-010-9065-1

butcher_product!(t, t1, t2)

Compute the non-associative Butcher product t = t1 ∘ t2 of rooted trees in-place. It is formed by adding an edge from the root of t1 to the root of t2.

Arguments

• t::RootedTree: Mutable destination with enough storage for the result.
• t1::RootedTree: Left factor of the Butcher product.
• t2::RootedTree: Right factor of the Butcher product.

Returns

• RootedTree: The mutated destination t, in canonical representation.

Examples

julia> t = rootedtree([1]);

julia> butcher_product!(t, rootedtree([1]), rootedtree([1]));

julia> butcher_representation(t)
"[τ]"

See also ∘ (available as \circ plus TAB).

Reference: Section 301 of

• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2016.

butcher_representation(t::RootedTree)

Return the representation of t::RootedTree introduced by Butcher as a string. Thus, the rooted tree consisting whose only vertex is the root itself is represented as τ. The representation of other trees is defined recursively; if t₁, t₂, ... tₙ are the subtrees of the rooted tree t, it is represented as t = [t₁ t₂ ... tₙ]. If multiple subtrees are the same, their number of occurrences is written as a power.

Arguments

• t::RootedTree: Rooted tree to represent.
• normalize::Bool=true: Whether repeated leaf subtrees should be written as superscript powers.

Returns

• String: Butcher bracket representation of t.

Examples

julia> rootedtree([1, 2, 3, 2]) |> butcher_representation
"[[τ]τ]"

julia> rootedtree([1, 2, 3, 3, 2]) |> butcher_representation
"[[τ²]τ]"

References

Section 300 of

• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008.

canonical_representation!(t::AbstractRootedTree)

Change the representation of the rooted tree t to the canonical one, i.e., the one with lexicographically biggest level sequence.

See also canonical_representation.

canonical_representation(t::AbstractRootedTree)

Returns a new tree using the canonical representation of the rooted tree t, i.e., the one with lexicographically biggest level sequence.

See also canonical_representation!.

check_canonical(t::AbstractRootedTree)

Check whether t is in canonical representation.

count_trees(order)

Count all rooted trees with order nodes.

Arguments

• order::Integer: Number of nodes in each tree. Must be nonnegative.

Returns

• Int: Number of canonical rooted trees of the requested order.

Throws

• ArgumentError: If order is negative.

Examples

julia> count_trees(4)
4

γ(t::AbstractRootedTree)
density(t::AbstractRootedTree)

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.

Arguments

• t::AbstractRootedTree: Rooted tree to inspect.

Returns

• Integer: Density of t; the empty tree has density one.

Examples

julia> density(rootedtree([1, 2, 2]))
3

Reference: Section 301 of

• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008.

derivative_weight(t::ColoredRootedTree, ark::AdditiveRungeKuttaMethod)

Compute the derivative weight (ΦᵢD)(t) of the AdditiveRungeKuttaMethod ark for the colored rooted tree t.

Arguments

• t::ColoredRootedTree: Colored rooted tree whose derivative weight is evaluated.
• ark::AdditiveRungeKuttaMethod: Additive Runge-Kutta coefficients used for the evaluation.

Returns

• AbstractVector: Derivative weight for each stage of ark.

References

• A. L. Araujo, A. Murua, and J. M. Sanz-Serna. "Symplectic Methods Based on Decompositions". SIAM Journal on Numerical Analysis 34.5 (1997): 1926–1947. DOI: 10.1137/S0036142995292128
• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008. Section 312

derivative_weight(t::RootedTree, ros::RosenbrockMethod)

Compute the derivative weight (ΦᵢD)(t) of the RosenbrockMethod ros for the rooted tree t.

Arguments

• t::RootedTree: Rooted tree whose derivative weight is evaluated.
• ros::RosenbrockMethod: Rosenbrock coefficients used for the evaluation.

Returns

• AbstractVector: Derivative weight for each stage of ros.

derivative_weight(t::RootedTree, rk::RungeKuttaMethod)

Compute the derivative weight (ΦᵢD)(t) of the RungeKuttaMethod rk with Butcher coefficients A, b, c for the rooted tree t.

Arguments

• t::RootedTree: Rooted tree whose derivative weight is evaluated.
• rk::RungeKuttaMethod: Runge-Kutta coefficients used for the evaluation.

Returns

• AbstractVector: Derivative weight for each stage of rk.

Reference: Section 312 of

• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008.

elementary_differential(t::RootedTree)

Deprecated alias for elementary_differential_latexstring.

Use elementary_differential_latexstring for new code.

Arguments

• t::RootedTree: Rooted tree whose elementary differential is represented.

Returns

• LaTeXString: Deprecated elementary-differential representation.

Examples

julia> elementary_differential(rootedtree([1])) isa AbstractString
true

elementary_differential_latexstring(t::RootedTree)

Returns the elementary differential as a LaTeXString from the package LaTeXStrings.jl.

Arguments

• t::RootedTree: Rooted tree to represent.

Returns

• LaTeXString: LaTeX representation of the elementary differential.

Examples

julia> elementary_differential_latexstring(rootedtree([1])) isa AbstractString
true

elementary_weight(t::ColoredRootedTree, ark::AdditiveRungeKuttaMethod)

Compute the elementary weight Φ(t) of the AdditiveRungeKuttaMethod ark for a colored rooted tree t.

Arguments

• t::ColoredRootedTree: Colored rooted tree whose weight is evaluated.
• ark::AdditiveRungeKuttaMethod: Additive Runge-Kutta coefficients used for the evaluation.

Returns

• Number: Elementary weight of t for ark.

References

• A. L. Araujo, A. Murua, and J. M. Sanz-Serna. "Symplectic Methods Based on Decompositions". SIAM Journal on Numerical Analysis 34.5 (1997): 1926–1947. DOI: 10.1137/S0036142995292128
• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008. Section 312

elementary_weight(t::RootedTree, ros::RosenbrockMethod)

Compute the elementary weight Φ(t) of the RosenbrockMethod ros for a rooted tree t.

Arguments

• t::RootedTree: Rooted tree whose weight is evaluated.
• ros::RosenbrockMethod: Rosenbrock coefficients used for the evaluation.

Returns

• Number: Elementary weight of t for ros.

elementary_weight(t::RootedTree, rk::RungeKuttaMethod)
elementary_weight(t::RootedTree, A::AbstractMatrix, b::AbstractVector, c::AbstractVector)

Compute the elementary weight Φ(t) of the RungeKuttaMethod rk with Butcher coefficients A, b, c for a rooted tree t.

Arguments

• t::RootedTree: Rooted tree whose weight is evaluated.
• rk::RungeKuttaMethod: Runge-Kutta coefficients used for the evaluation.
• A, b, c: Alternative coefficient arguments used by the compatibility method; they are passed to RungeKuttaMethod.

Returns

• Number: Elementary weight of t for the supplied method.

Reference: Section 312 of

• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008.

elementary_weight_latexstring(t::RootedTree)

Returns the elementary_weight as a LaTeXString from the package LaTeXStrings.jl.

Arguments

• t::RootedTree: Rooted tree to represent.

Returns

• LaTeXString: LaTeX representation of the elementary weight.

Examples

julia> elementary_weight_latexstring(rootedtree([1])) isa AbstractString
true

latexify(t::Union{RootedTree, BicoloredRootedTree})

Return a LaTeX representation of the rooted tree t. This makes use of the LaTeX package forest and assumes that you use the following LaTeX code in the preamble.

% Classical and colored Butcher trees based on
% https://tex.stackexchange.com/a/673436
\usepackage{forest}
\forestset{
    whitenode/.style={draw,             circle, minimum size=0.5ex, inner sep=0pt},
    blacknode/.style={draw, fill=black, circle, minimum size=0.5ex, inner sep=0pt},
    colornode/.style={draw, fill=#1,    circle, minimum size=0.5ex, inner sep=0pt},
    colornode/.default={red}
}
\newcommand{\blankforrootedtree}{\rule{0pt}{0pt}}
\NewDocumentCommand\rootedtree{o}{\begin{forest}
    for tree={grow'=90, thick, edge=thick, l sep=0.5ex, l=0pt, s sep=0.5ex},
    delay={
      where content={}{
        for children={no edge, before drawing tree={for tree={y-=5pt}}}
      }
      {
        where content={o}{content={\blankforrootedtree}, whitenode}{
          where content={.}{content={\blankforrootedtree}, blacknode}{}
        }
      }
    }
    [#1]
\end{forest}}

To change the style of latexify to a human-readable Butcher-representation, you can use RootedTrees.set_latexify_style.

Examples

julia> rootedtree([1, 2, 2]) |> RootedTrees.latexify |> println
\rootedtree[.[.][.]]

julia> rootedtree([1, 2, 3, 3, 2]) |> RootedTrees.latexify |> println
\rootedtree[.[.[.][.]][.]]

normalize_root!(t::AbstractRootedTree, root=one(eltype(t.level_sequence)))

Normalize the level sequence of the rooted tree t such that the root is set to root.

order(t::AbstractRootedTree)

Return the order of a rooted tree t, i.e., the number of nodes in its level sequence.

Arguments

• t::AbstractRootedTree: Rooted tree to inspect.

Returns

• Int: Number of nodes in t.

Examples

julia> order(rootedtree([1, 2, 2]))
3

partition_forest(t::RootedTree, edge_set)

Form the partition forest of the rooted tree t where edges marked with false in the edge_set are removed. The ith value in the Boolean iterable edge_set corresponds to the edge connecting node i+1 in the level sequence to its parent.

Arguments

• t::RootedTree: Rooted tree to partition.
• edge_set: Boolean iterable of length order(t) - 1; false removes the corresponding edge and true keeps it.

Returns

• Vector{<:RootedTree}: Connected trees in the partition forest, ordered from the deepest removed subtree to the remaining tree.

Throws

• AssertionError: If edge_set does not have one entry per non-root node.

See also partition_skeleton, PartitionIterator, and PartitionForestIterator.

Examples

julia> forest = partition_forest(rootedtree([1, 2, 2]), Bool[false, true]);

julia> length(forest)
2

References

Section 2.3 of

• Philippe Chartier, Ernst Hairer, Gilles Vilmart (2010) Algebraic Structures of B-series. Foundations of Computational Mathematics DOI: 10.1007/s10208-010-9065-1

partition_skeleton(t::AbstractRootedTree, edge_set)

Form the partition skeleton of the rooted tree t, i.e., the rooted tree obtained by contracting each tree of the partition forest to a single vertex and re-establishing the edges removed to obtain the partition forest.

Arguments

• t::AbstractRootedTree: Rooted tree to partition.
• edge_set: Boolean iterable of length order(t) - 1; the same convention as partition_forest is used.

Returns

• AbstractRootedTree: Canonical partition skeleton with the same concrete tree type as t.

Throws

• AssertionError: If edge_set does not have one entry per non-root node.

See also partition_forest and PartitionIterator.

Examples

julia> skeleton = partition_skeleton(rootedtree([1, 2, 2]), Bool[false, true]);

julia> order(skeleton)
2

References

Section 2.3 (and Section 6.1 for colored trees) of

• Philippe Chartier, Ernst Hairer, Gilles Vilmart (2010) Algebraic Structures of B-series. Foundations of Computational Mathematics DOI: 10.1007/s10208-010-9065-1

residual_order_condition(t::ColoredRootedTree, ark::AdditiveRungeKuttaMethod)

The residual of the order condition (Φ(t) - 1/γ(t)) / σ(t) with elementary_weight Φ(t), density γ(t), and symmetry σ(t) of the AdditiveRungeKuttaMethod ark for the colored rooted tree t.

Arguments

• t::ColoredRootedTree: Colored rooted tree whose order condition is evaluated.
• ark::AdditiveRungeKuttaMethod: Additive Runge-Kutta coefficients used for the evaluation.

Returns

• Number: Residual of the order condition for t.

References

• A. L. Araujo, A. Murua, and J. M. Sanz-Serna. "Symplectic Methods Based on Decompositions". SIAM Journal on Numerical Analysis 34.5 (1997): 1926–1947. DOI: 10.1137/S0036142995292128
• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008. Section 312

residual_order_condition(t::RootedTree, ros::RosenbrockMethod)

The residual of the order condition (Φ(t) - 1/γ(t)) / σ(t) with elementary_weight Φ(t), density γ(t), and symmetry σ(t) of the RosenbrockMethod ros for the rooted tree t.

Arguments

• t::RootedTree: Rooted tree whose order condition is evaluated.
• ros::RosenbrockMethod: Rosenbrock coefficients used for the evaluation.

Returns

• Number: Residual of the order condition for t.

Reference

• Ernst Hairer, Gerhard Wanner. Solving ordinary differential equations II: Stiff and differential-algebraic problems. Springer, 2010. Section IV.7

residual_order_condition(t::RootedTree, rk::RungeKuttaMethod)

The residual of the order condition (Φ(t) - 1/γ(t)) / σ(t) with elementary_weight Φ(t), density γ(t), and symmetry σ(t) of the RungeKuttaMethod rk with Butcher coefficients A, b, c for the rooted tree t.

Arguments

• t::RootedTree: Rooted tree whose order condition is evaluated.
• rk::RungeKuttaMethod: Runge-Kutta coefficients used for the evaluation.

Returns

• Number: Residual of the order condition for t.

Reference: Section 315 of

• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008.

root_color(t::ColoredRootedTree)

Return the color of the root of t.

Arguments

• t::ColoredRootedTree: Colored rooted tree to inspect.

Returns

• eltype(t.color_sequence): Color stored at the root node.

Examples

julia> root_color(rootedtree([1, 2], Bool[false, true]))
false

rootedtree!(level_sequence, color_sequence)

Construct a canonical ColoredRootedTree object from a level_sequence and a color_sequence which may be modified in this process. See also rootedtree.

Arguments

• level_sequence: A mutable integer vector satisfying the rooted-tree level-sequence rules. Its contents may be reordered in place.
• color_sequence: A mutable color vector with the same axes as level_sequence. Its contents may be reordered in place in tandem.

Returns

• ColoredRootedTree: Canonical colored tree backed by the input vectors.

References

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

rootedtree!(level_sequence)

Construct a canonical RootedTree object from a level_sequence which may be modified in this process. See also rootedtree.

Arguments

• level_sequence: A mutable integer vector satisfying the rooted-tree level-sequence rules. Its contents may be reordered in place.

Returns

• RootedTree: Canonical rooted tree backed by level_sequence.

References

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

rootedtree(level_sequence, color_sequence)

Construct a canonical ColoredRootedTree object from a level_sequence and a color_sequence, i.e., a vector of integers representing the levels of each node of the tree and a vector of associated colors (e.g., Bools or Integers).

Arguments

• level_sequence: An integer vector satisfying the rooted-tree level-sequence rules.
• color_sequence: A vector of node colors with axes equal to axes(level_sequence). The input vectors are not mutated.

Returns

• ColoredRootedTree: Canonical colored tree backed by copies of both input vectors.

Throws

• DimensionMismatch: If the input vectors have different axes.
• ArgumentError: If level_sequence is not a valid rooted-tree level sequence.

Examples

julia> rootedtree([1, 2], Bool[false, true]).color_sequence
2-element Vector{Bool}:
 0
 1

References

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

rootedtree(level_sequence)

Construct a canonical RootedTree object from a level_sequence, i.e., a vector of integers representing the levels of each node of the tree.

Arguments

• level_sequence: An integer vector satisfying the rooted-tree level-sequence rules. The input is not mutated.

Returns

• RootedTree: Canonical rooted tree backed by a copy of level_sequence.

Throws

• ArgumentError: If level_sequence is not a valid rooted-tree level sequence.

Examples

julia> rootedtree([1, 2, 3, 2]) |> butcher_representation
"[[τ]τ]"

References

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

RootedTrees.set_latexify_style(style::String)

Set the style of rooted trees when using latexify. Possible options are

• "butcher": print the butcher_representation of rooted trees
• "forest": use the LaTeX macro \rootedtree described in the docstring of latexify

This system is based on Preferences.jl.

RootedTrees.set_printing_style(style::String)

Set the printing style of rooted trees. Possible options are

• "butcher": print the butcher_representation of rooted trees
• "sequence": print the level sequence representation

This system is based on Preferences.jl.

subtrees(t::ColoredRootedTree)

Returns a vector of all subtrees of t.

subtrees(t::RootedTree)

Return an allocated vector containing all child subtrees of t.

Arguments

• t::RootedTree: Rooted tree to decompose.

Returns

• Vector{<:RootedTree}: One tree for each child subtree of t. The result is independent of t and can be retained safely.

See also SubtreeIterator.

Examples

julia> length(subtrees(rootedtree([1, 2, 2])))
2

σ(t::AbstractRootedTree)
symmetry(t::AbstractRootedTree)

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

Arguments

• t::AbstractRootedTree: Rooted tree to inspect. It is canonicalized if necessary without modifying the input.

Returns

• Integer: Symmetry factor of t.

Examples

julia> symmetry(rootedtree([1, 2, 2]))
2

Reference: Section 301 of

• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008.

unsafe_copyto!(t_dst::AbstractRootedTree, dst_offset,
               t_src::AbstractRootedTree, src_offset, N)

Copy N nodes from t_src starting at offset src_offset to t_dst starting at offset dst_offset. The types of the rooted trees must match. For example, you cannot copy a ColoredRootedTree to a RootedTree.

This is an unsafe operation since the rooted tree t_dst will not necessarily be in canonical representation afterwards, even if the corresponding flag of t_dst is set. Use with caution!

unsafe_deleteat!(t::AbstractRootedTree, i)

Delete the node i from the rooted tree t. This is an unsafe operation since the rooted tree will not necessarily be in canonical representation afterwards, even if the corresponding flag of t is set. Use with caution!

unsafe_resize!(t::AbstractRootedTree, n::Integer)

Resize the rooted tree t to n nodes. This is an unsafe operation since the rooted tree will not necessarily be in canonical representation afterwards, even if the corresponding flag of t is set. Use with caution!

α(t::AbstractRootedTree)

The number of monotonic labelings of t not equivalent under the symmetry group.

Arguments

• t::AbstractRootedTree: Rooted tree to label.

Returns

• Integer: Number of inequivalent monotonic labelings.

Examples

julia> α(rootedtree([1, 2, 2]))
1

Reference: Section 302 of

• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008.

β(t::AbstractRootedTree)

The total number of labelings of t not equivalent under the symmetry group.

Arguments

• t::AbstractRootedTree: Rooted tree to label.

Returns

• Integer: Number of inequivalent labelings.

Examples

julia> β(rootedtree([1, 2, 2]))
3

Reference: Section 302 of

• Butcher, John Charles. Numerical methods for ordinary differential equations. John Wiley & Sons, 2008.

γ(t::AbstractRootedTree)

Alias for density. Return the product of the orders of the subtrees rooted at every vertex of t.

Arguments

• t::AbstractRootedTree: Rooted tree to inspect.

Returns

• Integer: Density of t.

σ(t::AbstractRootedTree)

Alias for symmetry. Return the order of the automorphism group of the rooted tree t.

Arguments

• t::AbstractRootedTree: Rooted tree to inspect.

Returns

• Integer: Symmetry factor of t.