# Ford-Fulkerson Algorithm

• 11-21-2009, 04:36 PM
justinsbabe5000
Ford-Fulkerson Algorithm
I have a program that reads in a graph from a file and builds an adjacency list from it. The adjacency list consists of an ArrayList of FlowEdges. A flow edge is represented as source vertex, destination vertex, weight/capacity, and flow. The flow is initially 0. The adjacency list (network) is displayed, the adjacency list is reversed and displayed, the augmenting path from source to sink is diaplayed, and the modified network is diplayed. I have to write some methods but I'm not sure what each method is doing. Can someone please explain them to me and also explain the Ford-Fulkerson algorithm since I don't quite understand it.

Here are the methods I have to write:
Code:

```class FlowNetwork extends WeightedDigraph {     /**     * Finds an augmenting path from the source to the sink and returns     * it as a list (stack) of oriented edges. Returns null if there is no     * augmenting path.     * @param source     * @param sink     * @return     */     List<OrientedFlowEdge> getAugmentingPath(int source, int sink)     {                throw new UnsupportedOperationException("Write this method.");     }     /**     * This method is initially called with an augmenting path consisting     * of just one forward edge emanating from the start vertex. The method     * implements a backtracking dfs type search to extend the augmenting     * path all the way to the source. If no augmenting path can be found the     * method returns false with the stack of edges left in the same state     * as at the time of the call. If an augmenting path is found, it is     * stored in the stack of oriented flow edges augPath and the method     * returns true.     * @param augPath        * @param visited An array of boolean indicating which vertices have     * already been visited in an attempt to find an augmenting path.     * When the method backtracks, the visited vertices remain marked.     * @param sink     * @return true if an augmenting path is found, false otherwise.     */     boolean dfs(Stack<OrientedFlowEdge> augPath, boolean [] visited, int sink)     {            throw new UnsupportedOperationException("Write this method.");     }     /**     * returns the maximum additional flow that can be pushed through     * an augmenting path     * @param path     * @return     */     int getIncrementalFlow(List<OrientedFlowEdge> path)     {       throw new UnsupportedOperationException("Write this method.");        }     /**     * Modify the flow in the network along the augmenting path     * @param augPath     * @return the incremental flow used that  pushed through the path     */     int augmentFlow(List<OrientedFlowEdge> augPath)     {             throw new UnsupportedOperationException("Write this method.");     } }```
So in the getAugmentingPath method do I call the dfs method to find a path from source to sink and if the dfs method returns true I add that path to the stack in getAugmentingPath?

Not sure how to do getIncrementalFlow and augmentalFlow methods.

In main if the total flow is initialized to 0 how would I find the total flow?

Please help. I really need to get this done but I just don't know how to do this. I don't want someone to do this for me. Just explain this to me. Thanks.
• 11-22-2009, 01:43 PM
A321
You really should stop posting code examples right from our hw...
• 11-24-2009, 05:25 PM
bcat
Yeah, you really should stop. :WAVE: