python - min st カットに 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 に送られます]