graph_tool.flow

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")
_images/flow-example.png

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