python - python-igraph 可以用于最小切割吗？

Question

Python-igraph 可以用来做 min st cut 吗？

我想要削减指定源和汇节点的最小成本削减。

谢谢！

Answer 1

是的。

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 提供切割的值.

[所有功劳归功于@Tamás]