REMINDER: hw5 program (BWT.java) is due soon.  I delayed the duedate
to Friday evening, just because I was so tardy getting the "turnin"
working (see recent email).  I also created ../hw5/CharSort.java to
better illustrate key-indexed counting sort for char arrays.

Future: Friday, we'll say a bit about linear programming and
reductions, Monday will be review.  I'll also offer a review session
11am Wednesday (reading day) in W302.

Today we continue looking at the Ford-Fulkerson algorithm, this time a
Java implementation.

Slides, resuming around page 46:
   Java implementation:
     * each edge object keeps track of its capacity (part of the input)
       and its current flow value (ultimately part of the output)
     * since an edge is sometimes useful in the reverse direction,
       the edge object appears in both adjacency lists
     * the concept of the "residual network" (G_f : G with flow f),
       where we just need to look for a directed path
   [wonky labels on page 51]

Running the example code (the network is from page 54 of slides):

$ run FlowNetwork ../book/tinyFN.txt
+ java -cp .:/home/cs323000/share/book/jar/book.jar FlowNetwork tinyFN.txt
6 8
0:  0->2 0.0/3.0  0->1 0.0/2.0
1:  1->4 0.0/1.0  1->3 0.0/3.0
2:  2->4 0.0/1.0  2->3 0.0/1.0
3:  3->5 0.0/2.0
4:  4->5 0.0/3.0
5:

Application: maximum bipartite matching
    The integer maxflow gives us a matching, and the mincut shows us
    why we cannot improve this matching.

    Question: how long does FF take for this application?
    Answer:   at most V augmentations, so O(VE) time total.

We'll skip the "baseball" application.

If we have time, a few things from outside the slides:

  * Why does BFS (shortest path) finish in O(VE) augmenting steps?
    [Idea: distance labels never decrease, edge can reverse O(V) times.]

  * How to compute the "fattest path", instead of the shortest?
    [Idea: priority queue of unreached vertices, pick "fattest" next.]

A remark on the worst-case FF time bounds:

    max-flow is a problem where the performance that you see on
    "typical" problems is often *much* better than what is guaranteed
    by the worst-case analysis.  This is rather different from what
    you have seen for early problems (sorting, searching, heaps, uf,
    etc, where the worst-case analysis is close to practice).
    In FF the worst case is possible, but it does not usually occur.


HARDER ALGORITHMS (beyond scope of this course):
   There are somewhat better "preflow push" algorithms for maxflow.
   There are similar algorithms for "min-cost flow", and for "min cost
   perfect matching" in bipartite graphs.
   There are O(VE) algorithms for matchings in general graphs (*not*
   just bipartite), but they are more complicated to implement.