Network Flow - Simulating a network of water pipes

Question

I'm trying to devise an algorithm that will simulate a network of pipes with multiple sources and multiple sinks of specific capacity.

So far I have tried using the classic Ford-Fulkerson algorithm but the issue i run into is this, given the following graph:

    S
    |
    a
   / \
  B   C

Given S with a source capacity of 1, and both B and C with a sink capacity of 1 - a flow will result S - a - B, saturating B to 1 and leaving C with flow 0.

I'm trying to distribute flow uniformly across the network, so that both B and C receive 0.5. Any ideas?

Thanks!

Answer 1

Say you have n sources s₁, ..., s_n with source capacities c_i and m sinks t₁, ..., t_m. Let f = sum_i c_i. We want to find a feasible flow in the network where every source i has a net flow of -c_i and every sink has a net flow of f / m.

We can solve this by introducing a super source S and a super sink T and connecting each of the sources i to S via an edge (s_i, S) of capacity c_i. We connect each t_i to T via an edge of capacity f / m. Then we just run max-flow with source S and sink T.

If it is not possible to push exactly f / m units of flow to each sink, it is not clear what you want to optimize, but you might find the following two approaches useful:

• Choose e and connect the sinks to T via edges with capacities f / m + e. Use binary search to find the minimum e such that the total flow will be f. This minimizes max_i inflow(t_i)
• Choose e and add the sinks to T via edges with lower bound e. Use binary search to find the maximum e that still allows for a feasible flow. This maximizes min_i inflow(t_i). The feasible flow problem with lower bounds can be reduced to max-flow: http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/18-maxflowext.pdf In this case the construction is really simple: Just add an additional super-source S' and connect S' to S via an edge of capacity m * e. Connect all sinks to T via edges of capacity e. Check if the maximum flow between S' and T is m * e

Answer 2

I work as a water network engineer. When I model water supply networks, I usually put sources as pressure nodes and sinks as demand nodes, because water simulation software solves for either the head or the flow at nodes. And I know the capability of the pumps at the source and the consumption at the customers. Flow in pipes is resolved with headloss-flow equations such as Hazen-Williams or Darcy-Weisbach.

In your example the sinks demand more than what the source can provide, all in terms of flow. The customers at both B and C will try to open their faucets as large as possible, to fulfil their 1 unit of demand; but assuming that the pipe path from a to B is identical to from a to C, the 1 unit of flow will split evenly after both B and C tried their best to maximise flow to their respective ends.

But because the constraint of 2 units total demand is not met, the simulation software will not resolve. Either the source should be changed to pressure node, which will give the pressure required to send 2 units of water out, or the customer demands should be reduced to match source capabilities. In the latter case, the purpose is to model the hydraulic grade line from source to sink.