Python中的s-t切割算法

Question

我在找一个用Python实现的s-t切割算法，适用于流网络（有向图）。

这个算法有没有顶点切割的版本呢？

Answer 1

igraph 有这个功能：

>>> from igraph import Graph
>>> from random import randint
>>> g = Graph.GRG(100, 0.2)        # generate a geometric random graph
>>> g.es["capacity"] = [randint(0, 1000) for i in xrange(g.ecount())]
>>> cut = g.maxflow(0, 99, "capacity")

cut.membership 会告诉你每个点的归属情况（0-1向量），cut[0] 会给你切割一边的点，cut[1] 则给你另一边的点，cut.value 会告诉你这个切割的值。