<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>By applying 1 and 2 I get the network shown in the second image (from top).</p>

<p>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 </p>

<p>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.</p>

<p>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?</p>

<p>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.</p>

<p>My network:</p>

<p>See <a href="http://s1.directupload.net/file/d/3179/36dvrm3u_jpg.htm" rel="nofollow">http://s1.directupload.net/file/d/3179/36dvrm3u_jpg.htm</a></p>

<p>Note:</p>

<p>q - source of original problem</p>

<p>s = sink of original problem</p>

<p>q0 - source of helper graph NH to use Ford-Fulkerson</p>

<p>s0 - sink of helper graph NH to use Ford-Fulkerson</p>

<p>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)</p>

<p>Thank you for any help!</p>

<p>P.S. I tried to translate the terminology from german, so please excuse me should I be using incorrect english terminology.</p>

<p>EDIT:</p>

<p>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</p>

CC BY-SA 3.0
2013-02-28T01:15:59.497Z
Voting to close as off-topic; this is not a research-level question.  Your solution and the reference solution are both correct.
Jeffε
CC BY-SA 3.0
2013-03-01T08:15:38.360Z
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
CC BY-SA 3.0
2013-03-02T14:39:02.943Z
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
CC BY-SA 3.0
2013-03-02T19:06:22.790Z
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
<graph-theory><graph-algorithms>
Using Max-Flow (Ford Fulkerson) to find satisfying flow
Philipp
# Using Max-Flow (Ford Fulkerson) to find satisfying flow

(Asked by: username_0 on 2013-02-27)

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

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Voting to close as off-topic; this is not a research-level question.  Your solution and the reference solution are both correct.  
> **username_0**: I see, but since my solution does not transport any units from vertex 1 (source of original problem) it is not correct is it?  
> **username_2**: 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.  
> **username_0**: 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.  

---

## 0 answers

