Functions
	test_tree3_stage1_bfs_finest_first_leaf_distribution ()
	Integration test for Stage I with traversal="bfs_finest_first".

	test_tree3_stage2_bottom_up_propagation ()
	Integration test for Stage I + Stage II with traversal="bfs_finest_first".

	test_tree3_stage3_no_root_promotion_with_single_root_first_row_embedding ()
	Integration test for Stage I + Stage II + Stage III (full pipeline).

	test_tree3_all_rows_stage1_leaf_distribution ()
	Stage I test for the all-rows representation variant.

	test_tree3_all_rows_stage2_bottom_up_propagation ()
	Stage II test for the all-rows representation variant.

	test_tree3_all_rows_stage3_promotes_level1_not_root ()
	Stage III test for the all-rows representation variant.

Function Documentation

◆ test_tree3_all_rows_stage1_leaf_distribution()

test_splittrees_tree3_fine_first_bfs.test_tree3_all_rows_stage1_leaf_distribution ( )

Stage I test for the all-rows representation variant.

In this all-rows recursive expansion variant, the represented tree is much denser than the first-row embedding. For 4 subtrees, Stage I deterministically distributes 585 leaves as [147, 146, 146, 146].

Definition at line 247 of file test_splittrees_tree3_fine_first_bfs.py.

◆ test_tree3_all_rows_stage2_bottom_up_propagation()

test_splittrees_tree3_fine_first_bfs.test_tree3_all_rows_stage2_bottom_up_propagation ( )

Stage II test for the all-rows representation variant.

Stage II keeps the root in subtree 0 and propagates ownership into non-leaf nodes according to uniform-child regions in this dense all-rows representation.

Deterministic outcome after Stage II:

Level 1 already contains propagated non-zero ownership in selected cells.
Level 2 column ownership sets follow a fixed mixed/uniform pattern.

Definition at line 286 of file test_splittrees_tree3_fine_first_bfs.py.

◆ test_tree3_all_rows_stage3_promotes_level1_not_root()

test_splittrees_tree3_fine_first_bfs.test_tree3_all_rows_stage3_promotes_level1_not_root ( )

Stage III test for the all-rows representation variant.

With all-row expansion, Stage III updates Level-1 ownership while keeping the root unchanged.

Deterministic Level-1 outcome after Stage III:

row 0: [0, 3, 2]
row 1: [0, 1, 3]
row 2: [0, 1, 3]

Root remains subtree 0.

Definition at line 358 of file test_splittrees_tree3_fine_first_bfs.py.

◆ test_tree3_stage1_bfs_finest_first_leaf_distribution()

test_splittrees_tree3_fine_first_bfs.test_tree3_stage1_bfs_finest_first_leaf_distribution ( )

Integration test for Stage I with traversal="bfs_finest_first".

Exercises the tree described by tree3_stage1_fine_first_bfs.dot:

23 leaves total (21 at the finest level + 2 childless level-1 leaves).
BFS finest-first processes level 2 leaves before level 1 leaves.
With 4 subtrees, the balanced distribution is [6, 6, 6, 5].

Expected leaf assignments after Stage I (first-row positions at each level): Level 3: (0,0)–(0,5) → subtree 0 [L3A1*, L3A2*] (0,9)–(0,14) → subtree 1 [L3B1*, L3B2*] (0,18)–(0,23)→ subtree 2 [L3C1*, L3C2*] (0,24)–(0,26)→ subtree 3 [L3C3*] Level 2: (0,2) → subtree 3 [L2A3, childless leaf] (0,5) → subtree 3 [L2B3, childless leaf] Non-leaf nodes (all levels) remain subtree 0.

Definition at line 13 of file test_splittrees_tree3_fine_first_bfs.py.

◆ test_tree3_stage2_bottom_up_propagation()

test_splittrees_tree3_fine_first_bfs.test_tree3_stage2_bottom_up_propagation ( )

Integration test for Stage I + Stage II with traversal="bfs_finest_first".

Exercises the tree described by tree3_stage2_fine_first_bfs.dot. After Stage II (bottom-up propagation), parents whose existing children all share the same subtree id are promoted to that subtree.

Changes introduced by Stage II on top of Stage I: Level 1: L2B1=(0,3): all children → subtree 1 → promoted from 0 to 1 L2B2=(0,4): all children → subtree 1 → promoted from 0 to 1 L2C1=(0,6): all children → subtree 2 → promoted from 0 to 2 L2C2=(0,7): all children → subtree 2 → promoted from 0 to 2 L2C3=(0,8): all children → subtree 3 → promoted from 0 to 3 L2A1=(0,0): all children → subtree 0 → stays 0 (no change) L2A2=(0,1): all children → subtree 0 → stays 0 (no change) L2A3=(0,2): no existing children → stays subtree 3 (Stage I result) L2B3=(0,5): no existing children → stays subtree 3 (Stage I result)

  Level 1:

L1A=(0,0): children {0,3} (L2A1=0, L2A2=0, L2A3=3) → mixed → stays 0 L1B=(0,1): children {1,3} (L2B1=1, L2B2=1, L2B3=3) → mixed → stays 0 L1C=(0,2): children {2,3} (L2C1=2, L2C2=2, L2C3=3) → mixed → stays 0

  Level 0:
      Root=(0,0): children {0} (L1A=0, L1B=0, L1C=0) at this stage → stays 0

Definition at line 96 of file test_splittrees_tree3_fine_first_bfs.py.

◆ test_tree3_stage3_no_root_promotion_with_single_root_first_row_embedding()

test_splittrees_tree3_fine_first_bfs.test_tree3_stage3_no_root_promotion_with_single_root_first_row_embedding ( )

Integration test for Stage I + Stage II + Stage III (full pipeline).

Exercises the tree described by tree3_stage3_fine_first_bfs.dot using a single-root Level 0 representation of the tree3 structure.

Even with a single root at Level 0, this first-row-only 2D embedding does
not satisfy Stage III's promotion precondition at the root:
the root has only 3 existing Level-1 children, while Stage III in 2D
requires all 3^2 = 9 children to exist.

Therefore Stage III should not change the root assignment.

Definition at line 186 of file test_splittrees_tree3_fine_first_bfs.py.