Flows#

Maximum Flow#

maximum_flow(flowG, _s, _t[, capacity, ...])

Find a maximum single-commodity flow.

maximum_flow_value(flowG, _s, _t[, ...])

Find the value of maximum single-commodity flow.

minimum_cut(flowG, _s, _t[, capacity, flow_func])

Compute the value and the node partition of a minimum (s, t)-cut.

minimum_cut_value(flowG, _s, _t[, capacity, ...])

Compute the value of a minimum (s, t)-cut.

Edmonds-Karp#

edmonds_karp(G, s, t[, capacity, residual, ...])

Find a maximum single-commodity flow using the Edmonds-Karp algorithm.

Shortest Augmenting Path#

shortest_augmenting_path(G, s, t[, ...])

Find a maximum single-commodity flow using the shortest augmenting path algorithm.

Preflow-Push#

preflow_push(G, s, t[, capacity, residual, ...])

Find a maximum single-commodity flow using the highest-label preflow-push algorithm.

Dinitz#

dinitz(G, s, t[, capacity, residual, ...])

Find a maximum single-commodity flow using Dinitz' algorithm.

Boykov-Kolmogorov#

boykov_kolmogorov(G, s, t[, capacity, ...])

Find a maximum single-commodity flow using Boykov-Kolmogorov algorithm.

Gomory-Hu Tree#

gomory_hu_tree(G[, capacity, flow_func])

Returns the Gomory-Hu tree of an undirected graph G.

Utils#

build_residual_network(G, capacity)

Build a residual network and initialize a zero flow.

Network Simplex#

network_simplex(G[, demand, capacity, weight])

Find a minimum cost flow satisfying all demands in digraph G.

min_cost_flow_cost(G[, demand, capacity, weight])

Find the cost of a minimum cost flow satisfying all demands in digraph G.

min_cost_flow(G[, demand, capacity, weight])

Returns a minimum cost flow satisfying all demands in digraph G.

cost_of_flow(G, flowDict[, weight])

Compute the cost of the flow given by flowDict on graph G.

max_flow_min_cost(G, s, t[, capacity, weight])

Returns a maximum (s, t)-flow of minimum cost.

Capacity Scaling Minimum Cost Flow#

capacity_scaling(G[, demand, capacity, ...])

Find a minimum cost flow satisfying all demands in digraph G.