### 3 releases (breaking)

0.6.3 | Aug 25, 2024 |
---|---|

0.5.0 | Aug 14, 2024 |

0.4.2 | Sep 13, 2023 |

#**141** in Science

**49** downloads per month

**GPL-3.0-only**

64KB

1.5K
SLoC

# 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`;`

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

to `0`

. Therefore, `n`

, `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

. See Solving for more options.`SolvingMethods ::`StarExpand

# Usage as CLI

Usage:

For the `payback [OPTIONS] <FILE> [OUTPUT] [METHOD]`

`[``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`;`

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 `-`

and `[``OUTPUT``]` `=` transactions

.`[``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`;`

# Note

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

#### Dependencies

~10MB

~156K SLoC