Skip to content

layout

etrack.processors.layout

processors/layout: LayoutProcessor — a topology placed on a grid: ranks by flow, lanes by neighbours, loops marked.

O(V + E) for the loops and ranks, O(V log V) for the lanes. A DFS from the entries finds the back edges — the arcs that close a cycle against the flow — and marks them loop; without them the graph is a DAG, and its topological generations are the ranks. Within a rank, nodes are ordered by the mean lane of the nodes that feed them (barycenter), then by id, so a layout is deterministic and arcs cross as little as one pass allows.

BackEdges

BackEdges()

Bases: DFSVisitor

Collects the arcs a depth-first walk meets pointing back at a node still open: the cycles' closing arcs.

LayoutProcessor

Places a topology; holds nothing between calls.

place

place(topology: Topology) -> Topology

The same nodes and arcs with rank, lane and loop set, and the grid's extent.