Flows¶
Algorithms¶
We are given a weighted directed or undirected graph \(G(V,E)\). Each edge \(e \in E\) has an associated non-negative 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 s-t flows can be performed using the following function.
-
jgrapht.algorithms.flow.max_st_flow(graph, source, sink)[source]¶ Compute a maximum flow using the Push-relabel 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 s-t 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 Push-relabel 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 s-t flow and a minimum s-t 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 s-t flow, min s-t 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 s-t flow and a minimum s-t 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 s-t flow, min s-t cut).
-
jgrapht.algorithms.flow.edmonds_karp(graph, source, sink)[source]¶ Compute a maximum flow using the Edmonds-Karp variant of the Ford-Fulkerson 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 s-t flow and a minimum s-t cut with the same value.
Note
This implementation assumes that the graph does not contain self-loops or multiple-edges.
- 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 s-t flow, min s-t 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 \(n-1\) minimum s-t cut computations.
For more details see:
Gusfield, D, Very simple methods for all pairs network flow analysis. SIAM Journal on Computing, 19(1), p142-155, 1990
This implementation uses the push-relabel algorithm for the minimum s-t 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