# 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.

#### A Sample Main to Test your Code

**
**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_

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_

Hints and Help: A Roadmap to an FHgraph-Compatible Implementation

While it might be possible to derive from **FHvertex** and **FHgraph** in order to solve the ** maximum flow problem**, we will spare ourselves the complication of syntax and write an

**FHflowGraph**class from scratch. You will be cannibalizing

**FHgraph**and

**FHvertex**in order to avoid duplication of effort. Therefore,

*of*

__make a copy__**FHgraph.java**and “morph” it into a new template called

**FHflowGraph.java**. (As usual, do this by making a new class that is peer with your other sources, not inside the

**cs_1c**package. So it will need an

**import cs_1c.*;**.) It is within this file that you can create your new flow graph machinery.

The discussion in the modules has explanation and diagrams that will be useful — probably necessary — to turn the following instructions into working code. Don’t try to use the steps below until you have read and understood the **FHgraph/dijkstra** material in ** Module 10**, and the maximum flow graph material in the one

**.**

*Module Section 11B.1*Morphing **FHvertex** to **FHflowVertex** is very easy. **adjList** is converted to two lists, **flowAdjList** and **resAdjList**. The remaining methods and data are trivially adjusted to account for this change. The terms *Unchanged*, *Removed* and *Added* below are with respect to the **FHvertex** template.

Data for FHflowVertex

·

Unchanged:

o

All static finals and sort key machinery

o

**data**, **dist**, and **nextInPath**

·

Removed:

o

**adjList**

·

Added:

o

**HashSets< Pair< … > flowAdjList**, **resAdjList**

Methods for FHflowVertex

·

Unchanged:

o

All sort key machinery

o

**equals()** and** hashCode()**

·

Removed:

o

**addToAdjList()**

o

**showAdjList()**

·

Trivially Modified or Added:

o

**addToFlowAdjList(), addToResAdjList()**

o

**showFlowAdjList(), showResAdjList()**

**FHedge** entirely removed.

**FHflowGraph** uses the same **vertexSet** that **FHgraph** used. The only additional data is a pair of **FHflowVertex<E>**objects, **startVert **and **endVert**, which represent the start and end of the flow problem. The terms *Unchanged*, *Removed* and *Added* below are with respect to the **FHgraph** template.

Data for FHflowGraph

·

Unchanged:

o

**vertexSet**

·

Added:

o

**FHflowVertex<E> startVert, endVert**

Methods for FHflowGraph

·

Unchanged (other than **FHflowVertex<E>** in place of **FHvertex<E>**):

o

**addToVertexSet()**

o

**clear()**

o

**getVertexWithThisData()**

·

Removed:

o

Constructor taking **Edges**

o

**showAdjTable()**

o

**setGraph()**

o

**getVertSet()**

·

Trivially Modified or Added:

o

**showFlowAdjTable(), showResAdjTable()**

o

**boolean setStartVert(E x)**, and **boolean setEndVert(E x)**

o

Default constructor

·

Removed:

o

**dijkstra()** – however, it is used as a basis for **establishNextFlowPath()**, discussed below, so don’t delete yet

o

**showShortestPath(), showDistancesTo()**

·

Modified

o

**addEdge()** – adds vertices as before, but adjacency lists are handled as follows:

§

**resAdjLists** will receive two edges based on this one call: a forward edge, exactly as before and a ** reverse edge** with cost

**0**

§

**flowAdjLists** are built as before but with all costs = 0

·

Added:

o

**double findMaxFlow()** – the main public algorithm. (All the remaining algorithms are helpers and can be private.) It returns the maximum flow found. The method loops, calling **establishNextFlowPath()** followed by **getLimitingFlowOnResPath()** and follows those calls by adjusting the residual and flow graphs using **adjustPathByCost()**. When **establishNextFlowPath()** returns **false** (or **adjustPathByCost()** returns **false** or the limiting flow becomes **0**, take your pick), the loop ends. Finally, the flow graph is probed to find the total flow for the functional return.

o

**boolean establishNextFlowPath()** – this is based on the **dijkstra()** method. It is less demanding than ** dijkstra**because any path that connects

**startVert**to

**endVert**will do. The simplest way to convert

**to this method is:**

*dijkstra*
§

Remove the functional parameter, since we will always start at **startVert**.

§

When traversing a newly popped **v**‘s adjacency lists, skip edges with **costVW == 0 **since they have been reduced to nothing (and are effectively no longer in the residual graph).

§

End the loop as soon as it finds a path to **endVert**. We don’t care about finding other flow paths since, in this version, it will be looking for “shorter” paths, something that is not necessarily good for us here.

§

It returns **true** if the **endVert **was successfully reached and **false**, otherwise.

§

(You could further modify ** dijkstra** in two more places to generate the

**path cost rather than a**

*maximum***, thinking that perhaps this will yield better flow results. This is not necessary, but if you do implement this, you must be very careful to avoid infinite loops by testing for (and rejecting) the inevitable**

*minimum***that will arise from the extra undo-paths. I don’t recommend this approach.)**

*cycles*This method will create the same **nextInPath** trail that ** dijkstra** did. That path is used in the subsequent methods to adjust vertex costs in each of the two graphs.

o

**double getLimitingFlowOnResPath()** – a helper for **findMaxFlow()** which follows on the coattails of **establishNextFlowPath()** and uses the data and path just created to find the limiting flow (minimum) of the residual path just found. The removed method **showShortestPath()** demonstrates how to trace the path from **endVert** to **startVert**, a maneuver that is useful here.

o

**boolean adjustPathByCost(double cost)** – a helper for **findMaxFlow()** which takes the result of **getLimitingFlowOnResPath()** and uses it to modify the costs of edges in both the ** residual graph** and the

**. Again, chasing the path from end to start will be the dominant action here. Because the path was based on an ad-hoc linked list using**

*flow graph***nextInPath**, from end to start, the two vertices in each loop pass (

**vert**and

**vert.nextInPath**) must be used to access the correct cost on the correct adjacency list. That’s the job of the next three methods:

o

**double getCostOfResEdge(FHflowVertex<E> src, FHflowVertex<E> dst)** – a helper to **getLimitingFlowOnResPath()**, this method examines **src’**s residual adjacency list to find **dst** and then return the **cost** of the edge **(src, dst)**.

o

**boolean addCostToResEdge(FHflowVertex<E> src, FHflowVertex<E> dst, double cost)** – a helper to **adjustPathByCost()**, this method examines **src’**s ** residual adjacency list** to find

**dst**and then add

**cost**to that edge (

**cost**can be negative if

**adjustPathByCost()**wants to subtract rather than add). It returns

**true**if there is no error in the arguments (null, e.g.)

o

**boolean addCostToFlowEdge(FHflowVertex<E> src, FHflowVertex<E> dst, double cost)** – a helper to **adjustPathByCost()**, this method examines **src’**s ** flow adjacency list** to find

**dst**and then adds

**cost**to that edge. If

**dst**is not found in

**src’s**list, that implies that the edge passed in was actually a reverse edge, in which case the flow edge we need to adjust is

**(dst, src)**. Further, this means we need to

__subtract__the flow because residual flow in the reverse direction is a signal that we are undoing some flow previously added. It returns

**true**if there is no error in the arguments (

**null**, e.g.)