`maxflow`

Maximum flow through a network from a source to a sink.

Category: Mathematics > Graph and Network Algorithms

Syntax

mf = maxflow(G, s, t)

Returns the value of the maximum flow from node s to node t.

[mf, GF] = maxflow(G, s, t)

Also returns a graph holding the flow on each edge.

Description

The maximum flow is how much can be pushed from s to t without exceeding any edge capacity. By the max-flow min-cut theorem it equals the capacity of the cheapest set of edges whose removal disconnects t from s. The classic uses are transport and pipe networks, bipartite matching and connectivity.

Input arguments

G: A graph or digraph whose Weight column holds the edge capacities. Without weights every capacity is 1.
s, t: Source and sink nodes.

Output arguments

mf: Value of the maximum flow.
GF: Graph with the same nodes and edges as G, where Weight is the flow carried by each edge.

Example

Two routes with limited capacity

D = digraph([1 1 2 3], [2 3 4 4], [3 2 2 3]);
[mf, GF] = maxflow(D, 1, 4);
mf
GF.Edges.Weight'

Output

mf = 4
ans = 1×4

     2     2     2     2

maxflow