flow-network

Flow Network

网络流的工业级应用

使用 Dinic 和朴素费用流，算法来自 DuckKnowNothing - 网络流

支持平台

在尝试了各种方法之后，GitHub Actions 在 Windows 平台下始终无法正确编译 C++，所以放弃支持 Windows 平台

• Linux
• macOS

安装

pip install flow-network

样例代码

from flow_network import MaximumFlow, MinimumCostFlow

mf = MaximumFlow(2)  # 创建一个包含 2 个点的网络流对象，下标从 0 开始
mf.add_edge(0, 1, 3)  # 添加一条从 0 指向 1 的边，容量为 3
result = mf.run(0, 1)  # 指定源点为 0，汇点为 1，跑最大流 & 最小割
print(result)  # 3

for edge in mf.edges:  # 遍历每条边
    print(edge.u, edge.v, edge.flow, edge.capacity)  # 边的起点、终点、流过的流量、最大容量

mcf = MinimumCostFlow(2)  # 创建一个包含 2 个点的费用流对象，下标从 0 开始
mcf.add_edge(0, 1, 3, 2)  # 添加一条从 0 指向 1 的边，容量为 3，单位流量的费用为 2
flow, cost = mcf.run(0, 1)  # 指定源点为 0，汇点为 1，跑最大流 & 最小费
print(flow, cost)  # 3 6

for edge in mcf.edges:
    print(edge.u, edge.v, edge.flow, edge.capacity, edge.cost)  # 边的起点、终点、流过的流量、最大容量、单位流量的费用

测试代码

tests.py

Reference

• How to use C++ classes with ctypes?
• Calling C/C++ from Python?
• C Class Instance from Void Pointer using Ctypes
• Python 库打包分发、setup.py 编写、混合 C 扩展打包的简易指南（转载）
• Binary wheel can't be uploaded on pypi using twine
• Manylinux wheel builder