simvx.core._topo_sort

Shared pure topological-sort helpers for render scheduling.

Two schedulers order work by dependency: the intra-scene RenderGraph (named passes over string resources, graphics package) and the inter-scene

class:

~simvx.core.scene_target_graph.SceneTargetGraph (scene render jobs over sampled render targets). Both call the single Kahn implementation here, per design/render_parallelism_and_multi_gpu.md P1-1 (extract the shared topo-sort helper, no fork).

Two entry points with deliberately different cycle policies:

• func:

  topo_sort raises :class:CycleError. An intra-scene pass cycle is always a bug (RenderGraph.compile).

• func:

  topo_sort_lagged never raises. An inter-scene cycle (two mirrors facing each other) is legitimate: Tarjan SCC finds each cyclic component and the minimal deterministic back-edge(s) are dropped to restore a DAG. Dropped edges are returned so the caller can treat them as async (lagged) edges sampling the previous frame’s target, scoped to the cyclic boundary.

Both sorts are deterministic: ties break by position in the input sequence (pass a name-sorted sequence for lexicographic tie-breaking).

Module Contents

Functions

topo_sort	Kahn topological sort of nodes; raises :class:CycleError on a cycle.
topo_sort_lagged	Kahn topological sort that degrades cycles to lagged edges, never raises.

Data

__all__

API

simvx.core._topo_sort.__all__

[‘CycleError’, ‘topo_sort’, ‘topo_sort_lagged’]

exception simvx.core._topo_sort.CycleError(remaining: collections.abc.Iterable)

Bases: ValueError

A dependency cycle was found where none is allowed.

remaining holds the nodes that could not be scheduled (every node participating in, or downstream of, a cycle).

Initialization

Initialize self. See help(type(self)) for accurate signature.

class __cause__

class __context__

__delattr__()

__dir__()

__eq__()

__format__()

__ge__()

__getattribute__()

__getstate__()

__gt__()

__hash__()

__le__()

__lt__()

__ne__()

__new__()

__reduce__()

__reduce_ex__()

__repr__()

__setattr__()

__setstate__()

__sizeof__()

__str__()

__subclasshook__()

class __suppress_context__

class __traceback__

add_note()

class args

with_traceback()

simvx.core._topo_sort.topo_sort(nodes: collections.abc.Sequence[simvx.core._topo_sort.topo_sort.K], deps: collections.abc.Mapping[simvx.core._topo_sort.topo_sort.K, collections.abc.Iterable[simvx.core._topo_sort.topo_sort.K]]) → list[simvx.core._topo_sort.topo_sort.K]

Kahn topological sort of nodes; raises :class:CycleError on a cycle.

Args: nodes: Every node, in tie-break order (position = priority). deps: node -> nodes that must come first. Entries not present in nodes are ignored (dangling dependencies are allowed, matching RenderGraph’s external-resource inputs). Self-dependencies are ignored.

Returns: The nodes in dependency order (producers first), ties broken by position in nodes.

simvx.core._topo_sort.topo_sort_lagged(nodes: collections.abc.Sequence[simvx.core._topo_sort.topo_sort_lagged.K], deps: collections.abc.Mapping[simvx.core._topo_sort.topo_sort_lagged.K, collections.abc.Iterable[simvx.core._topo_sort.topo_sort_lagged.K]]) → tuple[list[simvx.core._topo_sort.topo_sort_lagged.K], set[tuple[simvx.core._topo_sort.topo_sort_lagged.K, simvx.core._topo_sort.topo_sort_lagged.K]]]

Kahn topological sort that degrades cycles to lagged edges, never raises.

Same contract as :func:topo_sort, but on a cycle it runs Tarjan SCC, drops the minimal deterministic back-edge within each non-trivial SCC and retries until acyclic. Every node is always scheduled exactly once.

Returns: (ordered, dropped_edges) where dropped_edges is the set of (producer, consumer) pairs removed to break cycles: the consumer must read the producer’s previous output across that edge (a 1-frame lag under serial per-target execution). Empty on the acyclic case.