Flows¶
Algorithms¶
We are given a weighted directed or undirected graph \(G(V,E)\). Each edge \(e \in E\) has an associated nonnegative capacity \(c_e \ge 0\). The maximum flow problem involves finding a feasible flow \(f: E \mapsto \mathbb{R}_{0+}\) of maximum value. A flow is feasible if:
the flow \(f(e)\) of an edge \(e\) does not exceed its capacity, and
for each vertex except the source and sink, the sum of incoming flows is equal to the sum of outgoing flows.
Computing maximum st flows can be performed using the following function.

jgrapht.algorithms.flow.
max_st_flow
(graph, source, sink)[source]¶ Compute a maximum flow using the Pushrelabel algorithm.
This is a \(\mathcal{O}(n^3)\) algorithm where \(n\) is the number of vertices of the graph. For more details on the algorithm see:
Andrew V. Goldberg and Robert Tarjan. A new approach to the maximum flow problem. Proceedings of STOC ‘86.
The algorithm uses the graph edge weights as the network edge capacities.
 Parameters
graph – The input graph. This can be either directed or undirected. Edge capacities are taken from the edge weights.
source – The source vertex
sink – The sink vertex.
 Returns
The max st flow.
When the user requires more advanced control over the selected algorithm, the following functions are provided.

jgrapht.algorithms.flow.
push_relabel
(graph, source, sink)[source]¶ Compute a maximum flow using the Pushrelabel algorithm.
This is a \(\mathcal{O}(n^3)\) algorithm where \(n\) is the number of vertices of the graph. For more details on the algorithm see:
Andrew V. Goldberg and Robert Tarjan. A new approach to the maximum flow problem. Proceedings of STOC ‘86.
The algorithm uses the graph edge weights as the network edge capacities. It returns a maximum st flow and a minimum st cut with the same value.
 Parameters
graph – The input graph. This can be either directed or undirected. Edge capacities are taken from the edge weights.
source – The source vertex
sink – The sink vertex.
 Returns
A tuple (max st flow, min st cut).

jgrapht.algorithms.flow.
dinic
(graph, source, sink)[source]¶ Compute a maximum flow using Dinic’s algorithm with scaling.
This is a \(\mathcal{O}(n^2 m)\) algorithm where \(n\) is the number of vertices and \(m\) the number of edges of the graph.
The algorithm uses the graph edge weights as the network edge capacities. It returns a maximum st flow and a minimum st cut with the same value.
 Parameters
graph – The input graph. This can be either directed or undirected. Edge capacities are taken from the edge weights.
source – The source vertex
sink – The sink vertex.
 Returns
A tuple (max st flow, min st cut).

jgrapht.algorithms.flow.
edmonds_karp
(graph, source, sink)[source]¶ Compute a maximum flow using the EdmondsKarp variant of the FordFulkerson algorithm.
This is a \(\mathcal{O}(n m^2)\) algorithm where \(n\) is the number of vertices and \(m\) the number of edges of the graph.
The algorithm uses the graph edge weights as the network edge capacities. It returns a maximum st flow and a minimum st cut with the same value.
Note
This implementation assumes that the graph does not contain selfloops or multipleedges.
 Parameters
graph – The input graph. This can be either directed or undirected. Edge capacities are taken from the edge weights.
source – The source vertex
sink – The sink vertex.
 Returns
A tuple (max st flow, min st cut).
Computing maximum flow values between all pairs of vertices in an undirected network can be performed using:

jgrapht.algorithms.flow.
equivalent_flow_tree_gusfield
(graph)[source]¶ Computes an Equivalent Flow Tree using Gusfield’s algorithm.
Equivalent flow trees can be used to calculate the maximum flow value between all pairs of vertices in an undirected network. It does so by performing \(n1\) minimum st cut computations.
For more details see:
Gusfield, D, Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 19(1), p142155, 1990
This implementation uses the pushrelabel algorithm for the minimum st cut which is \(\mathcal{O}(n^3)\). The total complexity is, therefore, \(\mathcal{O}(n^4)\).
 Parameters
graph – an undirected network
 Returns
an equivalent flow tree as an instance of
jgrapht.types.EquivalentFlowTree