# Maximum Flow Graph Algorithm Project

#### A FLOW GRAPH ALGORITHM

You are to implement a maximum flow graph algorithm using a generic class, FHflowGraph. The input graph can be communicated to the FHflowGraph object by the client using any reasonable technique that takes underlying object data (Strings, Doubles, iTunesEntries, etc.); the method addEdge() used in the FHgraph template is recommended. Start and end vertices must be set using mutators setStartVert() and setEndVert(). There must be a findMaxFlow() public method to invoke the algorithm and return the maximum flow supported by the input graph. After that method is called, the client should be able to call I/O methods showFlowAdjTable() and showResAdjTable() to show both the flow graph and the residual graph that result from the recent call to findMaxFlow().

#### FINAL APPROACH

As we prepare to land from a very long flight, I recommend approaching this problem by spending a few days pondering your own data structure solution that meets this form factor. If it helps, forget the form factor and just focus on the algorithm to see how you would solve the problem without any constraints. Eventually, you’ll need to come back to the first paragraph and make your ideas work as described. If you do try your own design, you should plan on having a working product three full days before the assignment is due. This is just in case you can’t get the last couple pieces to fit, and need to abandon your original design and use the one I have prepared for you, below. It will take about three days to follow the specs below to lash up a working FHflowGraph.

This is not an easy design problem and you are not expected to devise a novel approach. The few days of preliminary thought will either yield a personal solution that works, or it will give you an appreciation for the ease with which we can turn the old FHgraph/dijkstra template into an FHflowGraph with just the right combination of ideas.

#### RUN AT LEAST TWO FLOW PROBLEMS. ONE SHOULD BE THE FLOW PROBLEM FROM THE MODULES OR TEXT IN ORDER TO EASILY CHECK THE ALGORITHM IS CORRECTLY CODED, AND A SECOND OF YOUR CHOICE. HERE IS A SAMPLE SOURCE AND OUTPUT FOR YOU TO USE AS YOU NEAR THE FINAL HOURS OF DEBUGGING: ```// --------------------------------------------------------------------_x000D_ // CIS 1C ASSIGNMENT #9_x000D_ // INSTRUCTOR SOLUTION CLIENT_x000D_ _x000D_ PUBLIC CLASS FOOTHILL_x000D_ {_x000D_ // ------- MAIN --------------_x000D_ PUBLIC STATIC VOID MAIN(STRING[] ARGS) THROWS EXCEPTION_x000D_ {_x000D_ DOUBLE FINALFLOW;_x000D_ _x000D_ // BUILD GRAPH_x000D_ FHFLOWGRAPH<STRING> MYG = NEW FHFLOWGRAPH<STRING>();_x000D_ _x000D_ MYG.ADDEDGE("S","A", 3); MYG.ADDEDGE("S","B", 2); _x000D_ MYG.ADDEDGE("A","B", 1); MYG.ADDEDGE("A","C", 3); _x000D_ MYG.ADDEDGE("A","D", 4); _x000D_ MYG.ADDEDGE("B","D", 2);_x000D_ MYG.ADDEDGE("C","T", 2); _x000D_ MYG.ADDEDGE("D","T", 3); _x000D_ _x000D_ // SHOW THE ORIGINAL FLOW GRAPH_x000D_ MYG.SHOWRESADJTABLE();_x000D_ MYG.SHOWFLOWADJTABLE();_x000D_ _x000D_ MYG.SETSTARTVERT("S");_x000D_ MYG.SETENDVERT("T");_x000D_ FINALFLOW = MYG.FINDMAXFLOW();_x000D_ _x000D_ SYSTEM.OUT.PRINTLN("FINAL FLOW: " + FINALFLOW);_x000D_ _x000D_ MYG.SHOWRESADJTABLE();_x000D_ MYG.SHOWFLOWADJTABLE();_x000D_ }_x000D_ }_x000D_ /* --------- OUTPUT -----------_x000D_ ------------------------ _x000D_ ADJ RES LIST FOR D: T(3.0) B(0.0) A(0.0) _x000D_ ADJ RES LIST FOR T: D(0.0) C(0.0) _x000D_ ADJ RES LIST FOR B: D(2.0) S(0.0) A(0.0) _x000D_ ADJ RES LIST FOR S: B(2.0) A(3.0) _x000D_ ADJ RES LIST FOR C: T(2.0) A(0.0) _x000D_ ADJ RES LIST FOR A: D(4.0) B(1.0) S(0.0) C(3.0) _x000D_ _x000D_ ------------------------ _x000D_ ADJ FLOW LIST FOR D: T(0.0) _x000D_ ADJ FLOW LIST FOR T: _x000D_ ADJ FLOW LIST FOR B: D(0.0) _x000D_ ADJ FLOW LIST FOR S: B(0.0) A(0.0) _x000D_ ADJ FLOW LIST FOR C: T(0.0) _x000D_ ADJ FLOW LIST FOR A: D(0.0) B(0.0) C(0.0) _x000D_ _x000D_ FINAL FLOW: 5.0_x000D_ ------------------------ _x000D_ ADJ RES LIST FOR D: T(0.0) B(2.0) A(1.0) _x000D_ ADJ RES LIST FOR T: D(3.0) C(2.0) _x000D_ ADJ RES LIST FOR B: D(0.0) S(2.0) A(0.0) _x000D_ ADJ RES LIST FOR S: B(0.0) A(0.0) _x000D_ ADJ RES LIST FOR C: T(0.0) A(2.0) _x000D_ ADJ RES LIST FOR A: D(3.0) B(1.0) S(3.0) C(1.0) _x000D_ _x000D_ ------------------------ _x000D_ ADJ FLOW LIST FOR D: T(3.0) _x000D_ ADJ FLOW LIST FOR T: _x000D_ ADJ FLOW LIST FOR B: D(2.0) _x000D_ ADJ FLOW LIST FOR S: B(2.0) A(3.0) _x000D_ ADJ FLOW LIST FOR C: T(2.0) _x000D_ ADJ FLOW LIST FOR A: D(1.0) B(0.0) C(2.0) _x000D_ ``` 