maxflow

Maximum flow in graph

Syntax

mf = maxflow(G,s,t)

mf = maxflow(G,s,t,algorithm)

[mf,GF] = maxflow(___)

[mf,GF,cs,ct] = maxflow(___)

Description

mf = maxflow(G,s,t) returns the maximum flow between nodes s and t. If graph G is unweighted (that is, G.Edges does not contain the variable Weight), then maxflow treats all graph edges as having a weight equal to 1.

mf = maxflow(G,s,t,algorithm) specifies the maximum flow algorithm to use. This syntax is only available if G is a directed graph.

[mf,GF] = maxflow(___) also returns a directed graph object, GF, using any of the input arguments in previous syntaxes. GF is formed using only the edges in G that have nonzero flow values.

[mf,GF,cs,ct] = maxflow(___) additionally returns the source and target node IDs, cs and ct, representing the minimum cut associated with the maximum flow.

Examples

Maximum Flow in Graph

Create and plot a weighted graph. The weighted edges represent flow capacities.

s = [1 1 2 2 3 4 4 4 5 5];
t = [2 3 3 4 5 3 5 6 4 6];
weights = [0.77 0.44 0.67 0.75 0.89 0.90 2 0.76 1 1];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight,'Layout','layered');

Determine the maximum flow from node 1 to node 6.

mf = maxflow(G,1,6)

mf = 1.2100

Maximum Flow with Specified Algorithm

Create and plot a graph. The weighted edges represent flow capacities.

s = [1 1 2 2 3 3 4];
t = [2 3 3 4 4 5 5];
weights = [10 6 15 5 10 3 8];
G = digraph(s,t,weights);
H = plot(G,'EdgeLabel',G.Edges.Weight);

Find the maximum flow value between node 1 and node 5. Specify 'augmentpath' to use the Ford-Fulkerson algorithm, and use two outputs to return a graph of the nonzero flows.

[mf,GF] = maxflow(G,1,5,'augmentpath')

mf = 11

GF = 
  digraph with properties:

    Edges: [6x2 table]
    Nodes: [5x0 table]

Highlight and label the graph of nonzero flows.

H.EdgeLabel = {};
highlight(H,GF,'EdgeColor','r','LineWidth',2);
st = GF.Edges.EndNodes;
labeledge(H,st(:,1),st(:,2),GF.Edges.Weight);

Minimum Cut Computation

Create and plot a weighted graph. The edge weights represent flow capacities.

s = [1 1 2 3 3 4 4 5 5];
t = [2 3 3 2 5 5 6 4 6];
weights = [0.77 0.44 0.67 0.69 0.73 2 0.78 1 1];
G = digraph(s,t,weights);
plot(G,'EdgeLabel',G.Edges.Weight,'Layout','layered')

Find the maximum flow and minimum cut of the graph.

[mf,~,cs,ct] = maxflow(G,1,6)

mf = 0.7300

cs = 3×1

     1
     2
     3

ct = 3×1

     4
     5
     6

Plot the minimum cut, using the cs nodes as sources and the ct nodes as sinks. Highlight the cs nodes as red and the ct nodes as green. Note that the weight of the edge that connects these two sets of nodes is equal to the maximum flow.

H = plot(G,'Layout','layered','Sources',cs,'Sinks',ct, ...
    'EdgeLabel',G.Edges.Weight);
highlight(H,cs,'NodeColor','red')
highlight(H,ct,'NodeColor','green')

Input Arguments

G — Input graph

graph object | digraph object

Input graph, specified as either a graph or digraph object. Use graph to create an undirected graph or digraph to create a directed graph.

Example: G = graph(1,2)

Example: G = digraph([1 2],[2 3])

s,t — Node pair (as separate arguments)

node indices | node names

Node pair, specified as separate arguments of node indices or node names to indicate the source node and target node. This table shows the different ways to refer to nodes either by their node indices or by their node names.

Value	Example
Scalar node index	1
Character vector node name	'A'
String scalar node name	"A"

Example: mf = maxflow(G,'A','B')

Example: mf = maxflow(G,1,10)

Data Types: double | char | string

algorithm — Maximum flow algorithm

'searchtrees' (default) | 'augmentpath' | 'pushrelabel'

Maximum flow algorithm, specified as one of the entries in the table.

Note

You can only specify nondefault algorithm options with a directed graph.

Option	Description
'searchtrees' (default)	Uses the Boykov-Kolmogorov algorithm. Computes the maximum flow by constructing two search trees associated with nodes s and t.
'augmentpath'	Uses the Ford-Fulkerson algorithm. Computes the maximum flow iteratively by finding an augmenting path in a residual directed graph. The directed graph cannot have any parallel edges of opposite direction between the same two nodes, unless the weight of one of those edges is zero. So if the graph contains edge [i j], then it can contain the reverse edge [j i] only if the weight of [i j] is zero and/or the weight of [j i] is zero.
'pushrelabel'	Computes the maximum flow by pushing a node's excess flow to its neighbors and then relabeling the node. The directed graph cannot have any parallel edges of opposite direction between the same two nodes, unless the weight of one of those edges is zero. So if the graph contains edge [i j], then it can contain the reverse edge [j i] only if the weight of [i j] is zero and/or the weight of [j i] is zero.

Example: mf = maxflow(G,'A','D','augmentpath')

Output Arguments

mf — Maximum flow

scalar

Maximum flow, returned as a scalar.

GF — Directed graph of flows

digraph object

Directed graph of flows, returned as a digraph object. GF contains the same nodes as G, but only contains those edges of G that have a nonzero flow. For multigraphs with multiple edges between the same two nodes, GF contains a single edge reflecting the flow through the multiple edges.

cs — Minimum cut source node IDs

node indices | node names

Minimum cut source node IDs, returned as node indices or node names.

• If s and t specify numeric node indices, then cs and ct also contain node indices.

• If s and t specify node names, then cs and ct also contain node names.

ct — Minimum cut target node IDs

scalar | vector | character vector | cell array of character vectors

Minimum cut target node IDs, returned as node indices or node names.

• If s and t specify numeric node indices, then cs and ct also contain node indices.

• If s and t specify node names, then cs and ct also contain node names.

More About

Maximum Flow

In the context of maximum flow, the edges in a graph are considered to have a capacity as represented by the edge weight. The capacity of an edge is the amount of flow that can pass through that edge. Therefore, the maximum flow between two nodes in a graph maximizes the amount of flow passing from the source node, s, to the target node, t, based on the capacities of the connecting edges.

Minimum Cut

A minimum cut partitions the directed graph nodes into two sets, cs and ct, such that the sum of the weights of all edges connecting cs and ct (weight of the cut) is minimized. The weight of the minimum cut is equal to the maximum flow value, mf.

The entries in cs and ct indicate the nodes of G associated with nodes s and t, respectively. cs and ct satisfy numel(cs) + numel(ct) = numnodes(G).

Version History

Introduced in R2015b