finds the maximum flow between source vertex s and target vertex t in a graph g.
finds the maximum flow between vertex indices s and t in a graph with edge capacity matrix m.
finds the maximum flow between multi-sources s1, … and multi-targets t1, ….
returns the value of "property".
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.
Examplesopen allclose all
Basic Examples (2)
FindMaximumFlow works with undirected graphs:
FindMaximumFlow works with large graphs:
Transportation Networks (3)
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:
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:
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:
Properties & Relations (5)
The vertex connectivity between two vertices can be found using FindMaximumFlow: