Tools for Trees

class pybs.unordered_tree.unordered_trees.Trees[source]

Class to memoize trees and provide some useful functions.

One instance, called the_trees, is made as the module is loaded. There is no need to make more.

Main purpose is to be a dictionary of TreeOrder objects. The TreeOrder object for trees of order n is accessed as the_trees[n]. If the TreeOrder object does not exist, it will be made by the the_trees object and returned.

index(tree)[source]

Return a tree’s index in \(T\) or \(FT\).

The index starts at 1 and respects to the total ordering. If the tree object is a FreeTree, the index is only over the free trees.

non_superfluous_index(tree)[source]

Return the index of a non-superfluous FreeTree.

Similar to the above, except that only non-superfluous trees are given indexes.

class pybs.unordered_tree.unordered_trees.TreeOrder(order, tree_type)[source]

A TreeOrder object provides all the trees of a given order.

It keeps a set or list of the rooted trees, the free trees and the non-superluous free trees of a given order. The purpose is mainly memoization.

trees(sort=False)[source]

Return the rooted trees of the order.

The trees are generated only the first time they are asked for, and they are sorted only the first time they are needed sorted. This is thus a slightly intricate memoization function. The sort argument in the following two functions serve the same purpose.

free_trees(sort=False)[source]

Return the free trees of the order.

Similar to trees(). Note that the FreeTree objects are guaranteed to know the complete set of rooted trees they represent.

non_superfluous_trees(sort=False)[source]

Return the non-superfluous free trees of the order.

Similar to trees().

number_of_free_trees_up_to_order()[source]

Return the number of free trees up to, but not including the order.

Calculated by counting.

number_of_non_superfluous_trees_up_to_order()[source]

Return the number of non-superfluous free trees up to, but not including the order.

Calculated by counting.

index(tree)[source]

Return the index of a tree in the order.

The index starts at zero for the smallest tree of the order. If the tree is a FreeTree, the index only counts free trees.

non_superfluous_index(tree)[source]

Return the index of a non-superfluous free tree in the order.

Just as the index()-method.

tree_with_index(index)[source]

Reurn the UnorderedTree with index within the order.

The index starts at zero.

free_tree_with_index(index)[source]

Reurn the FreeTree with index within the order.

The index starts at zero.

non_superfluous_tree_with_index(index)[source]

Reurn the index-th non-superfuous free tree within the order.

The index starts at zero.

pybs.unordered_tree.unordered_trees.tree_generator()[source]

Return a generator for all the trees.

If sort is true, the trees are returned in sorted order; if not they are returned order by order but otherwise arbitrarily.

pybs.unordered_tree.unordered_trees._graft_leaf(tree)[source]

Return a set of all trees made by grafting a leaf node on tree

This is the function used to construct all trees of a given order. It is not the grafting product, since multiplicity is ignored.

pybs.unordered_tree.unordered_trees.partition_into_free_trees(list_of_trees)[source]

Return a set of all the free trees from list_of_trees.

pybs.unordered_tree.functions.number_of_trees_of_order(n)[source]

Returns the number of unordered rooted trees with exactly n vertices.

Uses a formula from Sloane’s OEIS sequence no. A000081.

pybs.unordered_tree.functions.number_of_trees_up_to_order(n)[source]

Number of _trees up to, not including order n.

Based on number_of_trees_of_order.

pybs.unordered_tree.functions.number_of_tree_pairs_of_total_order(n)[source]

Needed for conjugate symplectic check. Known as \(m_n\). Taken from Hairer et al. On Conjugate symplecticity of B-series integrators