Ford-Fulkerson in MATLAB

One page of code will be more than enough. After testing it, email your program (not output, just the program) to me in text-only format. This is a strictly optional assignment - you can earn 40 extra marks towards your total. If you decide to do it, please hand it in by Thursday 4/22.

Instructions

Implement the Ford-Fulkerson algorithm as outlined in the textbook and in the course (ie read the description and the example once more!).

Here is a test file with three networks.
Draw the digraphs described in the test file.
Do the Ford-Fulkerson algorithm by hand using the examples from the test file.
Start programming with this file.
Write a function augment(n,C,F,s,t,outlevel) that just finds an augmenting path for a given flow (or else signals STOP by returning a path that does not end with t).
In the second stage, write the function ff(n,C,s,t,outlevel). Start with the zero flow. As long as your function augment finds an augmenting path, calculate the improved flow FPRIME and use FPRIME as input to augment for finding an even better one. FPRIME has to be an n by n - matrix in the same format as F.
Finally, return a maximal feasible flow.

Conditions, Restrictions

If you type 'MATLAB Ford-Fulkerson' into Google, you get a number of implementations. Therefore we have to have some restrictions.

I insist that you write this in MATLAB, no Java, C++ or anything else.
Your functions have to start with the lines
function P=augment(n,C,F,s,t,outlevel)
function F=ff(n,C,s,t,outlevel)
taking six resp. five parameters with the following description.
- n - number of vertices in graph
- C - n times n - matrix of edge capacities. Assume that all edge capacities are positive, and non-existent edges are marked by zeros. For edge ij (from i to j) with capacity c, C(i,j) is c and C(j,i) is -c.
- F - n times n - matrix of flow along given edges ij, with the same conventions as C.
- s,t - position of source and sink
- P - augmenting path for given flow F as described in the textbook. P should be specified as a list of vertices, beginning with s and ending with t.
- outlevel - nonnegative integer. Display no intermediate results if outlevel is zero, more and more as outlevel increases (be sensible - do what you need for debugging your program). Leave these lines in there - the loss in speed is negligible compared to the ease of understanding your program.
Use the algorithm as described in the lecture and in the textbook. The output should be the n by n - matrix F describing a maximum feasible flow. That is, if C(i,j) is zero, then F(i,j) is zero. If C(i,j) is positive, then F(i,j) is the flow on the edge from i to j. To specify F completely, make F(j,i) = - F(i,j).
Add comments!

I will accept anything that meets the specifications on input format and performs the correct algorithm, ie I will test it on a few more examples. Don't be put off by the apparently bigger task of writing two functions - both are actually very short. You can put them into one file ff.m.

Look up the MATLAB help pages! And revise the description of the algorithm and the examples that we did in class. If nothing helps, ask/email me.