Maxflow的轻量级包装器

为Yuri Boykov和Vladimir Kolmogorov修改的Maxflow算法提供Python轻量级包装器。Vladimir Kolmogorov的原始源代码可在http://pub.ist.ac.at/~vnk/software.html找到。此包装器使用一个修改版本，支持更大的图和稍微低一点的内存使用。有关更多详细信息，请参阅子模块存储库。

Maxflow与QPBO的比较

Maxflow算法的一个更高级的替代方案是（二次伪布尔优化）QPBO，它也使用s-t图割。与Maxflow不同，它允许使用非亚模量能量项，Maxflow则不允许（除非以特定方式构建图，这就是QPBO所做的那样）。在许多其他方面，这使得QPBO能够解决具有排除项的优化问题，这非常有用。QPBO使用更多的内存，并且比Maxflow稍微慢一些。

安装

使用pip install thinmaxflow安装软件包或克隆此存储库（包括子模块）。构建软件包需要Cython。

图类型

目前有四种不同的图类型：GraphInt、GraphShort、GraphFloat和GraphDouble。它们之间的唯一区别在于图中边容量所使用的底层数据类型。为了保证稳定性，建议使用GraphInt进行整型容量，使用GraphDouble进行浮点型容量。然而，在某些情况下，使用GraphShort或GraphFloat可能更有利于减少内存消耗。

小型示例

import thinmaxflow as tf

# Create graph object.
graph = tf.GraphInt()

# Number of nodes to add.
nodes_to_add = 2

# Add two nodes.
first_node_id = graph.add_node(nodes_to_add)

# Add edges.
graph.add_tweights(0, 5, 0) # s     --5->   n(0)
graph.add_tweights(0, 0, 1) # n(0)  --1->   t
graph.add_tweights(1, 0, 3) # n(1)  --3->   t
graph.add_edge(0, 1, 2, 1)  # n(0)  --2->   n(1)
                            # n(1)  --1->   n(0)

# Find maxflow/cut graph.
flow = graph.maxflow()

for n in range(nodes_to_add):
    segment = graph.what_segment(n)
    print('Node %d belongs to segment %d.' % (n, segment))
# Node 0 belongs to segment 0.
# Node 1 belongs to segment 1.
    
print('Maximum flow: %s' % flow)
# Maximum flow: 3

许可协议

由于Maxflow实现是在GPLv3许可下发布的，因此此包也是。