i am trying to find a first allowed flow from vertex q to vertex s in a network N which has both minimum and maximum capacities.
1.) To solve the problem I started by creating a helper network NH by adding a new source and sink to the graph and subtracting max-capacities and min-capacities and setting min-capacities to zero on every edge.
2.) Additionally I added some new edges depending on the amount of flow into and out of a vertex (see below). This gives me a graph where I can apply the Max-Flow algorithm by Ford and Fulkerson. After doing so I get a satisfying flow through the network.
By applying 1 and 2 I get the network shown in the second image (from top).
3.) Now i applied the Ford/Fulkerson algorithm to find a max flow from q0 to s0 (the newly added source/sink) For this example I found only two paths to increase the network flow ( and each with a flow of 1. NOTE: I used the method for Ford-Fulkerson using increment-networks
4.) By adding the min-capacities of the original network to the flow for each edge, I should now find a first flow through the original network.
However I do not come up with the (correct) solution provided at the bottom of the image (with different flow values for some edges). Applying Ford-Fulkerson simply does not generate a flow for those edges. Or am I missing something?
I think my problem is that I am not using the Infinity path created in NH (e.g. to move 3 units to q), however I do not see how I should come to use this path.
q - source of original problem
s = sink of original problem
q0 - source of helper graph NH to use Ford-Fulkerson
s0 - sink of helper graph NH to use Ford-Fulkerson
in the image on the top, the pairs mean min-capacity and max-capacity (e.g. 0|3 means min-cap 0 and max-cap 3) In the second image the numbers mean max-caps (Min-caps are all 0 so I ignored them). In the third and fourth image the numbers represent the resulting flow (which lies between min - and maxcap)
Thank you for any help!
P.S. I tried to translate the terminology from german, so please excuse me should I be using incorrect english terminology.
I see that my solution is correct by using the ford fulkerson algorithm, however I don´t get a correct flow since the source q is not sending out any transport units in my solution. Should I just add the 3 necessary transport units from q to 3 to get a correct flow through the network? Please help