Ford-Fulkerson Algorithm


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 3 of 3

Thread: Ford-Fulkerson Algorithm

Hybrid View

  1. #1
    Join Date
    Mar 2009
    Posts
    24

    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.

  2. #2
    Join Date
    Nov 2009
    Posts
    1
    You really should stop posting code examples right from our hw...

  3. #3
    Join Date
    Nov 2009
    Posts
    1
    Yeah, you really should stop.

Similar Threads

  1. Help with Dijkstra's Algorithm
    By justinsbabe5000 in forum Java
    Replies: 0
    Last Post: 11-15-2009, 01:03 AM
  2. Replies: 0
    Last Post: 11-09-2009, 06:24 PM
  3. Next Algorithm To Learn
    By Peter_APIIT in forum C++
    Replies: 4
    Last Post: 10-10-2008, 11:19 PM
  4. How to add third party algorithm in sql server 2000
    By shipra pandey in forum Database
    Replies: 0
    Last Post: 02-18-2006, 01:40 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center