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 , ... and multi-targets , ... .

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

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 .
  • 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 .
  • 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.
New in 9
New to Mathematica? Find your learning path »
Have a question? Ask support »