Algorithm for total flow through weighted directed acyclic graph

56 views Asked by At

I am working on an algorithm and I want to know if the following problem has been studied and has a name:

Take a connected directed acyclic graph with weighted edges and one root node with no incoming edges. This root node is assigned an initial flow value of 1, which is distributed to each of its child nodes as the product of the edge weighting connecting the child node and the flow value of the parent (1 for the root). The flow value for each of those nodes are then distributed to their respective child nodes and so on until each node has a flow value, which represents the amount of flow that has passed through it.

This problem mirrors a physical system in which a headwater is split into different pipes at different ratios, where pipes can recombine again, and the goal is to calculate the how much of the fixed initial water amount flowed through each pipe (node). In this scenario, the pipes have unlimited capacity, and can handle any amount of water, so it is only the initial splitting ratio that determines how much comes from the parent pipe.

I have an algorithm to find the flow through each node, but I want to know if this problem exists and has a specific name, so that I can see if I have missed anything or am using incorrect terminology.

I have found the Wikipedia article for flow networks: https://en.wikipedia.org/wiki/Flow_network

However, this topic seems to be directed at problems in which the flow within each pipe is restricted, and the ratio of the source that goes to each of its child pipes is a variable to be optimized. For my problem, flow within a pipe is unconstrained, but the ratio between child pipes is predetermined and the goal is to know how much flow goes to each pipe.

Edit: This question is not limited to tree graphs and can be applied to any directed acyclic graph with a root node (rooted graph).

Edit #2: enter image description here

Above is an example graph where each edge label shows the ratio of the parent node amount going to each child node. From this, using a starting value of 1 for node A, we would have:

A = 1, B = 0.4A = 0.4, C = 0.4A + 0.5B = 0.6, D = 0.2A = 0.2, E = C + D = 0.8, F = 0.5*B = 0.2

0

There are 0 answers