Dsxir.
Copy Markdown
Kahn's algorithm for sorting %Dsxir.RuntimeProgram.Node{} values into a
valid execution order.
Only {:node, _, _} -> {:node, _, _} edges contribute to the dependency
graph; program_input, program_output, and const endpoints are not
inter-node dependencies. Returns {:ok, [name]} on success or
{:error, {:cycle, [name]}} listing the remaining nodes when a cycle is
detected. The validator already proves runtime programs are acyclic, so the
error path is for robustness only.
Summary
Functions
Sort nodes topologically using edges. Only node-to-node edges
contribute to dependencies.
Functions
@spec sort([Dsxir.RuntimeProgram.Node.t()], [Dsxir.RuntimeProgram.Edge.t()]) :: {:ok, [atom()]} | {:error, {:cycle, [atom()]}}
Sort nodes topologically using edges. Only node-to-node edges
contribute to dependencies.
Linear-time Kahn implementation: builds an in-degree counter map and a
forward-adjacency map, then drains nodes whose in-degree is zero one at a
time, decrementing the in-degree of their children. Determinism is
preserved by seeding the work queue from the input nodes order and
appending newly-ready children in the order their parents are processed.