# Directed graph of bank balances and transactions, how to process transactions?

I'm working on a game where there are several different entities represented by nodes. Each node has a starting balance, and directed edges show where money is owed from one account to another.

One problem I'm trying to figure out is which order to process transactions in, take this example below:

If you start by processing node 'B', because there is no balance, the \$30 is not transferred to node C. Node A only receives \$20 instead of \$50, bringing the balance to \$50. 'A' can't afford to pay both D and B, so depending on which is paid first the result is different. If D is paid first the balance goes up to \$80. The remaining \$20 goes to B. Then B also receives \$80. The final graph is: Is there an algorithm for solving situations like this? Is this related to network flow graphs or is that something different? I'm trying to figure out what problem class this is. • It's not clear what your question is. Is your question whether or not it is possible to pay all the debt? What happens when A owes 20 to B but only has 10? Does B receive 10, with A still owing 10? Oct 28, 2022 at 11:05 • Let$v_A$be the money A has, let$L^-_A$be all incoming links to$A$and$L^+_A$be all outgoing links from A. Then if you for each person X let$t_X = v_X + \sum L^-_X - \sum L^+_X$, then you have the surplus/deficit for each player. If all values are non-negative, then it is possible to pay off all debts. Oct 28, 2022 at 11:09 • What happens if you have a cycle$A {{1}\over{\rightarrow}} B {{1}\over{\rightarrow}} C {{1}\over{\rightarrow}} A$and everyone's balance is 0? Oct 28, 2022 at 11:18 • If you find a cycle with bottleneck value$b$(i.e. the smallest value of the cycle), can we then deduct$b$from all edges of that cycle, or do you demand that each player actually pays that money? Oct 28, 2022 at 11:20 • The above question also stands wrt transitivity, if$A {1 \over \rightarrow} B {1 \over \rightarrow} C$, can we shortcut it to$A {1 \over \rightarrow} C\$ instead? Oct 28, 2022 at 18:20

Pop off a player $$X$$. If $$X$$ can pay, pop off the first debt. Then update the recipient's balance, and the number of debts they can pay off (binary search), and update the PQ. Then you push $$X$$ back onto the PQ with its updated count.
All in all, this should take $$O(m \log m)$$ time where $$m$$ is the number of debts.