graph_tool.flow

This module includes maximum flow / minimum cut algorithms.

Summary

edmonds_karp_max_flow	Calculate maximum flow on the graph with the Edmonds-Karp algorithm.
push_relabel_max_flow	Calculate maximum flow on the graph with the push-relabel algorithm.
boykov_kolmogorov_max_flow	Calculate maximum flow on the graph with the Boykov-Kolmogorov algorithm.
min_st_cut	Get the minimum source-target cut, given the residual capacity of the edges.
min_cut	Get the minimum cut of an undirected graph, given the weight of the edges.

Example network

The following network will be used as an example throughout the documentation.

from numpy.random import seed, random
from scipy.linalg import norm
gt.seed_rng(42)
seed(42)
points = random((400, 2))
points[0] = [0, 0]
points[1] = [1, 1]
g, pos = gt.triangulation(points, type="delaunay")
g.set_directed(True)
edges = list(g.edges())
# reciprocate edges
for e in edges:
   g.add_edge(e.target(), e.source())
# The capacity will be defined as the inverse euclidean distance
cap = g.new_edge_property("double")
for e in g.edges():
    cap[e] = min((1.0 / norm(pos[e.target()].a - pos[e.source()].a), 10))
g.edge_properties["cap"] = cap
g.vertex_properties["pos"] = pos
g.save("flow-example.xml.gz")
gt.graph_draw(g, pos=pos, edge_pen_width=gt.prop_to_size(cap, mi=0, ma=3, power=1),
              output="flow-example.pdf")

Example network used in the documentation below. The edge capacities are represented by the edge width.