up vote 1 down vote favorite

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.

My network:

See http://s1.directupload.net/file/d/3179/36dvrm3u_jpg.htm

Note:

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.

EDIT:

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

share|cite|improve this question
  • 2
    Voting to close as off-topic; this is not a research-level question. Your solution and the reference solution are both correct. – Jeffε Feb 28 '13 at 1:15
  • I see, but since my solution does not transport any units from vertex 1 (source of original problem) it is not correct is it? – Philipp Mar 1 '13 at 8:15
  • I removed my answer, I was making a mistake in definition of NH. There is nothing wrong with your solution. You only need a valid flow, that is, something where flow is conserved at each node. And this is happening in your solution. It doesn't matter that there is no net flow out of $q$. The 'correct' solution you wrote is just another valid flow from $q$ to $s$. The two need not be same. – polkjh Mar 2 '13 at 14:39
  • Allright, thx for the clarification. I just finished implementing described algorithm and it created a perfectly valid flow for a big input network (given by the programming assignment I have to do for a university project). I am glad I finally managed to solve the problem. Thank you very much again! You have been a great help. – Philipp Mar 2 '13 at 19:06

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.