EDGE Algorithms
Maximum Flow (Push-Relabel)
› interactive tensor walkthrough
Step through
one Einsum at a time, with every tensor
Compare
the same algorithm, written two ways
Graph
on each edge
F(u,v) / C(u,v)
— flow carried, out of capacity ·
on each node
d=
distance
D(u)
,
e=
excess
E(u)
active vertex (in
Act
)
source
sink
touched this step
stored 0
empty
positive
negative
true
Static tensors
— no rank I; never change
capacity
⇄ before / after
⊞ expand
Graph meaning
Einsum meaning
Generational tensors
— have rank I; carry state across iterations
Generational tensors
— have rank I; intermediates, rebuilt every iteration
reductions
⏮
◀
▶ play
▶
⏭
next iteration ⇥
speed
⏮
◀
▶ play
▶
⏭
✕
Operands read
— click any output cell to follow a different value
How this value is computed