Documentation Center 
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. 
[MaxFlow, FlowMatrix, Cut] = graphmaxflow(G, SNode, TNode)calculates the maximum flow of directed graph 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 Cut, all minimum cuts, has a time complexity of O(2^N), where N is the number of nodes. If this information is not needed, use the graphmaxflow function without the third output. 
[...] = graphmaxflow(G, SNode, TNode, ...'PropertyName', PropertyValue, ...) calls 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:
[...] = graphmaxflow(G, SNode, TNode, ...'Capacity', CapacityValue, ...) lets you specify custom capacities
for the edges. 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.
[...] = graphmaxflow(G, SNode, TNode, ...'Method', MethodValue, ...) lets you specify the algorithm used to find the minimal spanning tree (MST). Choices are:
'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).
graphallshortestpaths  graphconncomp  graphisdag  graphisomorphism  graphisspantree  graphminspantree  graphpred2path  graphshortestpath  graphtopoorder  graphtraverse  maxflow