Calculate maximum flow in directed graph
[
MaxFlow
, FlowMatrix
, Cut
] = graphmaxflow(G
, SNode
, TNode
)[...] = graphmaxflow(
G
, SNode
, TNode
, ...'Capacity', CapacityValue
, ...)[...] = graphmaxflow(
G
, SNode
, TNode
, ...'Method', MethodValue
, ...)
G  NbyN sparse matrix that represents a directed graph. Nonzero
entries in matrix G represent the capacities of
the edges. 
SNode  Node in G . 
TNode  Node in G . 
CapacityValue  Column vector that specifies custom capacities for the edges
in matrix G . It must have one entry for
every nonzero value (edge) in matrix G .
The order of the custom capacities in the vector must match the order
of the nonzero values in matrix G when
it is traversed columnwise. By default, graphmaxflow gets
capacity information from the nonzero entries in matrix G . 
MethodValue  String that specifies the algorithm used to find the minimal
spanning tree (MST). Choices are:

Tip For introductory information on graph theory functions, see Graph Theory Functions. 
[
calculates
the maximum flow of directed graph MaxFlow
, FlowMatrix
, Cut
] = graphmaxflow(G
, SNode
, TNode
)G
from
node SNode
to node TNode
.
Input G
is an NbyN sparse matrix that
represents a directed graph. Nonzero entries in matrix G
represent
the capacities of the edges. Output MaxFlow
is
the maximum flow, and FlowMatrix
is a sparse
matrix with all the flow values for every edge. FlowMatrix
(X
,Y
)
is the flow from node X
to node Y
.
Output Cut
is a logical row vector indicating
the nodes connected to SNode
after calculating
the minimum cut between SNode
and TNode
.
If several solutions to the minimum cut problem exist, then Cut
is
a matrix.
Tip
The algorithm that determines 
[...] = graphmaxflow(
calls G
, SNode
, TNode
, ...'PropertyName
', PropertyValue
, ...)graphmaxflow
with
optional properties that use property name/property value pairs. You
can specify one or more properties in any order. Each PropertyName
must
be enclosed in single quotes and is case insensitive. These property
name/property value pairs are as follows:
lets you specify custom capacities
for the edges. [...] = graphmaxflow(
G
, SNode
, TNode
, ...'Capacity', CapacityValue
, ...)CapacityValue
is a column
vector having one entry for every nonzero value (edge) in matrix G
.
The order of the custom capacities in the vector must match the order
of the nonzero values in matrix G
when
it is traversed columnwise. By default, graphmaxflow
gets
capacity information from the nonzero entries in matrix G
.
lets you specify the algorithm
used to find the minimal spanning tree (MST). Choices are:[...] = graphmaxflow(
G
, SNode
, TNode
, ...'Method', MethodValue
, ...)
'Edmonds'
— Uses the Edmonds
and Karp algorithm, the implementation of which is based on a variation
called the labeling algorithm. Time complexity
is O(N*E^2)
, where N
and E
are
the number of nodes and edges respectively.
'Goldberg'
— Default algorithm.
Uses the Goldberg algorithm, which uses the generic method known as preflowpush.
Time complexity is O(N^2*sqrt(E))
, where N
and E
are
the number of nodes and edges respectively.
Create a directed graph with six nodes and eight edges.
cm = sparse([1 1 2 2 3 3 4 5],[2 3 4 5 4 5 6 6],...
[2 3 3 1 1 1 2 3],6,6)cm =
(1,2) 2
(1,3) 3
(2,4) 3
(3,4) 1
(2,5) 1
(3,5) 1
(4,6) 2
(5,6) 3
Calculate the maximum flow in the graph from node 1 to node 6.
[M,F,K] = graphmaxflow(cm,1,6) M = 4 F = (1,2) 2 (1,3) 2 (2,4) 1 (3,4) 1 (2,5) 1 (3,5) 1 (4,6) 2 (5,6) 2 K = 1 1 1 1 0 0 1 0 1 0 0 0
Notice that K
is a tworow matrix because
there are two possible solutions to the minimum cut problem.
View the graph with the original capacities.
h = view(biograph(cm,[],'ShowWeights','on'))
View the graph with the calculated maximum flows.
view(biograph(F,[],'ShowWeights','on'))
Show one solution to the minimum cut problem in the original graph.
set(h.Nodes(K(1,:)),'Color',[1 0 0])
Notice that in the three edges that connect the source nodes (red) to the destination nodes (yellow), the original capacities and the calculated maximum flows are the same.
[1] Edmonds, J. and Karp, R.M. (1972). Theoretical improvements in the algorithmic efficiency for network flow problems. Journal of the ACM 19, 248264.
[2] Goldberg, A.V. (1985). A New MaxFlow Algorithm. MIT Technical Report MIT/LCS/TM291, Laboratory for Computer Science, MIT.
[3] Siek, J.G., Lee, LQ, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).