For quite some time now, I've been hacking away at this problem but never have managed to come up with an entirely satisfactory solution. It concerns network flow - where you have a graph of nodes which are imagined to have some kind of resource flowing between them, like water in pipes, or traffic on a road system, and so forth.

Such network flow problems seem to be usually given in terms of three types of nodes only: sources (i.e. resource is generated or at least emplaced into the network there), routers or junctions (splits or combines resource conservatively), and sinks (consumes, disposes, etc. of resource). And then we do something like ask how we can solve for the flows on the edges so as to try and figure out the best way to use what is available from the sources to meet the demand from the sinks, i.e. to compute the maximum flow.

But what I am interested in is how you deal with this when you add a fourth component into the mix: tanks, or parts which can "fill up" with resource to later discharge it. From the perspective of the network and depending on the amount of resource they contain, they can seemingly act like all three of the other components depending on their capacity and how they are hooked up - note that a tank can both have things feeding it and things drawing from it simultaneously, or have only feeders or only draws, so it can act in all three roles above. Moreover, depending on whether it contains content or empty space, it can likewise also change role - an empty tank cannot act as a source, obviously, nor can a full tank act as a sink, as it can't fit any more stuff into it.

For example, if the flow solver is given something like this:

then it should put a rate of 50 units/sec of flow on the left edge, 5 units/sec on the right edge, because the tank can absorb 45 units/sec.

But if the tank is hooked like this:

then the solver should put 45 units on the vertical edge as flowing out from the tank, and 5 units flowing from the source, to meet the total demand of 50 from the sink.

That is, in a graph involving a tank, the tank should "supplement" flow provided from sources to meet demand from sinks, or else should "absorb" excess flow that did not have corresponding demand. However, it must only do this while respecting what it can reach or what can reach it from the connections provided by the edges. Note here my drawings are perhaps oversimplified as they ignore the edge directions, but the intent is that the edge leading up from the tank in the second one is directed into the junction. Thus, the behavior in a different case where the source were to advertise 50 and the sink -5 should just be to route 5 U/s from the source to the sink, i.e. the usual max-flow, and the tank would not contribute any flow. If it had a bidirectional edge, then in this case it should absorb 45 U/s from the source, while in the original case behaving no different from the unidirectional case.

How can one create an algorithm to reliably generate such solutions, given only the graph and which nodes are tanks, junctions, sources, and sinks and what the supply from the sources and demand from the sinks are?

CodePudding user response：

Graph-theory algorithms are mostly (I don't know all) based on continuity. In your case you do not have continuity since flows are not balanced.

In order to consider your network as graph you need to define a node on each side of edge. In this case, you can define end node (node1) of produceEdge and begin node of consumeEdge as 2. Wasted or gained flow can be defined by adding node 4 and other nodes of edge produceEdge and consumeEdge can be defined as nodes 1 and 3, respectively.

In this case your algorithm will look like "Breadth First Search or BFS for a Graph". For more info you can refer to

CodePudding user response：

If you assume that your tanks have infinite capacity ( they can absorb an infinite quantity at the 'produce' rate AND be drawn down for an infinite quantity at the 'consume' rate, then you can solve the problem using normal graph flow algorithms.

If the tanks have finite capacity, i.e. they change their behavior when they run dry or become full, then the solution changes with time and times depend on the initial levels of the tank. If the tank capacities are large relative to the flow rates, the solutions will be steady state for significant periods. So you create multiple graphs, representing every possible combination of the three tanks states ( full, empty, or partial ) for each tank and solve each using graph theory. This will only be feasible if the number of tanks is modest.

If you have many tanks, and you are interested in the time behavior of your system. you will have to use a simulation approach.

There are many generic simulation packages available that can be configured to solve this problem. The challenge is to interpret the results, a task which requires good understanding of statistics.

You might also consider coding your own special purpose simulator. You do not mention your preferred coding language, but if you know C you can get a good start from https://github.com/JamesBremner/tankfill