Documentation

This is machine translation

Translated by Microsoft
Mouse over text to see original. Click the button below to return to the English verison of the page.

maxflow (biograph)

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

BGObjBiograph object created by biograph (object constructor).
SNodeNode in a directed graph represented by an N-by-N adjacency matrix extracted from biograph object, BGObj.
TNodeNode in a directed graph represented by an N-by-N adjacency matrix extracted from biograph object, BGObj.
CapacityValueColumn 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.
MethodValueCharacter vector that specifies the algorithm used to find the minimal spanning tree (MST). Choices are:
  • '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 preflow-push. Time complexity is O(N^2*sqrt(E)), where N and E are the number of nodes and edges respectively.

Description

[MaxFlow, FlowMatrix, Cut] = maxflow(BGObj, SNode, TNode) calculates the maximum flow of a directed graph represented by an N-by-N adjacency matrix extracted from a biograph object, 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^N), where N is the number of nodes. If this information is not needed, use the maxflow method without the third output.

[...] = maxflow(BGObj, SNode, TNode, ...'PropertyName', PropertyValue, ...) calls 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(BGObj, SNode, TNode, ...'Capacity', CapacityValue, ...)
lets you specify custom capacities for the edges. 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(BGObj, SNode, TNode, ...'Method', MethodValue, ...) lets you specify the algorithm used to find the minimal spanning tree (MST). Choices are:

  • '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 preflow-push. Time complexity is O(N^2*sqrt(E)), where N and E are the number of nodes and edges respectively.

More About

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).

Introduced in R2006b

Was this topic helpful?