偿付

如果你有一个由彼此拥有债务的人组成的网络，偿付债务可能会导致许多交易。使用这个crate可以将交易量最小化。

工作原理

我们将网络表示为图。每个节点代表一个人，每个人需要支付/接收的金额由顶点权重表示。负权重表示对网络的净债务，而正权重表示网络对个人的债务。目标是找到表示现金流的定向加权边，使得对于每个人，其流入量减去其流出量等于其顶点权重（他们拥有/从网络中获得的金额）。此外，边的数量应尽可能少。

在 Crates 中的使用

生成图

图可以通过两种不同的方式生成。

通过加权有向边

在这种方法中，我们描述节点之间的边。每条边都有一个起始节点和一个结束节点，以及一个权重。每个顶点需要一个独特的名称。否则，两个顶点将被解释为相同的。我们展示了如何创建以下图。

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

从这个表示生成的图将转换为 通过顶点权重 的图。

从 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();

这里的节点被命名为 A，B，C，D。

从 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();

这里的节点被命名为 A，B，C，D。

通过顶点权重

对于这种方法，我们将直接告诉图节点及其权重。这里有几种选择。权重表示一个人需要支付/接收的金额。我们展示了如何创建以下节点及其权重。

从 Vec<i64>

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

这里的节点名称只是从 0 到 n 的数字。因此，0，1，2，3。

从 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();

这里的节点被命名为 A，B，C，D。

从 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();

这里的节点被命名为 A，B，C，D。

解决方法

可用的求解器

近似算法不一定返回最优解，但它们的解不比给定因子更差。它们在多项式时间内运行。

精确算法给出最优解，但它的运行时间不是多项式的。这可能导致在处理较大输入时运行时间过长。通常情况下，没有实例，近似算法不会返回最优答案。

使用库

解决实例并获取字符串形式的解决方案。

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);

解决实例并打印用于graphviz图形可视化的dot字符串。

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);

您也可以选择除SolvingMethods::StarExpand之外的求解方法。有关更多信息，请参阅解决方法。

作为CLI的使用

用法：payback [OPTIONS] <FILE> [OUTPUT] [METHOD] 有关[OPTIONS]的详细信息，请参阅payback的帮助。 [OUTPUT]指定结果应以何种格式返回到stdout。这里提供的是dot和transactions选项。使用dot提供可由graphviz解析的输出，可以立即将其转换为图形。使用transactions仅打印解决方案的边及其权重。 [METHOD]确定求解算法，如#Solving中所述。 <FILE>选项应给出图形。可以是文件或将其管道输入到stdin。格式是csv。可以指定节点及其权重，如From Vec<(String, i64)>中所述，或者指定边及其权重，如From HashMap<(String, String), i64>中所述。

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

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

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

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

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

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

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