Алгоритм S-T вырезать в Python

Question

Я ищу реализацию алгоритма s-t cut для потоковой сети (ориентированный граф) в Python.

Существует ли вершинная версия алгоритма?

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 дает значение среза.