Maximum Flow Graph Algorithm Project – Excelsior Writers | excelsiorwriters.com
Programming
Excelsior Writers – Place your Order Now

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_

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, make a copy of 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 dijkstrabecause any path that connects startVert to endVert will do. The simplest way to convert dijkstra to this method is:

§
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 maximum path cost rather than a minimum, 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 cycles that will arise from the extra undo-paths. I don’t recommend this approach.)

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 flow graph. 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 nextInPath, from end to start, the two vertices in each loop pass (vertand 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.)


ORDER NOW