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(G, s, t[, capacity, residual, …])

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

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

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

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

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

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

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

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

gomory_hu_tree(G[, capacity, flow_func])

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

Build a residual network and initialize a zero flow.

`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(G[, demand, capacity, …])

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