Calculate maximum flow in biograph object
[
MaxFlow
, FlowMatrix
, Cut
] = maxflow(BGObj
, SNode
, TNode
)
[...] = maxflow(BGObj
, SNode
, TNode
, ...'Capacity', CapacityValue
, ...)
[...] = maxflow(BGObj
, SNode
, TNode
, ...'Method', MethodValue
, ...)
BGObj  Biograph object created by biograph (object
constructor). 
SNode  Node in a directed graph represented by an NbyN adjacency
matrix extracted from biograph object, BGObj . 
TNode  Node in a directed graph represented by an NbyN adjacency
matrix extracted from biograph object, BGObj . 
CapacityValue  Column vector that specifies custom capacities for the edges
in the NbyN adjacency matrix. It must have one entry for every nonzero
value (edge) in the NbyN adjacency matrix. The order of the custom
capacities in the vector must match the order of the nonzero values
in the NbyN adjacency matrix when it is traversed columnwise. By
default, maxflow gets capacity information from
the nonzero entries in the NbyN adjacency matrix. 
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 a directed graph represented by an
NbyN adjacency matrix extracted from a biograph object, MaxFlow
, FlowMatrix
, Cut
] = maxflow(BGObj
, SNode
, TNode
)BGObj
,
from node SNode
to node TNode
.
Nonzero entries in the matrix determine the capacity 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
)maxflow
method without
the third output.
[...] = maxflow(
calls BGObj
, SNode
, TNode
, ...'PropertyName
', PropertyValue
, ...)maxflow
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:
[...] = maxflow(
lets you specify custom capacities
for the edges. BGObj
, SNode
, TNode
, ...'Capacity', CapacityValue
, ...)CapacityValue
is a column
vector having one entry for every nonzero value (edge) in the NbyN
adjacency matrix. The order of the custom capacities in the vector
must match the order of the nonzero values in the matrix when it is
traversed columnwise. By default, graphmaxflow
gets
capacity information from the nonzero entries in the matrix.
[...] = maxflow(
lets you specify the algorithm
used to find the minimal spanning tree (MST). Choices are:BGObj
, 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).
allshortestpaths
 biograph
 conncomp
 graphmaxflow
 isdag
 isomorphism
 isspantree
 minspantree
 shortestpath
 topoorder
 traverse