maxflow (biograph)
(Removed) Calculate maximum flow in biograph object
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 N-by-N adjacency matrix
extracted from biograph object,
BGObj . |
TNode | Node in a directed graph represented by an N-by-N adjacency matrix
extracted from biograph object,
BGObj . |
CapacityValue | Column vector that specifies custom capacities for the edges in the
N-by-N adjacency matrix. It must have one entry for every nonzero value
(edge) in the N-by-N adjacency matrix. The order of the custom
capacities in the vector must match the order of the nonzero values in
the N-by-N adjacency matrix when it is traversed column-wise. By
default, maxflow gets capacity information from the
nonzero entries in the N-by-N 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 N-by-N 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 N-by-N 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 column-wise. 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 preflow-push. 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, 248-264.
[2] Goldberg, A.V. (1985). A New Max-Flow Algorithm. MIT Technical Report MIT/LCS/TM-291, Laboratory for Computer Science, MIT.
[3] Siek, J.G., Lee, L-Q, and Lumsdaine, A. (2002). The Boost Graph Library User Guide and Reference Manual, (Upper Saddle River, NJ:Pearson Education).