FindMaximumFlow

FindMaximumFlow[g,s,t]
finds the maximum flow between source vertex s and target vertex t in a graph g.

FindMaximumFlow[m,s,t]
finds the maximum flow between vertex indices s and t in a graph with edge capacity matrix m.

FindMaximumFlow[data,{s1,},{t1,}]
finds the maximum flow between multi-sources s1, and multi-targets t1, .

FindMaximumFlow[data,source,target,"property"]
returns the value of "property".

FindMaximumFlow[{vw,},]
uses rules vw to specify the graph g.

Details and OptionsDetails and Options

  • FindMaximumFlow finds the maximum flow from a source vertex to a target vertex, subject to capacity constraints.
  • By default, the maximum flow is returned.
  • Matrices and SparseArray objects can be used in FindMaximumFlow.
  • For undirected graphs, edges are taken to have flows in both directions at the same time and same capacities.
  • Self-loops are ignored, and parallel edges are merged.
  • FindMaximumFlow[data,source,target,"OptimumFlowData"] returns an OptimumFlowData object flowdata that can be used to extract additional properties, using the form flowdata["property"].
  • FindMaximumFlow[data,source,target,"property"] can be used to directly give the value of "property".
  • Properties related to the optimal flow data include:
  • "EdgeList"list of edges contributing to the flow
    "FlowGraph"graph of vertices and edges contributing to the flow
    "FlowMatrix"matrix of edge flows between pairs of vertices
    "FlowTable"formatted table of edge flows
    "FlowValue"value of the flow
    "ResidualGraph"residual graph of the flow
    "VertexList"list of vertices contributing to the flow
  • The following options can be given:
  • EdgeCapacityAutomaticcapacity for each edge
    VertexCapacityAutomaticcapacity for each vertex
  • With the default setting EdgeCapacity->Automatic, the edge capacity of an edge is taken to be the EdgeCapacity of the graph g if available; otherwise, it is 1.
  • With the default setting VertexCapacity->Automatic, the vertex capacity of a vertex is taken to be the VertexCapacity of the graph g if available; otherwise, it is Infinity.
  • FindMaximumFlow works with undirected graphs, directed graphs, multigraphs, and mixed graphs.

ExamplesExamplesopen allclose all

Basic Examples  (2)Basic Examples  (2)

Find the maximum flow between two vertices in a graph:

In[1]:=
Click for copyable input
Out[1]=

Find the maximum flow between "s" and "t":

In[1]:=
Click for copyable input
In[2]:=
Click for copyable input
Out[2]=

Highlight the flow:

In[3]:=
Click for copyable input
Out[3]=
Introduced in 2012
(9.0)
| Updated in 2015
(10.3)