Backend Contract

This document defines the structural contract for tree backends that want to interoperate with yggdrax geometry and traversal APIs.

Capability Layers

Backends are expected to satisfy capabilities in layers, not as one monolithic type.

TreeStructureProtocol (core)

Required for all tree traversal logic:

  • parent

  • left_child

  • right_child

TreeRangesProtocol (geometry ranges)

Required for geometry from particle ranges:

  • node_ranges

  • num_particles

MortonLeafBoundsProtocol (optional geometry mode)

Required only when use_morton_geometry=True:

  • use_morton_geometry

  • bounds_min

  • bounds_max

  • leaf_codes

  • leaf_depths

TreeLevelIndexProtocol (optional, derivable)

Used by level-major and interaction grouping paths. If absent, yggdrax derives these from parent:

  • node_level

  • nodes_by_level

  • level_offsets

  • num_levels

Explicit octree metadata (optional, octree-oriented consumers)

Backends that want to support level-wise FMM kernels or octant-major scheduling may additionally expose:

  • oct_parent

  • oct_children

  • oct_child_counts

  • oct_child_mask

  • oct_valid_mask

  • oct_node_codes

  • oct_node_depths

  • oct_node_ranges

  • oct_nodes_by_level

  • oct_level_offsets

  • oct_num_levels

  • oct_leaf_mask

  • oct_leaf_nodes

  • radix_node_to_oct

  • radix_leaf_to_oct

These fields are not required by current yggdrax geometry/traversal APIs, but they are useful for downstream FMM implementations that prefer explicit octree cells over the binary radix traversal structure.

Topology Containers

Public wrappers accept either:

  1. A topology object directly, or

  2. A container exposing .topology.

Use resolve_tree_topology(...) if writing custom adapters.

Derivation Helpers

When level metadata is not precomputed, use:

  • get_node_levels(tree)

  • get_num_levels(tree)

  • get_level_offsets(tree)

  • get_nodes_by_level(tree)

  • get_num_internal_nodes(tree)

Precomputing and storing these fields is still recommended for performance.

For octree-aware consumers, precomputing oct_children and the octree level-index buffers is likewise recommended when repeated FMM passes will reuse the same tree.

Minimum Practical Backend

A backend that wants geometry + interactions should provide at least:

  • parent, left_child, right_child

  • node_ranges, num_particles

  • either:

    • Morton leaf fields (use_morton_geometry + leaf bounds metadata), or

    • set use_morton_geometry=False and provide valid particle range topology.

Level metadata can be omitted initially and added later as an optimization.

Validation

Run conformance checks:

pytest -q --no-cov tests/unit/test_backend_conformance.py

The suite is adapter-driven and currently runs against radix as the reference backend.