This content has been marked as final.
Show 1 reply

1. Re: Problem in FordFulkerson algorithm in directed graph
marlin Feb 18, 2013 9:54 PM (in response to 990420)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.