The FlowFinder Class

This class will need three public methods and three private methods. Because the class is static, these methods will all need to be static.

A public method to read the input file

This method should take as its only parameter the name of the input file, and it should return the FlowNetwork read from the file. This method should not display any MessageBoxes, but should instead throw exceptions for the calling method to handle. All of the explicit error checking, except for what is done in the DirectedGraph class, should be done in this method. When you detect an error in the input, throw an exception containing the message that you want displayed to the user. The type of the exception can be any type that you feel is appropriate (e.g., FormatException or ArgumentException); however, you should avoid throwing simply Exception or any sub-type of IOException, as your calling code will then have trouble determining what message is to be displayed to the user (i.e., whether to display the entire exception or just the message part). To determine whether a stringcannot be converted to an int, use the static method Int32.TryParse (Links to an external site.)Links to an external site., which returns a bool indicating whether the given string can be converted to an int, and if so, places the int value in the out parameter. You should not need any try-catch blocks in this method.

A private method to find an augmenting path

This method should take as its only parameter a FlowNetwork giving the residual graph. It should return a dictionary of path information, as in Lab Assignment 34, giving a shortest path from the source to the sink in the residual graph. It should do a breadth-first search (see Lab Assignment 34) to find the shortest path. Use the Queue class from System.Collections.Generic, not Ksu.Cis300.LinkedListLibrary. If there is no path, it should return null. Because edges with a capacity of 0 are to be treated as having been removed, the search should ignore these edges (i.e., it shouldn't enqueue them). Note that because the sink node will never be the same as the source node, you don't need to handle that case.

A private method to find the minimum capacity on an augmenting path

This method should take as its parameters a dictionary of path information and a FlowNetwork representing a residual graph. It should return the minimum capacity of any edge on the path (given in the dictionary) from the source to the sink. It should use the dictionary to retrace the path backwards from the sink to the source, and for each edge, use the residual graph to obtain that edge's capacity.

A private method to augment the flow

This method should take the following parameters:

a FlowNetwork representing a residual graph;

a FlowNetwork representing a flow;

a dictionary of path information; and

the amount of flow to be added.

It should return nothing. As in the above method, it should retrace the path backwards from the sink to the source. For each edge (u, v) along this path, it should:

Decrease the capacity of (u, v) in the residual graph by the amount of flow being added.

Increase the capacity of (v, u) in the residual graph by the amount of flow being added.

If there is positive flow on (v, u), decrease this flow by the minimum of this flow and the flow being added.

If the flow being added is greater than the amount that the flow on (v, u) was decreased in the above step, add the difference of these values to the flow on (u, v).

For example, suppose we are adding a flow of 5, and that (u, v) has a capacity of 8, (v, u) has a capacity of 1, and there is a flow of 2 on (v, u). Then we decrease the capacity of (u, v) to 3, increase the capacity of (v, u) to 6, decrease the flow on (v, u) to 0 (in effect, removing this edge), and increase the flow on (u, v) to 3 (adding this edge in the process).

Be careful in getting edge data, as not all of the edges are guaranteed to exist (the edges whose capacities are decreased will always exist in the residual graph).

A public method to find a maximum flow

This method should take as its parameters a FlowNetwork and an out int parameter through which the value of the maximum flow will be returned. It should return a FlowNetwork giving the maximum flow. It should implement the algorithm described under "Maximum Flow Algorithm" above, making appropriate use of the above methods. While the algorithm indicates that the flow should be initialized to contain the same edges as in the given FlowNetwork, it is easiest to construct a FlowNetwork with the same source and sink, and allow the other nodes to be added automatically as edges are added (if some nodes don't get added, they will have no incoming or outgoing edges in the flow, and hence would not appear in the output). It also will be easiest to set up the loop as an infinite loop, with a return from inside the loop whenever no augmenting path is found.

A public method to write the output file

This method should take the following parameters:

the name of the file to be written;

a FlowNetwork giving the flow; and

the value of the flow.

It should return nothing. It should first write the value of the maximum flow to the file, then iterate through all the edges in the flow graph, writing the source, destination, and data for each edge that has positive data. It does not need to do any exception handling.