From: Matt McCutchen <matt@mattmccutchen.net>
Date: Fri, 11 Jul 2008 03:46:07 +0000 (-0400)
Subject: Rewrite Bellman-Ford and min-cost flow, especially to stop the latter from crashing.
X-Git-Url: https://mattmccutchen.net/match/match.git/commitdiff_plain/5a07db44406bad03321a90b0814cc4496c6b7d63?hp=5a07db44406bad03321a90b0814cc4496c6b7d63

Rewrite Bellman-Ford and min-cost flow, especially to stop the latter from crashing.

- 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.
---