Currently Being Moderated
Hello.
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.