CSC301.01 2015F, Class 30: Network Flows
========================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* All-pairs shortest path, continued.
* The Floyd-Warshall algorithm.
* The max-flow problem.
* Augmenting paths.
* The Ford-Fulkerson algorithm.
* Bipartite matching.

Preliminaries
-------------

### Admin

* Homework due Friday
    * Implement the naive version of the algorithm described in Section 6-2 and
      determine the average distance the arm travels on sets of 10,
      20, and 40 random inputs in where each coordinate is between 0 and
      99.
    * Implement the clever version of the algorithm described in Section 6-2.
    * Do problems 6-1, 6-5, 6-6, 6-12.
* Homework due next Wednesday (hopefully for real)
    * 6-20, 6-21, 6-23, 6-24, 6-25
* I got the example wrong.  See Monday's eboard for a successful
  use of a promotion to get additional value.

### Extra Credit

#### Academic

* Any other Long-String event (e.g., Friday night concert)
* Innovation Talk Wednesday.
* CS Extras Thursday: Mobile Sensing (UIowa).
* CS Table Tuesday: Something Positive

#### Peer

* SH concert 8:30 on Thursday
* 7 day film challenge 7:30 p.m. Friday in the Wall Theatre
* Orchestra concert 7:30 p.m. Saturday

### Questions

All-pairs shortest path, continued
----------------------------------

Make a matrix of all minimum-path lengths between two vertices.

Negative edge weights permitted, no negative cycles.

The Floyd-Warshall algorithm
----------------------------

Build a series of matrices.  Matrix k gives shortest paths involving
only intermediate nodes numbered 1 .. k.

How do we build matrix k+1 from matrix k?

      for (i = 1 to n)
        for (j = 1 to n)
          M(k+1)[i,j] = min(M(k)[i,k] + M(k)[k,j], M(k)[i,j])

What's the algorithm?

    for (k = 1 to n)
      for (i = 1 to n)
        for (j = 1 to n)
          M(k+1)[i,j] = min(M(k)[i,k] + M(k)[k,j], M(k)[i,j])

Why?

* Easy to implement - Likely to get right.
* Moderately fast O(n^3)
* Works with negative edge weights

The max-flow problem
--------------------

Treat the graph as a network.  Edges are capacities.

Give a source and a target, find the maximum "flow" from the source
to the target.

Augmenting paths
----------------

   Find a path from source to target. (augmenting path)
   Find the smallest size of an edge on that path
   For each edge on that path
     Decrement the edge in the original graph
     Increment the corresponding edge in the flow graph

INCORRECT!
The Ford-Fulkerson algorithm
----------------------------

Bipartite matching
------------------