6

I've tried to solve a question about the maximum-flow problem. I have one source and two sinks. I need to find a maximum flow in this network. This part is general max-flow. However, both targets have to get same amount of flow in this special version of the max-flow problem.

Is there anyone who can help me what should I do to do that?

Niklas B.
  • 92,950
  • 18
  • 194
  • 224
TheGost
  • 147
  • 1
  • 3
  • 8
  • What is the reason of -1 ? – TheGost Jan 21 '14 at 20:40
  • Are you talking fluid analysis or computer network messages? – Thomas Matthews Jan 21 '14 at 20:49
  • I would start with something along the lines of the same way you'd do general max flow, except at each step, find two augmenting paths, one from the source to each target. Then add enough flow to both paths such that both targets still get the same amount of flow (this is complicated a bit by non-edge disjoint graphs). I'm not sure that doing this will actually result in the max possible for both targets. – gms7777 Jan 21 '14 at 21:07
  • 3
    How is the question "unclear"? It's very obvious what is asked, IMHO. Actually in interesting problem. – Niklas B. Jan 21 '14 at 23:38

1 Answers1

8

Let s be your source vertex and t1 and t2 the two sinks.

You can use the following algorithm:

  1. Use regular max-flow with two sinks, for example by connecting t1 and t2 to a super-sink via edges with infinite capacities. You now have the solution with maximum excess(t1) + excess(t2), but it might be imbalanced.

  2. If excess(t1) == excess(t2), you are done. Otherwise, w.l.o.g. let excess(t1) > excess(t2)

  3. Run another round of max-flow with source t1 and sink t2 in the residual network of step 1. Restrict the flow outgoing from t1 to c = floor((excess(t1) - excess(t2)) / 2), for example by introducing a super-source S connected to t1 via an edge with the given capacity c. Now, excess(t2) is the maximum flow you can send to both sinks.

  4. If you need to reconstruct the flow values for each edge, do another round of max-flow to transport the excess(t1) - excess(t2) leftover units of flow back to the source.

The complexity is that of your max-flow algorithm.

If you already know how to solve max-flow with lower-bound capacities, you can also binary search the solution, resulting in complexity O(log W * f) where W is the solution value and f is the max-flow complexity.

Niklas B.
  • 92,950
  • 18
  • 194
  • 224
  • I'm sorry its not clear how adding a super source to t1 will transfer the flow units to t2. As far as I understand t1 will still remain a sink and transfer of flow 'from' t1 to any other node will be impossible. Sorry again if I mis-understand. – Abhishek Bansal Jan 26 '14 at 14:22
  • @AbhishekBansal treat t1 as a normal node and t2 as sink and proceed to do max-flow from new source to t2 – Kudayar Pirimbaev Jan 26 '14 at 15:27
  • to author: can you explain more explicitly about step 4? – Kudayar Pirimbaev Jan 26 '14 at 15:28
  • @KudayarPirimbaev t1 has all its edges as incoming edges (since it is a sink). How can it be considered a normal node? – Abhishek Bansal Jan 26 '14 at 15:32
  • @AbhishekBansal i think it is assumed that graph is bidirectional, in your case, i guess, you need to reverse directions of all edges to t1 except the one from new source, try like that, i'm not sure – Kudayar Pirimbaev Jan 26 '14 at 15:38
  • @AbhishekBansal: "t1 has all its edges as incoming edges (since it is a sink). How can it be considered a normal node". Doesn't matter. You just add an additional incoming edge that has capacity `floor((excess(t1) - excess(t2)) / 2)` and add it to a newly introduced source `S`. You can also think about it as setting `supply(t1) = floor((excess(t1) - excess(t2)) / 2)` and `demand(t2) = ∞`. The super-source is just a way to solve that. – Niklas B. Jan 26 '14 at 19:03
  • @KudayarPirimbaev: Let's say in the initial max-flow, `t1` receives 6 units of flow and `t1` receives 2. We now try to transfer 2 unit of flow from `t1` to `t2` for balancing. Now it might happen that this doesn't work, we just achieve to send 1 unit of flow from `t1` to `t2`, so we end up with `excess(t1) = 5` and `excess(t2) = 3`. The solution here is that both nodes receive 3 units of flow (the minimum of the two), so we need to send 2 units of flow from `t1` back to the original source in the residual network (another max-flow problem). – Niklas B. Jan 26 '14 at 19:06
  • @KudayarPirimbaev: And no, the graph is not assumed to be bidirectional. The algorithm would still work though. – Niklas B. Jan 26 '14 at 19:10
  • @AbhishekBansal: Sorry, I think I now understand better where you had a problem understanding the algorithm: "As far as I understand t1 will still remain a sink and transfer of flow 'from' t1 to any other node will be impossible." We are working on the residual network after step 1, so if `excess(t1) != 0`, then it will in fact have some outgoing residual edges! – Niklas B. Jan 26 '14 at 19:15
  • @NiklasB. so to balance to 3 (in this example), we should apply max-flow where source is t1 and sink is s? – Kudayar Pirimbaev Jan 26 '14 at 19:15
  • @KudayarPirimbaev: Yep. In the residual network after step 3, that is. Of course we only need to do this if we want the complete flow function, since we already know the value of the solution is 3. – Niklas B. Jan 26 '14 at 19:15
  • @NiklasB. I tried your algorithm using Edmonds-Karp. It updates flows correctly in the first step, but then it fails to update properly when I do it for supersource and sink t2 as well as when applying it in step 4. I think I implemented the Edmonds-Karp algorithm correctly, what can be my mistake in your opinion? – Kudayar Pirimbaev Jan 26 '14 at 19:28
  • @Kudayar: Do you always use the residual network from the last step? – Niklas B. Jan 26 '14 at 19:28
  • @NiklasB. Yes, only Edmonds-Karp itself changes flow matrix – Kudayar Pirimbaev Jan 26 '14 at 19:30
  • @Kudayar: What do you mean by "fails to update properly"? I mean it should always respect the flow balance and flow conservation constraints. If it does and there exists a residual path from `t1` to `t2` in step 3, it should find it. It should never enter an inconsistent state. – Niklas B. Jan 26 '14 at 19:32
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/46119/discussion-between-niklas-b-and-kudayar-pirimbaev) – Niklas B. Jan 26 '14 at 19:37
  • @NiklasB. fixed it, was improperly using breadth-first, thanks for help – Kudayar Pirimbaev Jan 26 '14 at 20:03
  • @NiklasB. Thank you, I understand now. I had forgotten that we are working on the residual graph, not the original one. – Abhishek Bansal Jan 27 '14 at 04:32