uconf.core.trees

Rooted tree utilities for bar/cobar constructions.

Trees are represented using the RootedTree class:

• A leaf is a plain int in {1, …, n} (the arity).

• An internal vertex is a RootedTree instance holding a decoration (an operad/cooperad basis key, always a tuple) and an ordered sequence of children (each a leaf or another RootedTree). For connected operads, every vertex has at least 2 children.

RootedTree is immutable and hashable, making it suitable as a basis key in SageMath’s CombinatorialFreeModule and as an argument to @cached_method.

Structural properties that the old tuple encoding recomputed from scratch on every call — weight, leaves, min_leaf, tree_arity — are now eagerly cached at construction time and available in O(1).

Example (arity 3, weight 2):

RootedTree((1, 2), RootedTree((1,), 1, 2), 3)

represents a tree with root decorated by the Lie basis key (1, 2) (a binary bracket), whose first child is another internal vertex decorated by (1,) with leaves 1 and 2, and whose second child is leaf 3.

Functions

after_cobar_deg(tree, leaf_i, cooperad_cls, ...)	Total cobar degree of internal vertices after leaf_i in DFS order.
children(vertex)	Return the children of an internal vertex as a tuple.
contract_edge(tree, parent_vertex, ...)	Contract one internal edge, merging parent and child vertices.
copy_tree_structure(old_tree, new_decorations)	Create a tree with the same structure but new decorations.
decoration(vertex)	Return the decoration (operad basis key) of an internal vertex.
enumerate_planar_trees_generic_in_degree(...)	Enumerate DFS-canonical planar trees with an arbitrary per-vertex degree offset.
enumerate_planar_trees_in_degree(arity, ...)	Enumerate planar-decorated trees in B(P)(arity) of bar degree target_degree.
enumerate_shuffle_trees_cobar_in_degree(...)	Enumerate shuffle trees of arity leaves with cobar degree target_degree.
enumerate_shuffle_trees_free_in_degree(...)	Enumerate shuffle trees of arity leaves with free degree target_degree.
enumerate_shuffle_trees_generic_in_degree(...)	Enumerate shuffle trees with an arbitrary per-vertex degree offset.
enumerate_shuffle_trees_in_degree(arity, ...)	Enumerate all shuffle-tree basis elements of B(P)(arity) in bar degree target_degree.
expand_vertex(tree, target_vertex, ...)	Expand a vertex into two vertices connected by an edge.
graft(tree_top, i, tree_bot[, relabel_bot])	Graft tree_bot onto leaf i of tree_top.
internal_edges_dfs(tree)	Enumerate all internal edges (parent-child pairs between internal vertices).
is_internal(node)	Return True if node is an internal vertex.
is_leaf(node)	Return True if node is a leaf (an integer).
is_shuffle_tree(tree)	Check if a tree is in shuffle form.
leaves(tree)	Return the (frozen)set of all leaf labels in the tree.
min_leaf(tree)	Return the minimum leaf label in a tree or subtree.
relabel_leaves(tree, mapping)	Apply a leaf relabeling according to mapping.
replace_vertex_decoration(tree, target, ...)	Replace the decoration of a specific vertex in the tree.
split_at_vertex(tree, target_vertex)	Split the tree at a given internal vertex.
to_shuffle_tree_bar(tree, operad_cls, base_ring)	Normalize a tree to shuffle form for the bar construction B(P).
to_shuffle_tree_cobar(tree, cooperad_cls, ...)	Normalize a tree to shuffle form for the cobar construction Ω(C).
tree_arity(tree)	Return the arity of the tree (number of leaves).
tree_to_latex(tree, decoration_formatter)	Return a LaTeX representation of a decorated rooted tree.
tree_to_string(tree, decoration_formatter)	Return a human-readable string representation of a decorated tree.
validate_tree(tree, arity, operad_cls, base_ring)	Validate a tree for use in bar/cobar constructions.
vertex_arity(vertex)	Return the arity (number of children) of an internal vertex.
vertices_dfs(tree)	Return all internal vertices in depth-first (pre-order) traversal.
weight(tree)	Return the weight (number of internal vertices) of the tree.

Classes

RootedTree(decoration, *children)

Immutable rooted tree with eagerly cached structural properties.

class uconf.core.trees.RootedTree(decoration, *children)

Bases: object

Immutable rooted tree with eagerly cached structural properties.

Parameters

decorationtuple

Operad/cooperad basis key decorating this vertex.

*childrenint | RootedTree

Ordered children. Each child is either a leaf (int) or another RootedTree.

Cached attributes (O(1) access after construction):

• _decoration: the vertex decoration.

• _children: tuple of children.

• _arity: number of children (vertex arity).

• _weight: total number of internal vertices in this subtree.

• _leaves: frozenset of all leaf labels.

• _min_leaf: minimum leaf label.

• _tree_arity: total number of leaves.

RootedTree is immutable: all __slots__ are set once in __init__ and __setattr__ is overridden to prevent mutation.

to_tuple()

Convert back to the legacy nested-tuple representation.

Return type:

tuple

classmethod from_tuple(t)

Create a RootedTree from a nested-tuple representation.

Leaves (int) are returned as-is.

Parameters:

• decoration (tuple)

• children (int | RootedTree)

uconf.core.trees.is_leaf(node)

Return True if node is a leaf (an integer).

Return type:

bool

uconf.core.trees.is_internal(node)

Return True if node is an internal vertex.

Return type:

bool

uconf.core.trees.decoration(vertex)

Return the decoration (operad basis key) of an internal vertex.

Parameters:

vertex (RootedTree)

Return type:

tuple

uconf.core.trees.children(vertex)

Return the children of an internal vertex as a tuple.

Parameters:

vertex (RootedTree)

Return type:

tuple

uconf.core.trees.vertex_arity(vertex)

Return the arity (number of children) of an internal vertex.

Parameters:

vertex (RootedTree)

Return type:

int

uconf.core.trees.leaves(tree)

Return the (frozen)set of all leaf labels in the tree.

O(1) for RootedTree nodes (cached); O(n) for bare int leaves.

Return type:

frozenset[int]

uconf.core.trees.weight(tree)

Return the weight (number of internal vertices) of the tree.

O(1) for RootedTree nodes (cached).

Return type:

int

uconf.core.trees.tree_arity(tree)

Return the arity of the tree (number of leaves).

O(1) for RootedTree nodes (cached).

Return type:

int

uconf.core.trees.vertices_dfs(tree)

Return all internal vertices in depth-first (pre-order) traversal.

Each entry is the RootedTree object itself (identity-safe).

Return type:

list[RootedTree]

uconf.core.trees.after_cobar_deg(tree, leaf_i, cooperad_cls, base_ring)

Total cobar degree of internal vertices after leaf_i in DFS order.

In the DFS of a shuffle tree, the root vertex is visited first, then children are recursed left-to-right. A leaf is visited in place. after_cobar_deg returns the sum of (deg_C(v) - 1) for every internal vertex v whose DFS visit occurs after the visit of leaf_i.

For a corolla (single internal vertex) this is always 0, since the root is visited before any leaf.

Parameters:

leaf_i (int)

Return type:

int

uconf.core.trees.internal_edges_dfs(tree)

Enumerate all internal edges (parent-child pairs between internal vertices).

Returns a list of (parent_vertex, child_position, child_vertex) tuples where child_position is 1-indexed (the slot in the operad composition).

Return type:

list[tuple[RootedTree, int, RootedTree]]

uconf.core.trees.contract_edge(tree, parent_vertex, child_pos, new_decoration)

Contract one internal edge, merging parent and child vertices.

The child_pos-th child of parent_vertex is an internal vertex. Replace both with a single vertex having new_decoration and the combined children (children of parent before child_pos, children of child, children of parent after child_pos).

This function recursively finds and contracts the specified edge in the tree.

Parameters:

• tree (RootedTree)

• parent_vertex (RootedTree)

• child_pos (int)

• new_decoration (tuple)

Return type:

RootedTree

uconf.core.trees.graft(tree_top, i, tree_bot, relabel_bot=None)

Graft tree_bot onto leaf i of tree_top.

If relabel_bot is provided, it maps each leaf of tree_bot to its new label in the grafted tree. If not provided, leaves of tree_bot are relabeled to {i, i+1, ..., i+n_bot-1} and leaves > i in tree_top are shifted by n_bot - 1.

Returns the grafted tree.

Parameters:

• i (int)

• relabel_bot (dict | None)

uconf.core.trees.relabel_leaves(tree, mapping)

Apply a leaf relabeling according to mapping.

Parameters:

mapping (dict)

uconf.core.trees.split_at_vertex(tree, target_vertex)

Split the tree at a given internal vertex.

Returns (tree_top, position, tree_bot) where: - tree_bot is the subtree rooted at target_vertex - tree_top is the tree with target_vertex replaced by a single leaf - position is the position of that leaf in the grafting sense

Returns None if target_vertex is the root (can’t split at root).

Parameters:

• tree (RootedTree)

• target_vertex (RootedTree)

Return type:

tuple[RootedTree | int, int, RootedTree] | None

uconf.core.trees.validate_tree(tree, arity, operad_cls, base_ring)

Validate a tree for use in bar/cobar constructions.

Checks: - Leaves are exactly {1, …, arity} - All internal vertices have arity >= 2 (connected assumption) - All decorations are valid for the given operad/cooperad

Returns a validated tree with cleaned decorations, raises if invalid, or None if decorations are invalid but the tree structure is fine.

Parameters:

arity (int)

Return type:

RootedTree | Literal[1] | None

uconf.core.trees.enumerate_planar_trees_in_degree(arity, weight_bound, operad_cls, base_ring, target_degree)

Enumerate planar-decorated trees in B(P)(arity) of bar degree target_degree.

A tree is planar (in the quasi-planar cooperad sense) when:

1. All vertex decorations are planar elements of the base operad.

2. Children at each vertex have consecutive leaf-label ranges, so that planarize(T) = T ⊗ id (the global permutation is the identity).

Condition 2 means that the tree is a standard planar tree: leaf labels run 1, …, n strictly left-to-right, and each child subtree occupies a contiguous block. All such trees are automatically in shuffle form.

Uses the operad’s planar_basis_iter at the exact required degree for each vertex, so this is efficient even for operads with many basis elements per degree (e.g. Barratt–Eccles).

Requires the operad to implement planar_basis_iter.

The enumeration mirrors the binary-root topologies produced by enumerate_trees_by_weight, extended to planar decorations and restricted to consecutive child-leaf ranges.

Parameters:

• arity (int) – Number of leaves (arity of the bar-construction component).

• weight_bound (int) – Maximum number of internal vertices. For connected operads, callers should pass arity - 1 (the hard upper bound from the branching constraint sum(m_v - 1) = n - 1).

• operad_cls (Any) – Operad factory; must supply planar_basis_iter.

• base_ring (Any) – Coefficient ring.

• target_degree (int) – Exact bar degree to enumerate. May be any integer, including zero or negative, when the base operad has elements of negative degree (e.g. a shifted operad).

Return type:

Iterator[RootedTree]

uconf.core.trees.tree_to_string(tree, decoration_formatter)

Return a human-readable string representation of a decorated tree.

Parameters:

• tree – A rooted tree (RootedTree or leaf int).

• decoration_formatter (Callable[[tuple, int], str]) – Optional callback (decoration, arity) -> str. When provided, it is used to render each vertex decoration.

Return type:

str

uconf.core.trees.tree_to_latex(tree, decoration_formatter)

Return a LaTeX representation of a decorated rooted tree.

Parameters:

• tree – A rooted tree (RootedTree or leaf int).

• decoration_formatter (Callable[[tuple, int], str]) – Optional callback (decoration, arity) -> str. When provided, it is used to render each vertex decoration.

Return type:

str

uconf.core.trees.copy_tree_structure(old_tree, new_decorations)

Create a tree with the same structure but new decorations.

new_decorations should be in DFS order matching vertices_dfs(old_tree).

Parameters:

new_decorations (list[tuple])

Return type:

RootedTree

uconf.core.trees.replace_vertex_decoration(tree, target, new_decoration)

Replace the decoration of a specific vertex in the tree.

Parameters:

• tree (RootedTree)

• target (RootedTree)

• new_decoration (tuple)

uconf.core.trees.expand_vertex(tree, target_vertex, child_pos, left_decoration, right_decoration, left_arity, right_arity)

Expand a vertex into two vertices connected by an edge.

Used in the cobar differential d_2. The infinitesimal cocomposition Delta^{l; a, b}(c) splits an arity-k vertex (k = a + b - 1) into: - Top vertex with arity a, decoration c_L - Bottom vertex with arity b, decoration c_R - They connect at position l of the top vertex - Original children 1..l-1 go to top positions 1..l-1 - Original children l..l+b-1 go to bottom positions 1..b - Original children l+b..k go to top positions l+1..a

Parameters:

• tree (RootedTree)

• target_vertex (RootedTree)

• child_pos (int)

• left_decoration (tuple)

• right_decoration (tuple)

• left_arity (int)

• right_arity (int)

Return type:

RootedTree

uconf.core.trees.min_leaf(tree)

Return the minimum leaf label in a tree or subtree.

O(1) for RootedTree nodes (cached).

Return type:

int

uconf.core.trees.is_shuffle_tree(tree)

Check if a tree is in shuffle form.

A shuffle tree has, at each internal vertex, children ordered so that the minimum leaf label in each child subtree increases from left to right.

Example

RootedTree((), 1, 2) is shuffle (min({1})=1 < min({2})=2) RootedTree((), 2, 1) is NOT shuffle (min({2})=2 > min({1})=1)

Return type:

bool

uconf.core.trees.to_shuffle_tree_bar(tree, operad_cls, base_ring)

Normalize a tree to shuffle form for the bar construction B(P).

Returns a list of (shuffle_tree, coeff) pairs representing a (possibly multi-term) linear combination.

At each vertex, children are sorted by min leaf. The decoration is acted on by the sorting permutation (using the operad’s permute method), and Koszul signs are computed based on bar-degrees of subtrees.

When the operad’s permute produces multiple basis terms (e.g. for Lie-based operads), each term gives a separate output tree.

uconf.core.trees.enumerate_shuffle_trees_in_degree(arity, weight_bound, operad_cls, base_ring, target_degree)

Enumerate all shuffle-tree basis elements of B(P)(arity) in bar degree target_degree.

A shuffle tree is a rooted tree with leaves {1, ..., arity} in which children at every vertex are sorted by their minimum leaf label. Together with one decoration per vertex drawn from any basis of P(k), shuffle trees form a vector-space basis for the bar construction of any connected symmetric operad — not just quasi-planar ones.

Unlike enumerate_planar_trees_in_degree(), this function does not require the base operad to implement planarize or planar_basis_iter. It relies only on operad_cls(k, base_ring) having a basis_iter method (degree-aware or not) or Sage’s basis() family.

Parameters:

• arity (int) – Number of leaves (arity of the bar-construction component).

• weight_bound (int) – Maximum number of internal vertices. Pass arity - 1 for connected operads (the hard upper bound from sum(m_v - 1) = n - 1).

• operad_cls (Any) – Operad factory.

• base_ring (Any) – Coefficient ring.

• target_degree (int) – Exact bar degree to enumerate. May be any integer, including zero or negative, when the base operad has elements of negative degree (e.g. a shifted operad).

Yields:

Decorated shuffle trees as nested tuples valid as basis keys of BarConstruction(operad_cls)(arity).

Return type:

Iterator[tuple]

uconf.core.trees.enumerate_planar_trees_generic_in_degree(arity, weight_bound, operad_cls, base_ring, target_degree, vertex_offset, use_planar_decs=True)

Enumerate DFS-canonical planar trees with an arbitrary per-vertex degree offset.

A planar tree in the DFS-canonical sense has leaves 1, …, n in strict left-to-right order and every child subtree occupies a contiguous block of leaf labels. Together with planar vertex decorations (one per S_k-orbit), these trees form a basis for the planar part P_pl(n) of a quasi-planar symmetric sequence P.

Unlike enumerate_shuffle_trees_generic_in_degree(), which generates all shuffle trees (and thus over-counts orbits when the canonical form of P(n) under planarize is DFS-canonical rather than shuffle), this function yields exactly one representative per S_n-orbit, matching the output of P.Component.planarize(T) when sigma_global == id.

The three canonical choices for vertex_offset are:

• +1: bar degree Σ (deg_P(v) + 1).

• 0: free degree Σ deg_P(v) (no suspension).

• -1: cobar degree Σ (deg_C(v) − 1).

Parameters:

• arity (int) – Number of leaves.

• weight_bound (int) – Maximum number of internal vertices.

• operad_cls (Any) – Operad or cooperad factory for vertex decorations.

• base_ring (Any) – Coefficient ring.

• target_degree (int) – Exact total degree to enumerate.

• vertex_offset (int) – Per-vertex degree contribution.

• use_planar_decs (bool) – When True (default), restrict vertex decorations to the planar basis via planar_basis_iter.

Yields:

Decorated planar trees (nested tuples) as valid tree basis keys.

Return type:

Iterator[tuple]

uconf.core.trees.enumerate_shuffle_trees_free_in_degree(arity, weight_bound, operad_cls, base_ring, target_degree)

Enumerate shuffle trees of arity leaves with free degree target_degree.

The free degree of a decorated tree is Σ_v deg_P(dec(v)) — the sum of operad/cooperad element degrees over all internal vertices, without the per-vertex +1 offset used by the bar construction. This is the natural degree for the free P-algebra composite product P ∘ M and the cofree conilpotent C-coalgebra T^c_C(M).

Parameters:

• arity (int) – Number of leaves.

• weight_bound (int) – Maximum number of internal vertices (pass arity - 1 for connected operads).

• operad_cls (Any) – Operad or cooperad factory used for vertex decorations.

• base_ring (Any) – Coefficient ring.

• target_degree (int) – Exact free degree to enumerate.

Yields:

Decorated shuffle trees (nested tuples) as valid tree basis keys.

Return type:

Iterator[tuple]

uconf.core.trees.enumerate_shuffle_trees_cobar_in_degree(arity, weight_bound, cooperad_cls, base_ring, target_degree)

Enumerate shuffle trees of arity leaves with cobar degree target_degree.

The cobar degree of a decorated tree is Σ_v (deg_C(dec(v)) - 1) — the sum of desuspended cooperad element degrees over all internal vertices. This is the natural degree for the cobar construction Ω(C) and the cobar complex Ω_C(V).

Parameters:

• arity (int) – Number of leaves.

• weight_bound (int) – Maximum number of internal vertices (pass arity - 1 for connected cooperads).

• cooperad_cls (Any) – Cooperad factory used for vertex decorations.

• base_ring (Any) – Coefficient ring.

• target_degree (int) – Exact cobar degree to enumerate. May be negative when the cooperad has elements of low degree (e.g. CoAssociative in degree 0 contributes -1 per vertex).

Yields:

Decorated shuffle trees (nested tuples) as valid tree basis keys.

Return type:

Iterator[tuple]

uconf.core.trees.enumerate_shuffle_trees_generic_in_degree(arity, weight_bound, operad_cls, base_ring, target_degree, vertex_offset, use_planar_decs=False)

Enumerate shuffle trees with an arbitrary per-vertex degree offset.

The three canonical choices for vertex_offset are:

• +1: bar degree Σ (deg_P(v) + 1).

• 0: free degree Σ deg_P(v) (no suspension).

• -1: cobar degree Σ (deg_C(v) - 1).

Parameters:

• arity (int) – Number of leaves.

• weight_bound (int) – Maximum number of internal vertices.

• operad_cls (Any) – Operad or cooperad factory for vertex decorations.

• base_ring (Any) – Coefficient ring.

• target_degree (int) – Exact tree degree to enumerate.

• vertex_offset (int) – Per-vertex degree offset.

• use_planar_decs (bool) – When True, restrict vertex decorations to the planar basis (via planar_basis_iter) instead of the full basis. Use this for composite-product P ∘ M enumeration to obtain one representative per S_n-orbit.

Yields:

Decorated shuffle trees (nested tuples) as valid tree basis keys.

Return type:

Iterator[tuple]

uconf.core.trees.to_shuffle_tree_cobar(tree, cooperad_cls, base_ring)

Normalize a tree to shuffle form for the cobar construction Ω(C).

Returns a list of (shuffle_tree, coeff) pairs representing a (possibly multi-term) linear combination.

For the implemented cobar grading, subtree degrees are computed by subtree_degree_cobar (sum of deg_C(v) - 1 over internal vertices).