Max-flow: parallel and sequential, side by side

Push–relabel written as Extended Einsums — bulk-synchronous on the left, the textbook pseudocode written out on the right.

Both compute the same maximum flow on the same graph. The right-hand column is what you get writing the while loop out directly: pick one vertex, test it once, then push or relabel. The highlighting is computed by diffing the two specs, not marked by hand.

What sequentialising costs. A selector is added, four Einsums change, and — the part that is easy to miss — two are dropped. The parallel cascade recomputes Adm and Act after the push because bulk-synchronous execution has no read-after-write; a sequential cascade does not need them, and keeping them would let a vertex push and relabel in the same round. So the sequential cascade is shorter: 23 Einsums against 24.

Reading the right column. Its rows are aligned to the left so the expressions line up, which means its own labels run out of order — B11 and B12 appear down in the relabel section because that is where the parallel cascade asks the same question. That is the move, made visible: in the sequential cascade they run before the push, right after B10.