#Split Expenses using the Edmonds-Karp Algorithm

#Requirements

• Python: >= 3.10
• Poetry: >= 1.4
• Graphviz (Only needed for testing)

#Installation

# sudo apt-get install graphviz graphviz-dev
# sudo dnf install graphviz graphviz-devel
git clone https://git.sr.ht/~talfus-laddus/splt-exps-py
cd split-exps-py
poetry install

#Usage

poetry shell
pytest tests

#References

#General Informations

General Informations about Flow Networks, Maximum Flow Problem and Edmonds Karp Algorithm:

• https://en.wikipedia.org/wiki/Flow_network
• https://en.wikipedia.org/wiki/Maximum_flow_problem
• https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
• https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm

#Existing Implementations

Existing implementations of the Edmonds Karp Algorithm:

• Julia (JuliaGraphs)
• Python (networkx)
• Visualgo

#Articles

Articles describing how to use graph theory of flow networks to efficiently split group expenses:

• Settling Debts Efficiently: Zero-Sum Set Packing
• Solving the group expenses headache with graphs
• Algorithm Behind Splitwise’s Debt Simplification Feature