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,{s₁,…},{t₁,…}]

finds the maximum flow between multi-sources s₁, … and multi-targets t₁, ….

✖

FindMaximumFlow[data,source,target,"property"]

returns the value of "property".

✖

FindMaximumFlow[{vw,…},…]

uses rules vw 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 all

Basic Examples (2)Summary of the most common use cases

Find the maximum flow between two vertices in a graph:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-qwzt6s

Out[1]=1

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

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-5xwv1k

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-0qrgps

Out[2]=2

Highlight the flow:

In[3]:=3

✖

https://wolfram.com/xid/0btng3or8t0t-cnjuhi

Out[3]=3

Scope (10)Survey of the scope of standard use cases

FindMaximumFlow works with undirected graphs:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-gay90t

Out[1]=1

Directed graphs:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-1vbgvr

Out[1]=1

Multigraphs:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-s2h57c

Out[1]=1

Mixed graphs:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-i4ww80

Out[1]=1

Graphs with edge capacities:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-5e2cau

Out[1]=1

Use rules to specify the graph:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-bndh30

Out[1]=1

Compute the maximum flow for an edge capacity matrix:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-cojxn

Out[1]=1

Compute the maximum flow between multi-sources and multi-sinks:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-3vnkdo

Out[1]=1

Find properties of a maximum flow:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-7cd155

The value of the maximum flow:

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-gtx79i

Out[2]=2

List of edges contributing to the flow:

In[3]:=3

✖

https://wolfram.com/xid/0btng3or8t0t-bd3lak

Out[3]=3

Matrix of edge flows:

In[4]:=4

✖

https://wolfram.com/xid/0btng3or8t0t-scruz

Display the flow:

In[5]:=5

✖

https://wolfram.com/xid/0btng3or8t0t-q6o4gi

Out[5]=5

FindMaximumFlow works with large graphs:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-bdnamb

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-gegolt

Out[2]=2

In[3]:=3

✖

https://wolfram.com/xid/0btng3or8t0t-7ckwl

Out[3]=3

Options (2)Common values & functionality for each option

EdgeCapacity (1)

By default, the edge capacity of an edge is taken to be its EdgeCapacity property if available, otherwise 1:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-uc5puh

Out[1]=1

Use EdgeCapacity->capacities to set the edge capacity:

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-dh45n

Out[2]=2

VertexCapacity (1)

By default, the vertex capacity of a vertex is taken to be its VertexCapacity property if available, otherwise Infinity:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-m22fcr

Out[1]=1

Use VertexCapacity->capacities to set the vertex capacity:

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-gl2o5n

Out[2]=2

Applications (7)Sample problems that can be solved with this function

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:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-iz1zda

The maximum flow value from indexed cities {1,5,6,7,9,12,13,18} to {44,40}:

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-4llese

In[3]:=3

✖

https://wolfram.com/xid/0btng3or8t0t-g2ewlb

Out[3]=3

Visualize the flow:

In[4]:=4

✖

https://wolfram.com/xid/0btng3or8t0t-zw9ypw

Out[4]=4

A railroad network serving six major Canadian cities, with the daily number of car compartments:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-eu67n0

Find the maximum number of compartments that can be carried from Vancouver to Winnipeg:

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-5t58mo

In[3]:=3

✖

https://wolfram.com/xid/0btng3or8t0t-ttovxg

Out[3]=3

Number of compartments between cities:

In[4]:=4

✖

https://wolfram.com/xid/0btng3or8t0t-f9r2n

Out[4]=4

Show the flows of compartments:

In[5]:=5

✖

https://wolfram.com/xid/0btng3or8t0t-sed99g

Out[5]=5

In a regional power distribution network below with given capacities, find the maximum power that can be distributed to WanChai:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-rjrd1f

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-wc984

Out[2]=2

Show the flow:

In[3]:=3

✖

https://wolfram.com/xid/0btng3or8t0t-oym3f0

Out[3]=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:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-hfzcnr

Find the maximum flow and the flow graph:

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-gzvg05

Out[2]=2

In[3]:=3

✖

https://wolfram.com/xid/0btng3or8t0t-eqdo4a

Out[3]=3

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:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-haqilu

Since the maximum flow value equals 4, this means that the town has a balanced council:

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-im02q7

Out[2]=2

The flow graph shows that a possible balanced council could be R₁, R₂, R₄ and R₅:

In[3]:=3

✖

https://wolfram.com/xid/0btng3or8t0t-gcubpv

Out[3]=3

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:

In[1]:=1

✖

https://wolfram.com/xid/0btng3or8t0t-et0a2

The maximum flow from all employees to all tasks gives the number of simultaneous jobs:

In[2]:=2

✖

https://wolfram.com/xid/0btng3or8t0t-c1ep2b

In[3]:=3

✖

https://wolfram.com/xid/0btng3or8t0t-eoyvc1

Out[3]=3

Show possible job assignments:

In[4]:=4

✖

https://wolfram.com/xid/0btng3or8t0t-ldiiyb

Out[4]=4

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:

In[1]:=1