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