Payback

If you have a network of people, which own each other money, paying off debts can lead to many transactions. With this crate the amount of transactions can be minimized.

How it works

We represent the network as a graph. Each node represents one person and every person has an amount of money the need to pay/receive represented as a vertex weight. Negative weights indicate a net dept to the network while positive weights indicate a dept on the side of the network to the person. The aim is to find directed weighted edges, which indicate cash flow, such that for every person there inflow minus there outflow is equal to their vertex weight (how much money they own/get from the network). Also, the amount of edges should be minimal.

Usage in Crates

Generating Graphs

A graph can be generated in two different manners.

Via Weighted Directed Edges

In this method we describe the edges between the nodes. Each edge has a start and end node with a weight. Every vertex needs a unique name. Otherwise, the two vertices will be interpreted as the same. We show how to create the following graph.

graph TD;
A -- 1 --> C;
A -- 1 --> D;
B -- 1 --> D;

Loading

The graph from this representation will just be converted to a graph from Via Vertex Weights.

From Vec<((String, String), i64)>

let input: Vec<((String, String), i64)> = vec![
    (("A".to_string(), "C".to_string()), 1),
    (("A".to_string(), "D".to_string()), 1),
    (("B".to_string(), "D".to_string()), 1),
];
let graph: Graph = input.into();

Here the nodes are named A, B, C, D.

From HashMap<(String, String), i64>

let mut input: HashMap<(String, String), i64> = HashMap::new();
input.insert(("A".to_string(), "C".to_string()), 1);
input.insert(("A".to_string(), "D".to_string()), 1);
input.insert(("B".to_string(), "D".to_string()), 1);
let graph: Graph = input.into();

Here the nodes are named A, B, C, D.

Via Vertex Weights

For this method, we will tell the graph the nodes and there weight directly. Here are some options for this option. The weights represent how much a person has to pay/receive. We show how to create the following nodes and their weights.

Vertex	A	B	C	D
Weight	-2	-1	1	2

From Vec<i64>

let input: Vec<i64> = vec![-2, -1, 1, 2];
let graph: Graph = input.into();

Here the nodes names are just numbers from 0 to n. Therefore, 0, 1, 2, 3.

From Vec<(String, i64)>

let input: Vec<(String, i64)> = vec![
    ("A".to_string(), -2),
    ("B".to_string(), -1),
    ("C".to_string(), 1),
    ("D".to_string(), 2),
];
let graph: Graph = input.into();

Here the nodes are named A, B, C, D.

From HashMap<String, i64>

let mut input: HashMap<String, i64> = HashMap::new();
input.insert("A".to_string(), -2);
input.insert("B".to_string(), -1);
input.insert("C".to_string(), 1);
input.insert("D".to_string(), 2);
let graph: Graph = input.into();

Here the nodes are named A, B, C, D.

Solving

Available solver:

Solver	Type	SolvingMethods	Description
Star Expand	2 Approximation	StarExpand	Approximates optimal solution by choosing central node, to which all edges are incident.
Greedy Satisfaction	2 Approximation	GreedySatisfaction	Approximates optimal solution while minimizing the total weight of all edges.
Partitioning with Star Expand	Exact	PartitioningStarExpand	Partitioning based exact solver, which solves base cases with Star Expand.
Partitioning with Greedy Satisfaction	Exact	PartitioningGreedySatisfaction	Partitioning based exact solver, which solves base cases with Greedy Satisfaction.
BestPartition with Star Expand	Exact	BranchingPartitionStarExpand	Branching based exact solver with a runtime of O*(3^n), which solves base cases with Star Expand.
BestPartition with Greedy Satisfaction	Exact	BranchingPartitionGreedySatisfaction	Branching based exact solver with a runtime of O*(3^n), which solves base cases with Greedy Satisfaction.
Dynamic Program with Star Expand	Exact	DPStarExpand	Solver using dynamic programming technic with a runtime of O*(3^n), which solves bases cases with Start Expand
Dynamic Program with Star Expand	Exact	DPGreedySatisfaction	Solver using dynamic programming technic with a runtime of O*(3^n), which solves bases cases with Greedy Satisfaction

Approximation algorithm don't necessarily return the optimal solution but theirs is not worse than a given factor. Also, they run in polynomial time.

Exact algorithm give the optimal solution, but its runtime is not polynomial. This can lead to long runtimes while working with larger inputs. Generally it is uncommon to have an instance, for which an approximation algorithm does not return the optimal answer.

Using the Library

Solve the instance and get a solution as string.

use payback::graph::Graph;
use payback::probleminstance::{ProblemInstance, Solution, SolvingMethods};
                                                                                            
let instance: ProblemInstance = Graph::from(vec![-2, -1, 1, 2]).into();
let solution: Solution = instance.solve_with(SolvingMethods::StarExpand);
let result: Result<String, String> = instance.solution_string(&solution);

Solve the instance and print a dot string for graph visualization with graphviz.

use payback::graph::Graph;
use payback::probleminstance::{ProblemInstance, Solution, SolvingMethods};
                                                                                            
let instance: ProblemInstance = Graph::from(vec![-2, -1, 1, 2]).into();
let solution: Solution = instance.solve_with(SolvingMethods::StarExpand);
let result: Result<String, String> = instance.solution_to_dot_string(&solution);

You can also choose another solving method than SolvingMethods::StarExpand. See Solving for more options.

Usage as CLI

Usage: payback [OPTIONS] <FILE> [OUTPUT] [METHOD] For the [OPTIONS] see the help of payback. [OUTPUT] specifies in which format the result should be given back to the stdout. Here are the options dot and transactions available. With dot a graphviz parsable output is given, which can immediately be turned into a graph. With transactions the edges and their weights of the solution are just printed. [METHOD] determines the solving algorithm as in #Solving. The <FILE> options should give the graph. Either point to a file or pipe it into the stdin. The format is a csv. One can either specify the nodes with their weights as in From Vec<(String, i64)> or the edges with their weights as in From HashMap<(String, String), i64>.

If you want to input this graph

graph TD;
A -- 1 --> C;
A -- 1 --> D;
B -- 1 --> D;

Loading

either csv inputs the problem.

A,-2
B,-1
C,1
D,2

A,C,1
A,D,1
B,D,1

Examples

Use stdin with -. The defaults are [OUTPUT] = transactions and [METHOD] = approx-star-expand.

echo A,1\\nB,-1 | ./payback -
#  "A" to "B": 1.0

This is equivalent to

echo A,1\\nB,-1 | ./payback - transactions approx-star-expand

If you have graphviz installed you can create a PDF with the result.

echo A,C,1\\nA,D,1\\nB,D,1 > test.csv
./payback test.csv dot partitioning-greedy-satisfaction | dot -Tpdf > out.pdf

This is the resulting output in out.pdf.

graph TD;
A -- 2 --> D;
B -- 1 --> C;

Loading

Note

This problem is NP-Hard and therefore can have a long runtime for bigger instances.