factoriax.analysis.graph_layout

Place the nodes of an acyclic graph on a layered grid.

Both functions take the same map, {node: inputs}, and give each node one number. Together those two numbers are a grid position.

• assign_tiers() gives each node a tier, which becomes the column. A node with no inputs sits at tier 0. Every other node sits one tier after its deepest input.

• order_within_tiers() gives each node a row inside its tier, which becomes the slot in that column. It runs a Sugiyama barycenter sweep, which reduces the number of edges that cross.

Neither function knows about recipes. The recipe diagram is the only caller today, but any layered drawing can use them.

A tier is a longest-path layer, and not a shortest-path one. An item reachable by a two-step chain and by a one-step chain sits at tier 2. With shortest paths it sits at tier 1, level with a node that feeds it, and that edge then has to run backwards.

factoriax.analysis.graph_layout.assign_tiers(adjacency: Mapping[str, Iterable[str]]) → dict[str, int]

Give every node a tier, by the longest path from a source.

Parameters:

adjacency – {node: inputs}. A node with no inputs of its own does not need a key of its own. The walk finds such a node in the input lists and gives it tier 0.

Returns:

{node: tier} for every node named anywhere in the map, whether as a key or only as an input. A source sits at tier 0. Every other node sits one tier after its deepest input. An empty map gives an empty result.

Return type:

dict

Raises:

ValueError – When the map holds a cycle. The message names one node on that cycle. A node that lists itself as an input counts as a cycle.

Notes

The walk recurses once for each step of a chain, so a chain longer than the Python recursion limit raises RecursionError and not ValueError.

factoriax.analysis.graph_layout.order_within_tiers(adjacency: Mapping[str, Iterable[str]], tiers: Mapping[str, int], iterations: int = 8) → dict[str, int]

Give every node a row inside its tier, to reduce crossings.

Each pass sorts the nodes of a tier by the mean row of their neighbors in the tier beside it. A node with no neighbor in that tier sorts to the end. The sweep runs forward and then backward, because a node has neighbors on both sides.

This is a heuristic. It has no optimal answer to reach, and more passes do not always give fewer crossings.

Parameters:

• adjacency – The same {node: inputs} map given to assign_tiers().

• tiers – {node: tier} from assign_tiers(). Every node in adjacency must have an entry.

• iterations – How many forward and backward pairs of passes to run. Eight is the usual default of the Sugiyama method.

Returns:

{node: row}. Rows start at 0 in each tier and count up with no gaps. Position code multiplies the row by a fixed step, so a gap leaves an empty band in the figure.

Return type:

dict

Notes

The result depends only on the arguments. Each pass starts from a sorted node list, and not from dictionary order. Two runs in different processes therefore give the same rows, and a committed figure does not change between rebuilds.