Skip to content

FindMaximumFlow

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

FindMaximumFlow[g, s, t]

gives the value of a maximum flow from s to t (s and t may be lists of sources and sinks). FindMaximumFlow[g, s, t, "prop"] gives "FlowValue", "FlowMatrix" (dense n x n matrix of edge flows) or "EdgeList" (edges carrying flow, oriented along it). Capacities come from the EdgeCapacity -> {c1, ...} option (EdgeList order), else from g's own EdgeCapacity, else 1; EdgeWeight is ignored; VertexCapacity -> {c1, ...} caps the flow through each vertex. Undirected edges carry flow either way. Dinic's algorithm; exact for integer capacities.

Examples (17)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (3)

In[1]:= FindMaximumFlow[CompleteGraph[4], 1, 4]
Out[1]= 3

In[2]:= FindMaximumFlow[CycleGraph[6], 1, 4, "EdgeList"]
Out[2]= {1 <-> 2, 1 <-> 6, 2 <-> 3, 3 <-> 4, 5 <-> 4, 6 <-> 5}

In[3]:= FindMaximumFlow[CycleGraph[6], {1, 2}, {4, 5}]
Out[3]= 2

Scope (1)

In[4]:= FindMaximumFlow[CycleGraph[4], 2, 2]
Out[4]= 0

Options (10)

In[5]:= FindMaximumFlow[Graph[{1->2,2->3,1->3}], 1, 3, EdgeCapacity -> {2, 3, 1}]
Out[5]= 3

In[6]:= FindMaximumFlow[Graph[{1->2,2->3,1->3}], 1, 3, "FlowMatrix", EdgeCapacity -> {2, 3, 1}]
Out[6]= {{0, 2, 1}, {0, 0, 2}, {0, 0, 0}}

In[7]:= FindMaximumFlow[Graph[{1->2,2->3,1->3}], 1, 3, EdgeCapacity -> {1/2, 3, 1}]
Out[7]= 1.5

In[8]:= FindMaximumFlow[Graph[{1->2, 2->3, 1->3}, EdgeCapacity -> {2, 3, 4}], 1, 3]
Out[8]= 6

In[9]:= FindMaximumFlow[Graph[{1,2,3},{1->2,2->3,1->3}, EdgeWeight->{5,5,5}], 1, 3]
Out[9]= 2

In[10]:= FindMaximumFlow[Graph[{1->2,2->3,1->3}], 1, 3, EdgeCapacity -> {Infinity, 3, 1}]
Out[10]= 4

In[11]:= FindMaximumFlow[Graph[{1->2,2->3,1->3}], 1, 3, EdgeCapacity -> {-1, 3, 1}]
Out[11]= FindMaximumFlow[Graph[<3 vertices, 3 edges>], 1, 3, EdgeCapacity -> {-1, 3, 1}]

In[12]:= FindMaximumFlow[PathGraph[{1, 2, 3}], 1, 3, EdgeCapacity -> {10, 10}, VertexCapacity -> {2, 10, 10}]
Out[12]= 2

In[13]:= FindMaximumFlow[CompleteGraph[4], {1, 2}, {3, 4}, VertexCapacity -> {3, 1, 1, 5}]
Out[13]= 3

In[14]:= FindMaximumFlow[PathGraph[{1, 2, 3}], 1, 3, VertexCapacity -> {1, 1/2, 1}]
Out[14]= 0.5

Applications (3)

Direct 3 plus 1 through vertex 2

In[15]:= FindMaximumFlow[Graph[{1, 2, 3}, {1 -> 2, 2 -> 3, 1 -> 3}, EdgeCapacity -> {2, 1, 3}], 1, 3]
Out[15]= 4

Unit capacities: three edge-disjoint paths

In[16]:= FindMaximumFlow[CompleteGraph[4], 1, 2]
Out[16]= 3

Bottlenecked by the middle edges

In[17]:= FindMaximumFlow[Graph[{1, 2, 3, 4}, {1 -> 2, 1 -> 3, 2 -> 4, 3 -> 4}, EdgeCapacity -> {3, 2, 2, 3}], 1, 4]
Out[17]= 4

Options & behaviour

EdgeWeight is not a capacity, an infinite capacity is allowed, s == t gives 0, and a negative capacity or a non-graph leaves the call unevaluated:

Implementation notes

Algorithm. builtin_find_maximum_flow computes the value of a maximum flow from s to t (either may be a list of sources/sinks) with Dinic's algorithm. A fourth argument selects the property: "FlowValue" (default), "FlowMatrix" (a dense n x n matrix of per-edge flows), or "EdgeList" (the edges carrying flow, oriented along it, in flow-matrix row-major order). Capacities come from EdgeCapacity -> {c1, ...} (else the graph's own EdgeCapacity, else 1); EdgeWeight is ignored. A VertexCapacity option caps the flow through each vertex, modelled by the split-vertex construction (v_in -> v_out). Several sources/sinks are wired to a super-source/super-sink. An undirected edge carries flow either way up to its capacity; a directed edge only forwards.

Data structures. Capacities are parsed into a scaled-int64 GfCap (exact integers; reals scaled by a shared power of two; Infinity as a finite stand-in above every finite sum) ā€” including a packed-buffer fast path that reads an NDArray capacity list without unpacking. The network is a GfNet CSR residual graph (adjacent forward/reverse arc pairs) with level-BFS truncated at the sink's level and an iterative current-arc blocking-flow search. The flow matrix is offered to the packer (pack_offer).

Complexity / limits. O(E sqrt(E)) on unit capacities; a handful of phases in practice. Exact Integer for integer capacities, Real otherwise, Infinity when the flow reaches the Infinity stand-in. A negative or symbolic capacity leaves the call unevaluated.

  • Part of the graph-algorithm family (flows, cuts, matchings, covers, cliques, independent sets, Hamiltonian cycles, isomorphism, planarity) implemented in src/graph/galg_*.c, declared in src/graph/graph_algos.h and registered by graph_algos_init(). Every head in the family reads graphs through the validated-graph memo, so on a graph built by Graph[...] it starts from pre-resolved integer endpoints. Every head is Protected, stays unevaluated on a non-graph (the *Q predicates give False), and returns a fresh value. Semantics and output forms were checked against Mathematica 15 by a randomized differential test (benchmarks/95-graph-algorithms/diff_mathematica.py, about 12k cases, 0 failures); where the answer is unique the outputs are identical.
  • s and t may be lists of sources / sinks; s == t gives 0.
  • "FlowValue" is the default. "FlowMatrix" is a dense n x n matrix of edge flows (packed); Mathematica returns a SparseArray, which Mathilda does not have. "EdgeList" gives the edges carrying flow, oriented along the flow, in flow-matrix row order.
  • Options: EdgeCapacity -> {c1, ...} (in EdgeList order) and VertexCapacity -> {c1, ...} (in VertexList order). Sources and sinks are capped by their own vertex capacity too, as in Mathematica. The two lists are parsed together onto one exact scale, so an exact EdgeCapacity mixes with a Rational/Real VertexCapacity (Mathematica leaves a non-integer VertexCapacity unevaluated). Matches Mathematica on 160 random vertex-capacitated instances (single and multiple terminals, directed and undirected). Where every capacity on the source side is Infinity, Mathematica 15 answers 0; Mathilda gives the true value (Infinity, or the finite bottleneck).
  • Capacities ignore EdgeWeight, exactly as Mathematica does. With no EdgeCapacity option (or EdgeCapacity -> Automatic) the capacities are the graph's own EdgeCapacity when it was built with one (Graph[e, EdgeCapacity -> {...}]), else 1 for every edge ā€” Mathematica's documented rule. An explicit option wins over the stored list. An undirected edge carries flow either way.
  • Numbers (shared by the whole flow/cut family): integer capacities/weights give exact Integers; Rational or Real ones give a Real (as Mathematica); Infinity is an allowed capacity; a negative or symbolic one leaves the call unevaluated. Internally everything is int64: reals are scaled by a common power of two, so the max flow of machine-real capacities is computed exactly.
  • Algorithm: Dinic (BFS levels truncated at the sink, iterative blocking flow with current-arc pointers) on a CSR residual network.

Attributes: Protected.

References

See also: SparseArray, EdgeList, VertexList, EdgeWeight

Notes & additional examples

Notes

The flow value is capacity-limited: capacities come from the EdgeCapacity option (EdgeList order), defaulting to 1 per edge when none is given, and EdgeWeight plays no part. With integer capacities the answer is exact.

A fourth argument requests "FlowValue", "FlowMatrix", or "EdgeList". Sources and sinks may each be a list, and VertexCapacity bounds the flow through individual vertices. An undirected edge can carry flow in either direction; a directed edge only forwards.