algorithme de coupe s-t en Python

Question

Je cherche une implémentation de l'algorithme de coupe s-t pour le réseau de flux (graphe orienté) en Python.

Existe-t-il une version vertex cut de l'algorithme?

Answer 1

igraph a elle:

>>> 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 vous donne la composition de chaque sommet (0-1 vecteur), cut[0] vous donne les sommets d'un côté de la coupe, cut[1] donne l'autre, donne cut.value la valeur de la coupe.