- Rewrite Bellman-Ford and min-cost flow solvers using the state-transformer
feature, adding infrastructure as necessary.
- Make Bellman-Ford detect the presence of a negative cycle.
- Min-cost flow now uses edges of arbitrary capacity, not just 1, although it's
the same naive algorithm that augments along the lowest-cost path no matter
how little flow that adds. Adjust the reduction accordingly; now it uses
fewer edges. Additional benefit: the change brings my min-cost flower's
interface closer to that of an eventual CS2 adaptor.
- Min-cost flow was crashing on larger instances because round-off error
prevented it from identifying the edge to be flipped by subtracting the costs
to its endpoints. To avoid this problem, redesign min-cost flow so edges are
identified by unique indices. Now doMatching "pulls" flow values for the
edgesD it generated instead of being "pushed" by edges in the residual graph.
- Make the Show implementation for Instances prettier.