1
$\begingroup$

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

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Voting to close as off-topic; this is not a research-level question. Your solution and the reference solution are both correct. $\endgroup$ – Jeffε Feb 28 '13 at 1:15
  • $\begingroup$ I see, but since my solution does not transport any units from vertex 1 (source of original problem) it is not correct is it? $\endgroup$ – Philipp Mar 1 '13 at 8:15
  • $\begingroup$ 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. $\endgroup$ – polkjh Mar 2 '13 at 14:39
  • $\begingroup$ 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. $\endgroup$ – Philipp Mar 2 '13 at 19:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.