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  Character vector that specifies the algorithm used to find
the minimal spanning tree (MST). Choices are:

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.
The algorithm that determines Cut
,
all minimum cuts, has a time complexity of O(2^
,
where N is the number of nodes. If this information
is not needed, use the N
)graphmaxflow
function
without the third output.
[...] = 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:
[...] = graphmaxflow(
lets you specify custom capacities
for the edges. 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
.
[...] = graphmaxflow(
lets you specify the algorithm
used to find the minimal spanning tree (MST). Choices are: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.
[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