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 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:
-
EdgeCapacity Automatic capacity for each edge VertexCapacity Automatic capacity 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.
Examples
open allclose allBasic Examples (2)
Scope (10)
FindMaximumFlow works with undirected graphs:
Use rules to specify the graph:
Compute the maximum flow for an edge capacity matrix:
Compute the maximum flow between multi-sources and multi-sinks:
Find properties of a maximum flow:
The value of the maximum flow:
List of edges contributing to the flow:
FindMaximumFlow works with large graphs:
Options (2)
EdgeCapacity (1)
By default, the edge capacity of an edge is taken to be its EdgeCapacity property if available, otherwise 1:
Use EdgeCapacity->capacities to set the edge capacity:
VertexCapacity (1)
By default, the vertex capacity of a vertex is taken to be its VertexCapacity property if available, otherwise Infinity:
Use VertexCapacity->capacities to set the vertex capacity:
Applications (7)
Transportation Networks (3)
Based on the 1940 Soviet railway network, find the maximum amount of cargo that can be transported from sources in the Western Soviet Union to destinations in Eastern Europe:
The maximum flow value from indexed cities {1,5,6,7,9,12,13,18} to {44,40}:
A railroad network serving six major Canadian cities, with the daily number of car compartments:
Find the maximum number of compartments that can be carried from Vancouver to Winnipeg:
Number of compartments between cities:
Show the flows of compartments:
In a regional power distribution network below with given capacities, find the maximum power that can be distributed to WanChai:
Network Connectivity (2)
A directed network that describes the flow of information among 10 organizations concerned with social welfare issues in one Midwestern US city. Find the maximum possible information flow from COUN to COMM:
Find the maximum flow and the flow graph:
A town has 7 residents, 4 clubs and 3 political parties. Each resident is a member of at least one club and can belong to exactly one political party. In a balanced council each club must nominate one of its members to represent it in town council so that the number of council members belonging to the political party 
is at most 
. Find if it is possible to create a balanced council:
Since the maximum flow value equals 4, this means that the town has a balanced council:
The flow graph shows that a possible balanced council could be R1, R2, R4 and R5:
Assignment Problems (2)
A company has a number of different jobs. Each employee is suited for some of these jobs, and each person can perform at most one job at a time. Find the maximum number of jobs that can be performed at the same time:
The maximum flow from all employees to all tasks gives the number of simultaneous jobs:
Show possible job assignments:
Given a set of women, each of whom has a preference for some subset of men, find a maximal matching where only matches that agree with preferences are allowed:
Since you want each person to match once, restrict the vertex capacity to 1:
Properties & Relations (5)
The sum of in-flows is equal to the sum of out-flows for interior vertices:
The in-flow for interior vertices:
The out-flow for interior vertices:
A graph with self-loops is treated as a simple graph:
The edge connectivity between two vertices is equal to the value of the maximum flow:
The vertex connectivity between two vertices can be found using FindMaximumFlow:
Text
Wolfram Research (2012), FindMaximumFlow, Wolfram Language function, https://reference.wolfram.com/language/ref/FindMaximumFlow.html (updated 2015).
CMS
Wolfram Language. 2012. "FindMaximumFlow." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2015. https://reference.wolfram.com/language/ref/FindMaximumFlow.html.
APA
Wolfram Language. (2012). FindMaximumFlow. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/FindMaximumFlow.html