1 Reply Latest reply on Feb 19, 2013 3:54 AM by marlin

    Problem in Ford-Fulkerson algorithm in directed graph


      I'm working with a directed graph of huge dimensions (tens of thousands of nodes and arcs).

      This directed graph links each pair of directly connected nodes by means of a pair of arcs (for example, if one has two nodes, let's say "s" and "t" directly connected, the graph has one arc coming from s in direction of t and one arc coming from t, to s).

      I've implemented a Ford-Fulkerson algorithm for this graph. The output of the code, for each combination of nodes “s” and “t”, are the following: the maximum flow; the arcs that are cut by the algorithm, the nodes that were separated in two disjoint sets after the minimum cut and the number of elements in each of the sets.

      However the outputs generated by this code are making me wonder if there is any error in this implementation: when running the algorithm with a given choice of source-node and destiny-node and then inverting this orientation (that is, the node there was the source now becomes the target-node and vice-versa) the minimum cuts (the arcs cut by the algorithm) are differents, although the value of the maximum flow is always the same.

      Are these results correct? It is possible that running the algorithm for a given combination of nodes s and t, and then running again the algorithm the choices (of source-nodes and target-nodes) inverted the maximum flow is always the same (although the minimum cuts are always different)?

      Thank you very much.
        • 1. Re: Problem in Ford-Fulkerson algorithm in directed graph
          I am certainly no expert on the Ford Fulkerson algorithm. I did look it up from your quesion and the short answer is that I would not be concerned that you are getting different cuts when running the algorithm with your source and sink reversed.

          The basic reason is that in the same way that there is no requirment that the optimal flow throug a network have a single unique path there is also no reason that you can't have multiple disconnecting cuts that all attain the same minimum.

          Consider a graph that is simply a straight line going from A to B to C to D. Suppose that the capacity AB is 2, BC is 10, and CD is aslo 2. Clearly the maximum flow from A to D is 2. The middle pipe is not at maximum capacity but AB and CD both are. Clearly AB by itself is a minimal cut that matches the maximum flow of 2. Equally clearly CD is a alternative cut that achieves the same minimum.

          I did not look at all at the method by which these proving cut are produced in the Ford Fulkerson algorithm, but presumably it is some local search that starts from the source and thus if you have swapped these in your different runs it is no particular surprise that you could produce different cuts that prove the same single maximal flow value.

          If you would like to test this theory that you are merly observing a situation where your graph just happens to support multiple identical cuts, you could perhaps do the following:

          Generate your two runs swapping source and sink, generate you two supporting cuts. These cuts are different so take an edge that is NOT common to both cuts and increment its capacity. This should NOT change the max flow (because the cut that you did not alter is still the valid supporting cut justifying the previous maximum flow) Run the algorithm again on this altered graph. You should be able to repeat this until the graph produces the identical cuts regardless of the directions you are going because you have systematically removed cuts that happened to have the same minimal value.

          I have no idea if this is an easy or a complicated hack in your code. I also don't know how many times you might have to run it in order to converge to a graph with a single cut. But iif it is easy to do it may give you more confidence that your code is working correctly OR of course, it might just expose some flaw.

          Hope that helps.