# 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

## Types¶

Flows are represented using instances of the following classes.

class jgrapht.types.Flow[source]

A network flow.

This is a dictionary from edges to double values.

abstract sink()[source]

Sink vertex in flow network.

abstract source()[source]

Source vertex in flow network.

property value

Flow value.

class jgrapht.types.EquivalentFlowTree[source]

An Equivalent Flow Tree.

abstract as_graph()[source]

Compute the equivalent flow tree as a graph.

abstract max_st_flow_value(s, t)[source]

Compute the maximum s-t flow value.