SplitwiseApp
Minimize Cash Flow Algorithm
This project aims to ease several transactions into minimal transactions to make transactions more accessible and efficient. The underlying data structure used for the implementation of the project is heaps that can be visualized through a directed graph.
Detailed Algorithm: Do following for every person Pi where i is from 0 to n-1.
- Compute the net amount for every person. The net amount for person ‘i’ can be computed be subtracting sum of all debts from sum of all credits.
- Find the two persons that are maximum creditor and maximum debtor. Let the maximum amount to be credited maximum creditor be maxCredit and maximum amount to be debited from maximum debtor be maxDebit. Let the maximum debtor be Pd and maximum creditor be Pc.
- Find the minimum of maxDebit and maxCredit. Let minimum of two be x. Debit ‘x’ from Pd and credit this amount to Pc
- If x is equal to maxCredit, then remove Pc from set of persons and recur for remaining (n-1) persons.
- If x is equal to maxDebit, then remove Pd from set of persons and recur for remaining (n-1) persons.