Python中的s-t切割算法

Question

我正在尋找Python中用於流動網絡（有向圖）的s-t切割算法的實現。

是否有Vertex Cut算法的版本？

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給切割的價值。