graphmaxflow
(Removed) Calculate maximum flow in directed graph
graphmaxflow
has been removed. Use maxflow
instead. For details, see Version History.
Syntax
[
MaxFlow
, FlowMatrix
, Cut
] = graphmaxflow(G
, SNode
, TNode
)
[...] = graphmaxflow(G
, SNode
, TNode
, ...'Capacity', CapacityValue
, ...)
[...] = graphmaxflow(G
, SNode
, TNode
, ...'Method', MethodValue
, ...)
Arguments
G
| N-by-N adjacency 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 column-wise. By
default, graphmaxflow gets capacity information from the
nonzero entries in matrix G . |
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 directed graph MaxFlow
, FlowMatrix
, Cut
] = graphmaxflow(G
, SNode
, TNode
)G
from node
SNode
to node TNode
. Input
G
is an N-by-N adjacency 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 adjacency 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
)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 column-wise. 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 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).