maxflow (biograph)
(To be removed) Calculate maximum flow in biograph object
maxflow (biograph)
will be removed in a future release. Use the maxflow
function of graph
or digraph
instead.
Syntax
[
MaxFlow
, FlowMatrix
, Cut
] = maxflow(BGObj
, SNode
, TNode
)
[...] = maxflow(BGObj
, SNode
, TNode
, ...'Capacity', CapacityValue
, ...)
[...] = maxflow(BGObj
, SNode
, TNode
, ...'Method', MethodValue
, ...)
Arguments
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 or string that specifies the algorithm used to find
the minimal spanning tree (MST). Choices are:

Description
Tip
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.
Tip
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 isO(N*E^2)
, whereN
andE
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 isO(N^2*sqrt(E))
, whereN
andE
are the number of nodes and edges respectively.
References
[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).