Warning

This documents an unmaintained version of NetworkX. Please upgrade to a maintained version and see the current NetworkX documentation.

Flows

Maximum Flow

maximum_flow(G, s, t[, capacity, flow_func]) Find a maximum single-commodity flow.
maximum_flow_value(G, s, t[, capacity, ...]) Find the value of maximum single-commodity flow.
minimum_cut(G, s, t[, capacity, flow_func]) Compute the value and the node partition of a minimum (s, t)-cut.
minimum_cut_value(G, s, t[, capacity, flow_func]) 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.

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]) Return 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]) Return 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.