Rewrite Bellman-Ford and min-cost flow, especially to stop the latter from crashing.
authorMatt McCutchen <matt@mattmccutchen.net>
Fri, 11 Jul 2008 03:46:07 +0000 (23:46 -0400)
committerMatt McCutchen <matt@mattmccutchen.net>
Fri, 11 Jul 2008 03:46:07 +0000 (23:46 -0400)
- 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.


No differences found