Functions
tuple[str, str]	split_tree (Tree peano_tree, decomposition, str traversal="bfs_finest_first", bool enable_propagate_bottom_up=False, bool enable_optimize_hierarchy=False, bool require_all_children_for_hierarchy_optimization=True, list[bool]\|None periodic_BC=None, bool verbose=False)
	Split a tree using a staged load-balancing workflow.

bool	_is_along_periodic_boundary (int level, coordinates, periodic_BC)
	Does a cell touch a periodic boundary?

list[int]	_assign_leaves (Tree peano_tree, leaf_nodes, decomposition, periodic_BC=None)
	Assign leaves to subtrees in the order given.

tuple[bool, list[int]]	distribute_leaves_bottom_up (Tree peano_tree, decomposition, bool finest_level_first=False, list[bool]\|None periodic_BC=None)
	Stage I: BFS-style leaf redecomposition over Peano SFC order.

tuple[bool, list[int]]	distribute_leaves_top_down (Tree peano_tree, decomposition, list[bool]\|None periodic_BC=None)
	Stage I: DFS-style leaf redecomposition over the Peano SFC.

None	propagate_bottom_up (Tree peano_tree)
	Propagate information bottom-up.

None	_optimize_hierarchy (Tree peano_tree, bool require_all_children=True)
	Stage III of the staged load-balancing workflow.

None	generate_tree_yaml (Tree peano_tree, str output_yaml_file)
	Generate a YAML file describing the complete tree structure with spatial layout.

Tree	reset_tree_to_single_subtree (Tree peano_tree)
	Reset all tree nodes to belong to subtree 0, effectively erasing all splitting.

tuple[list[int], list[int], list[int], list[bool]]	extract_split_instructions (Tree peano_tree)
	Stage IV of the staged load-balancing workflow.

Function Documentation

◆ _assign_leaves()

list[int] SplitTrees._assign_leaves	(	Tree	peano_tree,
			leaf_nodes,
			decomposition,
			periodic_BC = `None`
	)

protected

Assign leaves to subtrees in the order given.

Leaves along periodic boundaries stay on subtree 0 and count towards its share, as Peano never hands over such cells. The remaining leaves are handed out in the order of leaf_nodes: Subtree 0 gets the first ones until its share is reached, then subtree 1, and so forth.

Args: peano_tree: Tree to update (modified in place). leaf_nodes: Leaves as (level, a, b) or (level, a, b, c) tuples. decomposition: Number of leaves per subtree. periodic_BC: One flag per axis, or None.

Returns: Number of leaves per subtree.

Definition at line 156 of file SplitTrees.py.

References _is_along_periodic_boundary().

Referenced by distribute_leaves_bottom_up(), and distribute_leaves_top_down().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ _is_along_periodic_boundary()

bool SplitTrees._is_along_periodic_boundary	(	int	level,
			coordinates,
			periodic_BC
	)

protected

Does a cell touch a periodic boundary?

Args: level: Level of the cell (0-based w.r.t. the API tree arrays). coordinates: Integer coordinates of the cell on this level. periodic_BC: One flag per axis, or None if there are no periodic boundaries.

Definition at line 137 of file SplitTrees.py.

Referenced by _assign_leaves().

Here is the caller graph for this function:

◆ _optimize_hierarchy()

None SplitTrees._optimize_hierarchy	(	Tree	peano_tree,
		bool	require_all_children = `True`
	)

protected

Stage III of the staged load-balancing workflow.

Minimise the total number of split operations whilst preserving load balance
established by Stage II. The algorithm lifts split decisions up the tree hierarchy
by promoting a parent on level L-1 to the dominant subtree among its children
on level L.

Hierarchy lifting is applicable when:
- All children of a parent exist (count equals 3^d, where d is the spatial
    dimensions count: d=2 -> 9 children, d=3 -> 27 children)
- Children are mixed across at least two subtrees
- A dominant child subtree M exists (largest child count)
- The dominant subtree differs from the current parent subtree and yields a
    reduction of lower-level split pressure

When these conditions are met, the parent is reassigned to the dominant subtree.
Remaining child subtrees stay on level L, but their source parent subtree is now
the updated one (which effectively moves part of splitting upwards).

The algorithm operates bottom-up from finest to coarsest level(s), iteratively lifting applicable promotions until no further reductions are possible.

Args: peano_tree: Tree to update (modified in place). Required precondition: Stage II (bottom-up propagation) must have been applied first to ensure non-leaf subtree consistency. require_all_children: If True (default), only promote parents whose full 3^d child set exists. If False, also allow promotions for mixed partial child sets.

Returns: None.

Notes:

This function is intended to run after _propagate_bottom_up().
Preserves node existence flags (weight).
Modifies only subtree assignments to reduce split operation count.
Multi-pass iteration allows cascading promotions up the tree.
The "all children in one subtree" case is already resolved by Stage II; Stage III primarily targets mixed-child parents.

Definition at line 581 of file SplitTrees.py.

Referenced by split_tree().

Here is the caller graph for this function:

◆ distribute_leaves_bottom_up()

tuple[bool, list[int]] SplitTrees.distribute_leaves_bottom_up	(	Tree	peano_tree,
			decomposition,
		bool	finest_level_first = `False`,
		list[bool] \| None	periodic_BC = `None`
	)

Stage I: BFS-style leaf redecomposition over Peano SFC order.

This strategy runs through the mesh level by level. It first assigns all leaves on the finest level to partitions, then the leaves on the next coarser level, and so forth. Within each level, cells are visited in Peano space-filling-curve order, so the redecomposition follows the same ordering as the SFC traversal used elsewhere in the load-balancing API.

The goal is to keep the finest-mesh cells contiguous while respecting the hierarchical tree structure. In practice, that makes the routine well suited for solvers that spend most of their work on the finest cells, such as limiter-based or multigrid-style workflows.

The lexicographic order that used to be documented here now lives in strategies/Lexicographic.py; this function intentionally uses Peano SFC order instead.

Leaf definition:

Any existing cell on the finest level, or
Any existing coarser-level cell with no children on the next level.

Args: peano_tree: Tree to update (modified in place). number_of_subtrees: Total number of subtrees to create. finest_level_first: If False (default), process levels from coarsest to finest (0..max_level-1). If True, process levels from finest to coarsest while keeping BFS order inside each level.

Returns: A tuple (has_leaves_to_split, moved_nodes_per_subtree):

has_leaves_to_split: False if no eligible leaves were found.
moved_nodes_per_subtree: Per-subtree counts of reassigned leaves.

Notes:

Only leaves in subtree 0 are redistributed.
Node existence flags (weight) are preserved.
This stage does not update non-leaf assignments.

Definition at line 205 of file SplitTrees.py.

References _assign_leaves().

Referenced by split_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ distribute_leaves_top_down()

tuple[bool, list[int]] SplitTrees.distribute_leaves_top_down	(	Tree	peano_tree,
			decomposition,
		list[bool] \| None	periodic_BC = `None`
	)

Stage I: DFS-style leaf redecomposition over the Peano SFC.

Collect leaf cells currently assigned to subtree 0 and redistribute them across number_of_subtrees subtrees as evenly as possible. The redecomposition logic is identical to distribute_leaves_bottom_up(), but leaf discovery order follows DFS instead of level-order scanning. Both component-root discovery and per-parent child traversal use Peano SFC order.

Args: peano_tree: Tree to update (modified in place). number_of_subtrees: Total number of subtrees to create.

Returns: A tuple (has_leaves_to_split, moved_nodes_per_subtree):

has_leaves_to_split: False if no eligible leaves were found.
moved_nodes_per_subtree: Per-subtree counts of reassigned leaves.

Both return values can be ignored if you want to.

Definition at line 308 of file SplitTrees.py.

References _assign_leaves().

Referenced by split_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ extract_split_instructions()

tuple[list[int], list[int], list[int], list[bool]] SplitTrees.extract_split_instructions ( Tree peano_tree )

Stage IV of the staged load-balancing workflow.

Derive the enumerated splits for Peano's hardcoded load balancer from a split tree.

The function scans the tree arrays and reconstructs a sequence of splits which replays the observed decomposition with toolbox::loadbalancing::strategies::Hardcoded. Entry k of each returned list describes the kth split. The C++ strategy decides itself when to issue the kth split, i.e. there is no notion of mesh sweeps here.

A split is emitted whenever, on some level, a cell with subtree_id > 0 exists whose parent exists and has a different subtree id (i.e. the subtree gets introduced across a parent–child edge). Level 0 has no parent; any cells with subtree_id > 0 on level 0 are treated as introduced from subtree 0.

BottomUp vs AggressiveTopDown extraction

The level at which a split is emitted depends on how many distinct introduction levels the subtree has:

AggressiveTopDown (single introduction level): a split is emitted at that one level.
BottomUp (multiple introduction levels): the subtree's forest of root cells does not all reside on the same level. In BottomUp mode, Peano propagates the split upward from the finest level automatically, so there must be no split instruction higher up the tree. A single split is therefore emitted at the finest introduction level (the deepest level at which any root cell of the subtree borders a parent of a different subtree). Coarser introduction levels are suppressed.

The splits are ordered from coarse to fine emission level and, within a level, by subtree id.

Mapping:

splittingTrees is the unique parent subtree id for all introduced cells on the emitted level, or 0 if ambiguous.
numberOfCells is the count of introduced cells on the emitted level.
subTrees are subtree ids (not MPI ranks); map them to destination ranks separately.
bottomUpFlags is a per-split boolean that is True when the corresponding subtree has multiple introduction levels (BottomUp) and False otherwise (AggressiveTopDown).

Args: peano_tree: Input tree with subtree assignments.

Returns: Tuple (splittingTrees, numberOfCells, subTrees, bottomUpFlags) suitable for building a Hardcoded configuration.

Note: This helper is intended for offline replay of an already-computed split pattern. It does not modify the tree.

Definition at line 915 of file SplitTrees.py.

◆ generate_tree_yaml()

None SplitTrees.generate_tree_yaml	(	Tree	peano_tree,
		str	output_yaml_file
	)

Generate a YAML file describing the complete tree structure with spatial layout.

YAML Structure

The output contains:

Tree Metadata: Name, dimensions, domain boundaries, leaf counts
Split Summary: Distribution statistics across subtrees
Level Data: Complete spatial arrays for each refinement level

Spatial Array Format

Each level contains a spatial representation:

2D: Row-indexed arrays with comma-separated (weight,subtree_id) tuples
3D: Plane-row indexed arrays with nested structure
Indexing: 0-based indexing for both rows and planes

Data Format Example

tree_structure:
  - level: 1
    size: 3
    data:
      0: "(1,0), (1,0), (1,1)"
      1: "(1,1), (1,1), (1,2)"
      2: "(1,2), (1,2), (1,2)"

Integration with Peano

The YAML format is designed for:

Direct import into Peano's hardcoded load balancer
Visualization tools and analysis scripts
Checkpoint/restart mechanisms for offline decomposition

Technical Details

Preserves exact spatial relationships from tree arrays
Maintains type consistency (all values converted to int)
Uses safe YAML dumping to prevent formatting issues

Args: peano_tree: Tree object to generate YAML from output_yaml_file: Path to the output YAML file

Returns: None

Raises: IOError: If file cannot be written due to permissions or disk space

Note: Large trees may generate substantial YAML files. Consider file system constraints when processing high-resolution adaptive meshes.

Definition at line 737 of file SplitTrees.py.

◆ propagate_bottom_up()

None SplitTrees.propagate_bottom_up ( Tree peano_tree )

Propagate information bottom-up.

This correponds to the second stage of the staged load-balancing workflow.

Propagate subtree assignments from leaves to internal nodes in a bottom-up pass. For each existing non-leaf node, if all existing children belong to the same subtree, assign the parent to that subtree.

Implementation

We work from finest to the coarsest level. On each level, we trigger an iterative process (while loop) for each colour (tree number) k that we find:

Check if all kids of one cell belong to the same tree

For a cell on level level, we run over all 3^d children (counter child_a and child_b). There is a set, and we add all the child tree numbers to this set. Once we have visited all children, we can check the set cardinality: If the set cardinality equals 1, all children are assigned to the same tree. We therefore can assign the parent to this tree number, too.

Make decision if to assign the parent

If all kids belong to the same tree, we can propagate this ownership one level up. However, we do this for a tree k if and only if the following tests pass:

There could be multiple nodes k within the tree that span all together a forest of small trees. Let max_k be the maximum level of these root nodes within the forest, and let min_k be the minimum level.

We assign an arbitrary node from another tree colour the colour k if and only if

max_k - min_k becomes smaller through the assignment, or;
max_k - min_k = 0 and we could group all root nodes of k into k/3^d coarser nodes.

Rationale

The reason is that we don't want to propagate too aggressively bottom-up. Eventually, our goal is to introduce a hierarchy over the trees. For this, it helps us if all the root nodes of tree k are on the same level. In this case, we can determine (likely) one parent ‘k’ and then tell ‘k’ to fork x times where x is the number of roots within the forest of k.

Therefore, we try to ensure that max_k - min_k becomes smaller and smaller. This implies that, in an adaptive mesh, we try to group all the fine mesh parts together first.

Eventually, all root nodes of the forest k will end up on the one and same level. It could now be that we could move all of them one level up. This is covered by the second case distinction.

Returns: None.

Notes:

Operates from finest internal level to root.
Preserves node existence flags (weight).
Parents with mixed-child subtree assignments remain unchanged.
Intended to run after Stage I (distribute_leaves_bottom_up() or distribute_leaves_top_down()).

Definition at line 458 of file SplitTrees.py.

◆ reset_tree_to_single_subtree()

Tree SplitTrees.reset_tree_to_single_subtree ( Tree peano_tree )

Reset all tree nodes to belong to subtree 0, effectively erasing all splitting.

Use Cases

Algorithm Testing: Reset to known state between experiments
Re-splitting: Clear previous decomposition before applying new strategy
Debugging: Return to simple single-subtree configuration

Implementation Details

Preserves all node weights (existence flags)
Only modifies subtree assignments (sets all to 0)
Updates tree metadata (subtree_count, split_pattern) consistently

Args: peano_tree: Tree object to reset

Returns: Modified Tree object with all nodes assigned to subtree 0

Note: This operation is irreversible - previous subtree assignments are lost. Consider generating YAML backup before reset if preservation is needed.

Definition at line 857 of file SplitTrees.py.

◆ split_tree()

tuple[str, str] SplitTrees.split_tree	(	Tree	peano_tree,
			decomposition,
		str	traversal = `"bfs_finest_first"`,
		bool	enable_propagate_bottom_up = `False`,
		bool	enable_optimize_hierarchy = `False`,
		bool	require_all_children_for_hierarchy_optimization = `True`,
		list[bool] \| None	periodic_BC = `None`,
		bool	verbose = `False`
	)

Split a tree using a staged load-balancing workflow.

Stages:

distribute_leaves_bottom_up() or distribute_leaves_top_down(): Redistribute leaf nodes across subtrees.
_propagate_bottom_up(): Propagate subtree ownership to internal nodes.
_optimize_hierarchy() (optional): Further reduce split complexity by promoting complete child sets up the hierarchy.
1. create_constructor_initialisation_string() (optional): Derive full hardcoded constructor configuration from the transformed tree.

Args: peano_tree: Tree to split (modified in place). number_of_subtrees: Total number of subtrees to create. traversal: Stage I traversal strategy. Supported values:

"bfs": level-order leaf collection
"bfs_finest_first": level-order leaf collection within each level, but levels processed from finest to coarsest
"dfs": depth-first leaf collection enable_propagate_bottom_up: If True, enable Stage II bottom-up subtree propagation after leaf redecomposition. enable_optimize_hierarchy: If True, enable Stage III hierarchical optimisation to minimise split operations through hierarchy lifting. periodic_BC: One flag per axis. Peano never hands over cells along a periodic boundary, so these cells stay on tree 0. If you pass the periodic boundary conditions of your experiment, Stage I keeps the leaves along periodic boundaries on tree 0, too, and counts them towards tree 0's share. None means no periodic boundaries. require_all_children_for_hierarchy_optimization: Stage III guard for parent promotion. If True (default), a parent is only considered if all 3^d children exist. If False, Stage III may also promote mixed parents with partial child sets. enable_extract_split_instructions: If True, run Stage IV and return the derived (hardcoded_config, hardcoded_mode). destination_ranks: Optional destination rank list for Stage IV. If not provided, it defaults to target subtree IDs. verbose: If True, Stage IV prints extracted hardcoded parameters.

Notes:

All stages after Stage I are optional.
The tree is modified in place by the enabled transformation stages.
If number_of_subtrees <= 1, no transformation stage runs.
Stage III requires Stage II to have been applied first for correctness.

Definition at line 12 of file SplitTrees.py.

References _optimize_hierarchy(), distribute_leaves_bottom_up(), and distribute_leaves_top_down().

Referenced by 35_offline-load-balancing.offline_decomposition(), 35_offline-load-balancing-split-modes.offline_decomposition(), 35_offline-load-balancing-plan-vs-run.offline_plan(), and 35_offline-load-balancing-quantised.owner_of_cells().

Here is the call graph for this function:

Here is the caller graph for this function:

Functions

Function Documentation

◆ _assign_leaves()

◆ _is_along_periodic_boundary()

◆ _optimize_hierarchy()

◆ distribute_leaves_bottom_up()

◆ distribute_leaves_top_down()

◆ extract_split_instructions()

◆ generate_tree_yaml()

YAML Structure

Spatial Array Format

Data Format Example

Integration with Peano

Technical Details

◆ propagate_bottom_up()

Implementation

Check if all kids of one cell belong to the same tree

Make decision if to assign the parent

Rationale

◆ reset_tree_to_single_subtree()

Use Cases

Implementation Details

◆ split_tree()