Python中的s-t割算法

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